1
그래프 노드를 다음 조건을 만족하는 두 개 이상의 분리 된 집합으로 나누는 알고리즘이나 코드가 있습니까 : 처음으로 제거 할 수있는 가장자리 만. 두 번째, 에지는 가중치가 적용되고 제거되는 에지는 최소 가중치 (최소 컷 알고리즘)를 가져야합니다. 셋째, 원하는 분리 세트는 가능한 한 동일한 크기를 갖는다.그래프를 최소 잘라 내기로 같은 크기의 분리 된 집합으로 나눕니다.
A
답변
2
그래프 G가 주어 졌을 때 Min-bisection 문제를 해결하려고하는 것처럼 보입니다. V [G]를 동일한 크기의 두 개의 분리 된 하위 집합 A와 B로 분할하려는 경우, A와 B 사이의 모서리가 최소화됩니다. 죄송합니다. the Min-bisection problem is known to be NP-hard. 그러나 Kernighan–Lin algorithm은 문제에 대한 매우 간단한 O (n^2 * logn) 휴리스틱 알고리즘입니다. 이론적으로는 알고리즘에 대해 알려진 것이 거의 없지만 (최적의 솔루션에 비해 성능에 대한 검증 된 한계가 없음) 알고리즘 is shown to be quite effective in experiments.
관련 문제
- 1. SConstruct 코드를 별칭 집합으로 나눕니다.
- 2. 텍스트 파일을 n 문자 집합으로 나눕니다.
- 3. 문자열을 java/android의 단어로만 같은 크기의 두 부분으로 나눕니다.
- 4. 그래프를 약 두 개의 하위 그래프로 나누는 그래프에서 잘라 내기
- 5. 분리 된 2 부분 그래프의 꼭지점을 똑같이 나눕니다.
- 6. NetworkX에서 그래프를 그려 플롯 영역을 3으로 나눕니다.
- 7. 시퀀스를 최대 크기의 연속 세트로 나눕니다. K
- 8. matlab : 벡터를 고정 크기의 겹치는 덩어리로 나눕니다.
- 9. 잘라 내기의 최소 및 최대 데이터의 열로 잘라 내기 수준 잘라 내기.
- 10. 최소 샘플 크기의 행 값으로 데이터 비대칭
- 11. 다른 크기의 host_subplots을 사용하여 그래프를 저장하려면 어떻게해야합니까?
- 12. 최소 제곱 회귀 그래프에서 최소 제곱 회귀 그래프를 그립니다.
- 13. 같은 크기의 다른 크기의 반응 이미지
- 14. Div 같은 크기의 화면마다
- 15. 같은 크기의 빈 넣기
- 16. 다른 초기화 된 집합으로 구성된 튜플이 같은 이유는 무엇입니까?
- 17. 숫자를 집합으로 캐스팅하는 방법
- 18. 축 분리 - 봉쇄 및 최소 변환 벡터
- 19. 그래프 잘라 내기 R
- 20. 카메라에서 미리 정의 된 사진 잘라 내기
- 21. R은 각각 같은 크기의 xts 객체를 포함하는 2 개의 목록 객체를 나눕니다.
- 22. 중첩 된 테이블을 중첩 된 집합으로 변환
- 23. 잘라
- 24. SQL 결과를 범위로 분리
- 25. QGraphicsView의 기능과 같은 층 분리
- 26. 삽입 간격이 간격이없는 집합으로 삽입
- 27. 어떻게 집합의 요소를 자바 스크립트에서 분리 된 하위 집합으로 그룹화 할 수 있습니까?
- 28. 나는이 같은 구조로 그래프를 최적화
- 29. 정수 범위를 거의 같은 정수 범위로 나눕니다.
- 30. 같은 원소로 배열을 작은 배열로 나눕니다.
감사합니다. 그래프에서 스패닝 트리 (O (| V | + | E |))를 찾을 수 없으면 스패닝 트리를 사용할 수 없다면 랜덤 에지 (마녀는 오름차순으로 가중치로 정렬 됨)를 제거 할 수 있습니까? 가장자리는 그래프를 분리하고 우리는 두 개의 분리 된 세트를가집니다. 그런 다음 분리 된 세트의 크기를 확인합니다. 세트의 크기가 O (V)의 순서로되어 있다고 가정합니다. 나 맞아? 나는 같은 크기의 세트가 실제로 필요한 것은 아니지만 가까운 비율로하는 것이 더 좋습니다. –
10과 90의 비율로 두 개의 분리 된 세트를 만드는 가장자리를 찾으면 만족할 만합니다. 그래프를 가능한 한 오랫동안 적은 수의 에지를 잃어 버린 두 개의 분리 된 세트로 나누기 위해 재귀 적 방식으로이 절차를 수행하고 싶습니다. –