728x90 이분 그래프1 이분 그래프 (Bipartite Graph) 정리 이분 그래프(Bipartite Graph) 란? 이분 그래프(Bipartite Graph)는 그래프의 정점을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 의미한다고 합니다. 제가 풀이한 백준 1707번 이분 그래프 문제에서는 설명하고 있어 무슨 말인가 싶어 구글링을 통해 찾아본 결과 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠했을 때 모든 정점을 두 가지의 색으로 칠할 수 있는 그래프이다! 이러한 성질로 인해서 같은 그룹의 정점끼리는 간선으로 연결되지 않고, 간선은 서로 다른 그룹에 대한 정점만을 연결하는 특징을 갖습니다. 참고로 간선 없이 하나의 정점으로 존재하는 그래프 또한 이분 그래프(Bipartite graph)라고 할 수 있습니다! 이분 그래프.. 2022. 9. 17. 이전 1 다음 728x90
