[NetwrokX] 방향그래프의 연결성분(Connected Components)

지난 글에서는 그래프의 연결성분에 대한 개념을 알아보았습니다.

특히 "무방향" 그래프에 대해서 알아보았습니다.

[NetwrokX] 그래프 연결성분(연결요소, Connected Components)

지난번의 포스트가 "무방향"임을 강조하는 이유는,

 

방향그래프에서의 연결성분을 확인하는 방식이 무방향그래프에서와는 조금 다를 수 있기 때문입니다.

 

 

방향그래프의 강연결(Strongly Connected)과 약연결(Weackly Connected)

아시다시피, 방향그래프에서의 엣지는 방향성을 가집니다.

즉, 편도라는 뜻입니다.

 

한 방향으로 밖에 이동할 수 없다는 점에서, 방향그래프의 연결성분을 파악하는데 차이가 발생합니다.

 

강연결 (Strongly Connected)

• 모든 노드쌍(u,v)에서, u→v, v→u 가 가능한가?

위의 그래프에서 (노드 H)에서 출발하면 (노드 G)에 다다를 수 있습니다. (H→G)

 

그럼 그 반대는요? 

(G)에서 (H)로 갈 수 있는 방법은 없습니다.

 

즉, 위의 그래프는 강연결 상태가 아닙니다.

nx.is_strongly_connected(G)
# False

 

 

약연결 (Weakly Connected)

• 모든 엣지를 무방향성으로 취급하자
• 이때, 모든 노드쌍(u,v)에서, u→v, v→u 가 가능한가?

모든 화살표의 방향성을 무시한다면 이제야 (D)에서 (A)까지 갈 수 있습니다.

모든 노드쌍(u, v)에서 u→v, v→u 가 가능합니다.

 

즉, 위의 그래프는 약연결 상태입니다.

nx.is_weakly_connected(G)
# True

 

 

강연결, 약연결 연결성분

연결성분(연결요소, Connected Component)의 개념 및 조건은 무방향그래프와 동일합니다.

 

연결성분의 조건

• 연결성분 안의 모든 노드들은 동일한 성분 내의 다른 노드와 연결되어 있어야한다.
• 연결성분 밖에 있는 노드와 연결되면 안된다.

여기서 방향그래프는

"엣지의 방향성을 고려할것인가(강연결) VS 무시할것인가(약연결)"를 생각해야한다는 점에서

무방향 그래프와 차이가 있습니다.

 

강연결 요소 (Strongly connected component)

sorted(nx.strongly_connected_components(G))

# 결과
[{'M'},{'L'},{'K'},{'A','B','C','D','E','F','G','J','N','O'},{'H','I'}]

 

 

약연결 요소 (Weakly connected component)

sorted(nx.weakly_connected_components(G))

# 결과
[{'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'}]