차례:
정의-이분 그래프는 무엇을 의미합니까?
이분 그래프는 그래프 정점 세트를 두 개의 독립된 세트로 나눌 수 있으며 동일한 세트 내의 두 그래프 정점이 인접 해 있지 않은 그래프입니다. 다시 말해, 이분 그래프는 두 개의 채색 가능한 그래프로 간주 될 수 있습니다. 이분 그래프는 주로 두 개의 개별 객체 클래스 사이의 모델링 관계에 주로 사용됩니다.
이분 그래프는 이력서라고도합니다.
Techopedia에서 이분 그래프 설명
이분 그래프에는 모서리가 그려 질 때 A의 모든 꼭지점과 B의 모든 꼭지점 사이에 연결할 수 있어야하는 두 개의 정점 세트 (예 : A 및 B)가 있습니다. 그래프에 포함되지 않은 경우 홀수주기 (그래프의 꼭짓점 수가 홀수)이면 스펙트럼이 대칭입니다. 동일한 색을 공유하는 인접한 정점을 갖지 않고 정점을 채색하는 데 필요한 최소 색 수인 색도는 이분 그래프의 경우 2보다 작거나 같아야합니다. 모든 유형의 비순환 그래프 (그래프주기가없는 그래프)는 이분 그래프의 예입니다. 순환주기 그래프는 관련된 모든주기가 균일 한 경우 이분으로 간주됩니다. 코닝의 선 채색 정리에 따르면 모든 이분 그래프는 클래스 1 그래프입니다.
이분 그래프는 모델링 관계에서 사용되는 것 외에 현대 코딩 이론에서 널리 사용됩니다.
