그래프 G가 bipartite면 G는 홀수 cycle을 가지지 않는다. (bipartite) / Graph Theory #2

graph theory

A graph is bipartite iff it has no odd cycle.

위의 정리를 이해하려면 bipartite graph가 무엇인지 알아야 한다. 정의는 다음과 같다.

A graph G is bipartite if V(G) is the union of two disjoint (possibly empty) independent sets.

정의가 한 번에 이해가 되지는 않는다. 자세히 풀어보면, 그래프 G의 vertices가 두 개의 disjoint independent sets의 합집합이라고 한다.

모든 닫힌 홀수 walk는 홀수 cycle을 포함한다. (walk, trail, path, cycle) / Graph Theory #1

graph theory

Every closed odd walk contains an odd cycle. (모든 닫힌 홀수 walk는 홀수 cycle을 포함한다.)

위의 정리를 이해하려면 walk와 path에 대해서 알아야 한다. Graph는 vertex와 edge로 이루어져 있다. 하나의 vertex에서 다른 vertex로 edge를 통해서 이동하는 상상을 쉽게 해볼 수 있을 것이다. 이처럼 edge를 통해서 vertex를 이동하는 ‘길’을 walk라고 한다.