이분 그래프

1 개요

bipartite graph

二分 graph, 二分割 graph

이분 그래프, 이분할 그래프

• 그래프를 구성하는 정점들을 두 부분으로 나눌 때, 각 부분에 속하는 정점들이 모두 인접하지 않는 그래프
• 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프
• 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프
• 그래프의 정점들을 서로 다른 집합에 속한 정점들 사이에만 간선이 존재하도록 두 개의 집합으로 분할하는 것이 가능한 그래프

2 같이 보기

• 이분
• 그래프
• 이분할
• 완전 이분 그래프

3 참고

• 위키백과 "이분 그래프"
• 위키낱말사전 "이분 그래프"
• 다음사전 "이분 그래프"
• 다음백과 "이분 그래프"
• 네이버사전 "이분 그래프"
• 네이버백과 "이분 그래프"
• 나무위키 "이분 그래프"
• 리브레 위키 "이분 그래프"