그래프 이론 기초 플래시카드

Question 1

그래프 $G=(V,E)$란 무엇인가?

Accepted Answer

그래프는 순서쌍 $G=(V,E)$로, $V$는 정점(노드)의 집합이고 $E$는 간선의 집합이며 각 간선은 두 정점을 잇는다(무방향 그래프에서 간선은 순서 없는 쌍 $\{u,v\}$이다).

Question 2

워크(walk), 경로(path), 사이클(cycle)의 차이는 무엇인가?

Accepted Answer

워크는 정점/간선을 반복해도 된다. 경로는 정점을 반복하지 않는 워크이다. 사이클은 닫힌 경로(시작 = 끝)로, 첫/마지막 정점을 제외하고 정점이 반복되지 않는다.

Question 3

그래프가 평면 그래프(planar)라는 것은 무엇을 의미하며, 연결된 평면 그래프에 대한 오일러 공식은 무엇인가?

Accepted Answer

평면 그래프란 간선이 서로 교차하지 않도록(정점에서 만나는 경우는 제외) 평면 위에 그릴 수 있는 그래프를 뜻한다. 연결된 평면 임베딩에 대해 $$V-E+F=2,$$ 여기서 $F$는 면의 개수(바깥 면 포함)이다.

AI로 수학 마스터하기