알고리즘 그룹의 모든 싸이클 함께

Question

I는 에지 1가 {1:2}이다 에지 2가 {2:3}이다 에지 3은 {3,4}이고 숫자 값으로 나타내는 사이클이 많이 (예를 들어, 1-2-3-4 4 개 모서리와 사이클에 대응해야 가장자리 4은 {4,1} 등입니다.

주기가 하나의 가장자리를 공유하는 경우 다른주기와 연결되는 것으로 알려져 있습니다.

예를 들어 두 사이클이 1-2-3-4과 5-6-7-8 인 경우 두 사이클이 서로 연결되어 있지 않으므로 두 개의 사이클 그룹이 있다고 가정 해 보겠습니다. 1-2-3-4과 3-4-5-6의 두주기가있는 경우이 두주기가 같은 가장자리를 공유하기 때문에 하나의주기 그룹 만 있습니다.

아래 그림은 나의 점을 설명 할 수 있어야한다 :

alt text http://lh5.ggpht.com/_SDci0Pf3tzU/SuBhd07xbWI/AAAAAAAAFMs/9OlMhN8uzzQ/s640/mst.jpg

R1, R2R7에 내가 "주기"라고 부릅니다 있습니다. 위 그림에서 R1부터 R7까지를 포함하는 하나의주기 그룹 만 있습니다.

모든 사이클 그룹을 찾는 가장 효율적인 방법은 무엇입니까?

Answer 1

First 그래프의 모든주기를 찾아 예를 들어 A, B, C 등으로 레이블을 붙이십시오. 이제 그래프에있는 각주기가 새 그래프의 단일 노드로 변환되는 새 그래프를 만드십시오. 연관된 그래프가 오래된 그래프에서 "연결"되어있는 경우, 새로운 그래프의 가장자리가있는 노드를 연결하십시오 (다소 특이한) 연결 정의를 사용하십시오.

"주기 그룹 수"는 새 그래프의 connected components입니다.

Answer 2

나는 이것이 가장 효율적인 방법 아니라는 것을 확신 해요,하지만 이건 내 최초의 시도가 될 것입니다 :

먼저 교환이 정점에 가장자리 : 그래서 예를주기 1-2-3-4, 3-4-5-6 및 5-6-7-8를 들어, 'LL 필요 :이 괜찮 (V의 * (V-1))/2 정점,하지만 당신을 포기

"12" => "A" 
"23" => "B" 
"34" => "C" 
"45" => "D" 
"56" => "E" 
"67" => "F" 
"78" => "G" 
"41" => "H" 
"63" => "I" 
"85" => "J" 

- 그것은 여전히 ​​O (V^2) 알고리즘 충분 될 수 있습니다.

그리고 비트 필드로주기를 나타냅니다 은 "1-2-3-4은"

ABCDEFGHIJ 
1110000100 

ABCH

와 "3-4-5-6"가 CDEI

가되도록

ABCDEFGHIJ 
0011100010 

그들은 정확히 하나의 비트를 공유합니다. 즉, 원래의 그래프에서 정확히 한 모서리가 공통점을 가졌음을 의미합니다. 이것은 O (v^2)로 비트 단위로 검사하거나 바이너리 탐색 (비트가 공통 인 비트가있는 경우 ANDing을 먼저 수행 한 다음 비트의 처음 절반을 ANDing으로 검사)을 통해 확인할 수 있습니다.