두 종류 사이의 연결
사람과 작업을 정점으로 두고 사람이 맡을 수 있는 작업에만 간선을 잇는 상황을 생각할 수 있다. 사람끼리나 작업끼리의 간선 없이 두 종류 사이의 연결을 표현한다.
나눌 수 있는지가 핵심
정점들이 이미 두 줄로 그려져 있어야 하는 것은 아니다. 어떤 방식으로든 정점을 두 부분으로 나누어 간선 조건을 만족할 수 있으면 된다. 그림의 배치만으로 판단하지 않는다.
삼각형과 사각형
삼각형의 세 정점은 이런 두 부분으로 나눌 수 없다. 두 정점을 다른 부분에 두면 세 번째 정점이 양쪽 모두와 연결되어 문제가 생긴다. 반면 네 간선으로 둘러진 사각형은 번갈아 나누면 조건을 만족한다.
완전 이분 그래프
두 부분 사이에서 가능한 모든 정점 쌍을 연결하면 완전 이분 그래프가 된다. 두 부분의 정점 수가 m,n이면 Kₘ,ₙ으로 나타내고 간선 수는 mn이다. 같은 부분 안의 간선은 여전히 없다.
관련 문서
무향 그래프 / 단순 그래프 / 완전 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론) / 집합의 분할 / 집합