[이산수학] 그래프

그래프

 

그래프 $G = (V, E)$ 는 정접의 집합 V와 간선의 집합 E로 구성된다.

 

방향을 가진 그래프(directed graph)와 두 정점 간 대칭적인 관계인 무방향(undirected graph) 그래프가 있다.

• $e_k = (v_i, v_j)$ => $v_i$에서 $v_j$로 가는 방향을 가진 간선
• $e_k = \{v_i, v_j\}$ => 방향이 없는 간선

 

간선 e = (a, b)에 대해

• e는 정점 a, b에 인접하다
• e는 a에서 시작하고 b로 끝난다.
• e는 a에서 나다고 b로 들어간다.
• a는 b에 인접하다.
• a는 간선 (a, b)의 출발점이다.
• b는 간선 (a, b)의 도착점이다.

 

• (a, a)는 자기 자신을 연결한다. => loop
• 고립 정점 (isolated vertex) : 연결된 간선이 없다.

 

Walk

 

무방향 그래프에서 정점과 간선이 교대로 나타나는 열이면서 각 간선의 앞위에 위치한 정점을 그 간선의 양끝점으로 갖는 열

 

x-y walk는 정점 x에서 시작하여 n개의 간선을 지나 y로 끝난다. 이때 간선은 $e_i = \{x _{i - 1}, x_i\}$ 로 정의한다. 

 

walk의 길이는 포함된 간선의 수 n이다.

만약 n = 0일 경우 trival walk라고 한다.

 

시작점과 끝점이 같은 경우 Close Walk, 다른 경우 Open Walk 이다.

 

walk는 다양하게 존재할 수 있다.

 

Citcuit & Cycle

• x-y trail : x-y walk에서 간선이 반복되지 않는 경우
• Circuit : trail이면서 시작점과 끝점이 같은 경우
• x-y path : x-y walk에서 정점이 중복되지 않는 경우
• Cycle: path이면서 시작점과 끝점이 같은 경우

 

Examples of Circuit & Cycle

 

 

 

 

방향 그래프의 경우 direct walk, direct trail, direct path, ...

 

 

Connected Components

 

무향 그래프 G = (V, E) 에서 서로 다른 두 정점 u, v에 대해 path가 존재하면 connected graph 라고 함

 

연결된 그래프의 최대 연결된 부분 그래프를 연결성분이라고 한다.

 

$\kappa(G)$ : 그래프 G의 연결성분 개수

 

$\kappa(G) = 1$ 이면 그래프 전체가 연결되어 있다.

 

 

 

모든 정점의 path가 있기 때문에 $\kappa(G) = 1$이다

 

$\kappa(G) = 2$

 

두 개의 연결성분이 존재한다.

 

Connectivity in direct G

• Weakly connected : 간선의 방향을 없앴을 때 (방향 -> 무향으로 변경했을 때) 연결되어 있으면 Weakly
  • 모든 정점은 적어도 하나의 나가는 간선, 들어오는 간선이 있어야 한다.

• Strongly connected : 그래프 G의 모든 정점 {a, b}에 대해 a -> b , b -> a가 모두 존재하는 경우

• Unilaterally connected : 그래프 G의 모든 정점 {a, b}에 대해 a -> b 또는  b -> a가 존재하는 경우

• Multigraph : 두 정점 사이에 중복 간선이 허용되는 경우
  • (a, b)는 방향 multigraph
  • {a, b}는 무향 multigraph

 

 

Subgraph

 

 

그래프 G = (V, E)가 있을 때, $V_1 \subseteq V , E_1 \subseteq E$ 이면 $G_1 = (V_1, E_1)$ 은 G의 Subgraph이다.

 

 

• Spanning subgraph
  • G의 모든 정점을 포함할 경우

Induced subgraph

• Induced subgraph : 정점을 선택하면 그 정점들 간 원래 그래프에서 연결된 간선만 포함

 

G-v, G-e

 

G-v는 그래프 G에서 정점 v를 제거한 것

1. v를 제외한 모든 정점을 포함하고
2. 제거된 정점 v에 연결된 모든 정점을 제거한다.

 

G-e는 간선 e만 제거하고 모든 정점을 포함하는 것이다. spnning subgraph와 같다.

 

Complete Graph

 

Complete graph $K_n$은 모든 정점 쌍 사이에 간선이 존재하는 그래프이다. 

 

 

complete graph

 

Complement Graph

complete graph가 되도록 하는 그래프

complete 그래프 k에서 G에 포함되지 않은 간선만 포함한다.

 

$K_n$의 complement graph는 null이다.

 

complement graph

 

Isomorphism (동형)

 

Graph의 isomorphism은 그래프 $G_1(V_1, E_1), G_2(V_2, E_2)$ 가 있을 때

• 정점 $V_1$이 $V_2$ 에 일대일 대응되고
• 모든 간선 구조가 동일하게 유지 될 때

$G_1, G_2$를 isomorphic graphs 라고 한다.

 

 이 두 개의 그래프는 모양은 다르지만 Isomorphic이다.

 

 

각 정점이 일대일 대응되고 간선구조가 동일하기 때문이다.

 

 

Degree(차수)

 

무향 그래프 G가 있을 때 정점 v의 차수는 v에 연결된 간선의 개수이다.

 

loop은 차수 2로 계산된다.

 

차수 예시

 

무향 그래프에서 모든 정점의 차수 합은 간선 * 2이다.

$\sum_{v \in V} deg(v) = 2|E|$

 

각 간선은 두 정점에 연결되고 차수 1씩 기여한다. -> 2개씩 중복계산 된다.

 

홀수 차수를 가지는 정점의 개수는 항상 짝수이다. ->  전체 차수의 합이 |2E| 이기 때문에  홀수 차수를 가지는 정점이 홀수개 있다면 전체 차수의 합이 홀수가 되어 |2E| 가 성립하지 않는다. 

 

K - regular graph

 

모든 정점이 동일한 K개의 차수를 가지는 그래프

 

 

• 10개의 간선으로 4-regular graph를 만들 수 있을까?
  • 10개의 간선은 20개의 차수(2|E|)를 가진다. -> 5개의 정점으로 만들 수 있다.

Hypercubes

n-dimensional hypercube는 $2^n$개의 정점을 가지는 무향 그래프이다.

정점들은 n - bit로 이루어진 이진수 시퀀스이고 두 정점 v1, v2는 이진표현에서 정확히 하나의 비트만 다르다.

 

0~3 dimensional Hypercube

 

4 dimensional hypercube

 

n - dimensional hypercube의 차수는? => n개

 

 

Planar Graph (평면 그래프)

 

그래프 G가 평면에 그려질 수 있고 간선이 정점에서만 교차할 경우 planar라고 부른다.

=> 그래프가 평면에 겹침없이 표현 가능하다. 

=> 이러한 G의 그림을 평면에 G를 embedding한다고 한다.

 

$K_4$는 planar 그래프가 된다.

 

반면, $K_5$ 그래프는 planar 가 될 수 없다.

 

Bipartitle Graphs (이분 그래프)

 

그래프 G를 정점집합 두 개의 서로소 부분집합 V1, V2로 나눌 수 있어야 한다.

 

같은 부분집합에 속한 정점들끼리는 연결되지 않아야 한다.

 

Hypercube Q3도 이분 그래프와 동형이다.

 

Complete Bipartitle Graphs (완전 이분 그래프)

 

V1 집합의 모든 정점이 V2 집합의 모든 정점과 연결되어 있는 이분 그래프

만약 |V1| = m, |V2|=n 이면 그래프는 $K_{mn}$으로 표시한다.

 

하나의 정점은 다른 부분집합의 모든 정점과 연결되어 있다.

 

 

 

Subdivision (세분화)

 

elementary subdivision (기본 세분화) : 간선 e를 그래프 G에서 제거한 후 새로운 정점 v를 추가한 후 두 간선 {u, v}, {v, w}를 추가한다.

 

v는 기존 정점 집합에 속하지 않아야한다.

 

 

 

특정 간선에 새로운 정점을 삽입하여 그 간선을 두 개의 새로운 간선으로 나누는 작업이다.

 

 

Homeomorphic (동형적)

그래프 G1과 G2가 Homeomorphic이려면 

• 두 그래프가 isomorphic
• elementary subdivision을 통해 생성된 그래프의 경우
• G1의 세분화 중 하나인 G1'가 G2의 세분화 중 하나 G2'가 서로 동형일 경우

 

기본 그래프 H

 

 기본 그래프 H에서 세분화를 통해 생성된 두 그래프는 서로 homeomorphic이다. 

 

 

기존 두 그래프에서 세분화를 통해 생긴 두 그래프가 서로 동형일 경우 기존 두 그래프는 서로 homeomorphic이다.

 

homeomorphic은 구조적으로 동일하다는 뜻이다.

 

하나의 그래프에서 간선 중간에 차수가 2인 정점을 추가하거나 제거하는 방식으로 다른 그래프를 만들 수 있는 경우 두 그래프를 Homeomorphic 하다고 한다.

 

예를 들어 A-B-C라는 간선을 갖는 그래프가 있다면 A-X-B-C 와 같이 X라는 차수가 2인 정점을 추가해도 Homeomorphic하다고 말할 수 있다.

 

두 그래프가 서로 Homeomorphic 이라면 둘다 planar이거나 둘 다 nonplanar이다.

 

 

 

Hamilton Path & Cycle

 

그래프 G에서 모든 정점을 한 번만 지나고 다시 출발점이라면 그 cycle을 Hamilton cycle이라고 한다. 그리고 Hamilton cycle을 포함하는 그래프를 Hamiltonian graph라고 한다.

 

Hamilton path는 모든 정점을 한 번만 지나가지만 사이클이 아닌 단순 경로이다.

 

 

Hamilton Cycle

 

Non-Hamilton Cycle

 

 

TSP (외판원 순회)

Greedy Algorithm 으로 출발지에서 가장 비용이 낮은 간선을 선택해 다음 정점으로 가는 방법을 사용할 수 잇다.

하지만 항상 최적 해를 보장하지 않는다.

 

Greedy Algorithm은 항상 최적해가 아니다.

이를 슈도 코드로 표현하면 다음과 같다.