[이산수학] 그래프 : 용어(동형,방향,무향...), 탐색(워크,트레일,경로), 종류(완전,이분,정규), 표현(발생/인접행렬, 인접리스트), 오일러투어, 4색정리, 해밀턴경로

본 게시글은 대학 전공수업을 들으며 노션에 정리한 내용을 블로그로 옮긴 것으로, 노션 웹을 통해 최적화된 형태로 읽으시길 권장드립니다.(➡️ 노션 링크)

기본사항

그래프란?

쾨히스베르크 다리건너기 문제

🔗나무위키: 쾨니히스베르크 다리 건너기 문제

한 붓 그리기, 오일러 경로

https://namu.wiki/w/쾨니히스베르크 다리 건너기 문제

쾨니히스베르크시의 한 가운데는 프레겔 강[1]이 흐르고 있고 여기에는 가운데 섬들과 연결되어있는 일곱 개의 다리가 있다. 그 다리들을 한 번씩만 차례로 모두 건널 수 있겠는가?

추상화

주요 용어

https://gamedevlog.tistory.com/15

𝑮 = (𝑽, 𝑬)

𝑽 = {𝒗|𝒗는 꼭지점(vertex)}

𝑬 = {𝒆|𝒆는 변(edge})

• 변은 두 꼭지점을 연결함. (변에 의해 발생(incident)되었다.)
• 연결된 두 꼭지점은 서로 인접(adjacent)한다고 함
• 병렬 변(parallel edge) : 두 꼭지점을 연결하는 변이 복수개 있을 때
• 루프(loop) : 동일한 꼭지점을 연결하는 변
• 고립된 꼭지점(isolated vertex) : 어떠한 변도 연결되지 않은 꼭지점

병렬변과 루프

 

동형(isomorphic)

꼭지점과 변의 이름만 제외하고는 모두 동일한 그래프들을 서로 동형이라고 함.

https://math.stackexchange.com/questions/3141500/are-these-two-graphs-isomorphic-why-why-not

방향 그래프(directed graph)

:변이 방향을 가지고 있는 그래프(화살표 보이죠?)

무향 그래프(undirected graph)

:변이 방향을 가지고 있지 않은 그래프(화살표 없죠?)

단순 그래프(simple graph)

:루프와 병렬 변을 가지지 않는 무향 그래프

부분그래프(subgraph)

𝑮 = 𝑽, 𝑬 , 𝑯 = (𝑽′, 𝑬′)가 그래프일 때,

𝑽′ ⊆ 𝑽, 𝑬′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 부분 그래프라고 한다.

(즉, 포함 되는것!)

신장부분그래프(spanning subgraph)

𝑮 = 𝑽, 𝑬 , 𝑯 = (𝑽′, 𝑬′)가 그래프일 때,

𝑽′ = 𝑽, 𝑬′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 신장 부분 그래프라고 한다.

(즉, 꼭짓점은 그대로인데, 변이 적은 것)

차수(degree)

𝑮 = 𝑽, 𝑬 , 𝒗 ∈ 𝑽에서

𝒗에 인접한 변의 개수를 차수, [𝐝𝐞𝐠 𝒗 ]

총 차수(total degree)

𝑮에 속한 모든 꼭지점의 차수의 합을 총 차수라 하고,

[𝐝𝐞𝐠 𝑮 ] = $\sigma_{𝒗 ∈ 𝑽}\space deg(v)$

• 그래프에서 총 차수는 항상 짝수다.(handshaking Lemma : 악수를 한다는건 손이 2개이다!)

그래프 탐색

𝑮 𝑽, 𝑬 , 𝒗𝟎, 𝒗𝒌 ∈ 𝑽일 때,

https://symbio6.nl/en/blog/theory/definition/trail //

위 이미지 링크의 영어 설명 : Figure 1. Walk (vertices and edges can be repeated) vs. trail (edges are not repeated, but vertices can be repeated) vs. path (neither vertices nor edges are repeated). Labels are traversal steps.

워크(walk)

𝒗𝟎에서 𝒗𝒌까지의 워크

= 𝒗𝟎에서 시작하여 𝒗𝒌에 도착하는 꼭지점과 변들을 순서대로 나열한 것

W = 𝒗𝟎𝒆𝟏𝒗𝟏𝒆𝟐𝒗𝟐⋯ 𝒆𝒌𝒗𝒌

➔ 𝒗𝟎 → 𝒗𝟏 → 𝒗𝟐 → ⋯ → 𝒗𝒌

➔ 𝒆𝟏𝒆𝟐𝒆𝟑⋯ 𝒆𝒌

• $v_0$: 시작점, $v_k$: 종점, $v_1,v_2 \space ⋯ v_{k-1}$: 내부점
• k: W의 길이(length)
• $v_0$=$v_k$이면 W는 닫혀있다(closed)

트레일(trail)

워크 W의 변들이 모두 서로 다르면, W를 트레일 이라고 한다.

마찬가지로, $v_0$=$v_k$이면 W는 닫혀있다(closed)

경로(path)

트레일 W의 꼭지점이 모두 다르면, W를 경로 라고 한다.

마찬가지로, $v_0$=$v_k$이면 W는 닫혀있다(closed)

💡 즉, path ⊂ trail ⊂ walk

---

연결 그래프(connected graph)

https://www.gatevidyalay.com/tag/connected-graph-definition/

𝑮 = (𝑽, 𝑬) : 그래프이고, 𝒖, 𝒗 ∈ 𝑽일 때

• 𝒖에서 𝒗로 가는 경로가 존재하면 ⇒ 𝒖와 𝒗는 연결
• 𝑽의 꼭지점들은 서로 연결되고 다른 집합과 겹치지 않는 꼭지점들의 집합 𝑽𝟏, 𝑽𝟐,
  ⋯ 𝑽𝒏으로 나눌 수 있음. 이때 𝑽𝟏, 𝑽𝟐, ⋯ 𝑽𝒏을 𝑮의 연결성분
• ∀𝒖 , ∀𝒗 ∈ 𝑽, 𝒖에서 𝒗로 가는 경로가 존재하면 G는 연결 그래프(connected graph)
  • G는 오직 하나의 연결 성분으로 구성.

그래프의 종류

완전 그래프(complete graph)

임의의 두 꼭지점(아무 꼭지점)을 연결하는 변이 항상 존재하는 그래프.

즉, 𝑮 = 𝑽, 𝑬 : 그래프이고, ∀𝒖, ∀𝒗 ∈ 𝑽, ∃𝒆 = (𝒖, 𝒗) ∈ 𝑬 이면

𝑮는 완전 그래프이다. 이 때,

𝑲𝒏 을 |𝑽| = 𝒏인 완전 그래프라고 한다. (𝒏 = 꼭지점의 개수)

완전그래프 $K_n은\space \frac{n(n-1)}{2}$개의 변을 가짐

각각의 꼭짓점의 차수는 𝒏-1개.

이분 그래프(bipartite graph)

𝑽는 연결성분 $V_1$과 $V_2$로 분할되어 있고, 모든 변들이 $V_1$의 꼭지점과 $V_2$의 꼭지점을
인접시키는 경우

(= 두 개의 노드 집합이 있고, 한 집합의 노드에서 다른 집합의 노드로만 간선이 존재하는 그래프)

= 기호로 하면,

$(1) V_1 \cup V_2 = V, \quad V_1 \cap V_2 = \emptyset$

(=노드 집합이 두 개로 나뉘어 있으며, 각 집합의 노드 간에는 직접적인 연결(간선)이 없다.)

$\
(2) \forall e = (v_1, v_2) \in E, ; v_1 \in V_1, ; v_2 \in V_2$

(=간선은 항상 한 집합의 노드에서 다른 집합의 노드로 연결된다.)

완전이분그래프(Complete bipartite graph)

: 두 집합의 모든 노드가 서로 완전히 연결된 그래프

𝑮 = 𝑽, 𝑬 : 이분 그래프 (𝑽𝟏 ۩ 𝑽𝟐 = 𝑽) 일 때,

∀𝒗𝟏 ∈ 𝑽𝟏, ∀𝒗𝟐 ∈ 𝑽𝟐, ∃𝒆 = (𝒗𝟏, 𝒗𝟐) ∈ 𝑬이면 G를 완전 이분그래프라고 한다.

$K_{m,n} : |V_1|=m, \space |V_2|=n$ 인 완전 이분그래프

💡 이분 그래프와 비교해볼 것!

$\forall e = (v_1, v_2) \in E, ; v_1 \in V_1, ; v_2 \in V_2$

정규 그래프(regular graph)

𝑮 = 𝑽, 𝑬 : 그래프일때, 𝑮의 모든 꼭지점들이 동일한 수의 인접한 꼭지점을 갖는 경우

즉, ∀𝒗 ∈ 𝑽, 𝐝𝐞𝐠 𝒗 = 𝒌.

source: https://www.gatevidyalay.com/tag/connected-graph-definition/ ]

• A graph in which degree of all the vertices is same is called as a regular graph.
• If all the vertices in a graph are of degree ‘k’, then it is called as a “k-regular graph“. they are 2-Regular graphs.

그래프의 표현

발생 행렬(incidence matrix)

꼭지점을 행으로, 변을 열로 하여 변과 꼭지점 사이의 발생관계를 표현한 행렬

⇒ 발생행렬 $M_I=(a_{ij})$

• |𝑽| × |𝑬| 크기의 부울행렬
• $a_{ij}=1$ ($v_i가 e_j$에 의해 발생되는 경우)
• $a_{ij}=0$ (그 밖의 경우)

3 x 4 크기의 부울행렬.

인접 행렬(adjacency matrix)

꼭지점을 행과 열로 하여 꼭지점과 꼭지점 사이의 인접관계를 표현한 행렬

⇒ 인접행렬 $M_A=(a_{ij})$

• |𝑽| × |𝑽| 크기의 행렬(= 정방행렬)
• $a_{ij}=v_i에서 v_j$로의 연결 개수

인접 리스트(adjacency list)

각 꼭지점에 인접하는 꼭지점들을 차례로 연결 리스트(LinkedList)로 표현한 것

 

굿 윌 헌팅의 문제

-그래프의 조합론적 경로 문제 (Combinatorial Graph Paths Problem)

: 그래프의 인접행렬을 사용하여 노드 간의 연결 관계를 나타내고, 이를 통해 경로를 분석

그래프의 탐색

평면 그래프(planar graph)

그래프의 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프.

https://en.wikipedia.org/wiki/Planar_graph

오일러의 공식 (Euler’s Formula)

연결된 평면 그래프에서 면(face) 변들로 만들어지는 사이클을 경계로 형성된 공간

연결된 평면 그래프에서 꼭지점의 수를 𝒗, 변의 수를 𝒆, 면의 수를 𝒇라고 하면

𝒗 − 𝒆 + 𝒇 = 𝟐 이다.

4색 정리

https://ko.wikipedia.org/wiki/4색_정리

지도의 인접한 구역을 서로 다른 색으로 칠하는데 오직 4가지 색이면 충분하다.

(= 평면 그래프가 주어졌을 때, 각 꼭지점에 대하여 인접한 꼭지점과 서로 다른 색으로 칠하는데 필요한 색은 4가지이면 충분하다.)

오일러 투어(Eulerian tour)

https://en.wikipedia.org/wiki/Euler_tour_technique

• 오일러 트레일 (Eulerian trail)

그래프의 모든 변들을 각각 한 번만 지나는 트레일

• 오일러 투어 (Eulerian tour [circuit/cycle])

닫힌 오일러 트레일 (= 시작점과 종점이 같은 오일러 트레일)

 

해밀턴 경로(Hamiltonian path)

: 그래프의 모든 꼭지점들을 한 번씩만 지나는 경로

해밀턴 사이클 (Hamiltonian cycle)

닫힌 해밀턴 경로**(시작점과 종점이 같은 해밀턴 경로)**

= A Hamiltonian path is a path in an undirected graph that visits each vertex exactly once.

https://www.geeksforgeeks.org/hamiltonian-path-using-dynamic-programming/

 

 

이런거 알아서 어디 써먹는데?

• 가중그래프(weighted graph)
• 최단경로 문제(다익스트라 알고리즘 / (Dijkstra’s Shortest Paths)
• 최소신장트리(Minimal Spanning Tree)
• ⇒ 자세한 내용은 알고리즘 에서! (생략)

Weighted graph, https://hyperskill.org/learn/step/5645

Dijkstras Shortest Path, https://www.youtube.com/watch?v=bZkzH5x0SKU

Minimal Spanning Tree, https://www.youtube.com/watch?app=desktop&v=r4jf5d4_7S4