이분 그래프: 두 판 사이의 차이
Osteologia (토론 | 기여) 잔글편집 요약 없음 |
Osteologia (토론 | 기여) 잔글 →바깥 고리 |
||
39번째 줄: | 39번째 줄: | ||
* {{eom|title=Graph, bipartite}} |
* {{eom|title=Graph, bipartite}} |
||
* {{매스월드|id=BipartiteGraph|title=Bipartite graph}} |
* {{매스월드|id=BipartiteGraph|title=Bipartite graph}} |
||
* {{매스월드|id=k- |
* {{매스월드|id=k-PartiteGraph|title=''k''-partite graph}} |
||
* {{매스월드|id=CompleteBipartiteGraph|title=Complete bipartite graph}} |
* {{매스월드|id=CompleteBipartiteGraph|title=Complete bipartite graph}} |
||
* {{매스월드|id=CompleteTripartiteGraph|title=Complete tripartite graph}} |
* {{매스월드|id=CompleteTripartiteGraph|title=Complete tripartite graph}} |
||
* {{매스월드|id= |
* {{매스월드|id=CompletekPartiteGraph|title=Complete ''k''-partite graph}} |
||
== 같이 보기 == |
== 같이 보기 == |
2017년 4월 18일 (화) 03:44 판
그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 변이 X에 있는 꼭짓점과 Y의 꼭짓점을 잇는 형태로 되도록 꼭짓점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다. 다르게 표현하자면, 그래프의 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다.
정의
그래프 와 자연수 가 주어졌다고 하자. 만약 가 다음과 같은 조건을 만족시키는 집합의 분할
을 가질 수 있다면, 를 분 그래프(-分graph, 영어: -partite graph)라고 한다.
- 변으로 연결된 두 꼭짓점은 서로 다른 분할 성분에 속한다. 즉, 임의의 변 에 대하여, 만약 이며 라면, 이다.
즉, 의 색칠수가 이하이어야 한다.
일 때, 이를 이분 그래프라고 한다. 마찬가지로, 일 때, 이를 삼분 그래프(三分graph, 영어: tripartite graph)라고 한다.
성질
임의의 유한 그래프 에 대하여 다음 두 조건이 서로 동치이다.
- 이분 그래프이다.
- 홀수 길이의 순환이 존재하지 않는다.
특히, 예를 들어 홀수 길이의 순환 그래프는 이분 그래프가 될 수 없다.
변별 알고리즘
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다.
예
0분 그래프는 공(空)그래프, 즉 꼭짓점과 변이 없는 그래프 밖에 없다. 1분 그래프는 이산 그래프(즉, 아무런 변이 없는 그래프)와 동치인 개념이다.
완비 분 그래프
집합 의 조각 분할
가 주어졌다고 하자. 이 집합의 분할에 대응하는 완비 분 그래프(영어: complete -partite graph)는 위와 같은 분할에 대하여 분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.
데생당팡
리만 곡면에 대하여, 어떤 유한 평면 이분 그래프를 대응시킬 수 있다. 이를 데생당팡이라고 한다.
바깥 고리
- “Graph, bipartite”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Bipartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “k-partite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Complete bipartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Complete tripartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Complete k-partite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.