그래프 목차

• 정의
• 그래프 이론 유래
  • 그래프의 종류
  • 경로(path)
• 오일러의 경로(Eulerian path)
  • 오일러 경로를 판별하는 규칙
• 오일러 순회(Eulerian circuit)
  • 오일러 순회를 판별하는 규칙
• 오일러의 정리
• 해밀턴 경로(Hamiltonian Path)
  • NP-완전 Complete
• 해밀턴 순회(Hamiltonian circuit)
  • 외판원 문제 Travelling Salesman Problem(TSP)
  • 그래프의 표현

정의

그래프 이론에서 그래프란 객체의 일부 쌍 pair 들이 ‘연관되어’ 있는 객체 집합 구조
= ‘한붓 그리기’

• 그래프 이론은 논리회로 설계, 통신 네트워크, 작업계획 등 여러 방면에서 활용됨
• 기하학에 위상적인 개념을 접합시킨 응용으로서, 위상 기하학(Topological Geometry)적인 관계를 나타냄
• 그래프에서 점의 위치나 선의 길이 등에는 특별한 의미를 부여하지 않고 위상적인 형태에만 중점 둠
• 아래 그림의 (1)과 (2)는 위상적으로 서로 다르지만, (2)와 (3)은 위상적으로 같음
  

그래프 이론 유래

18세기 스위스 출신의 저명한 수학자 오일러 (Leonhard Euler, 1707~1783)에 의해 그래프 이론이 본격적으로 시작됨

쾨니히스베르크(Königsberg) 다리 문제

• 그래프 이론의 대표적인 예
• 두 개의 섬과 강둑 사이를 연결하는 7개의 다리가 있을 때 각 다리를 꼭 한 번씩만 건너는 경로를 찾는 문제임

[그래프 이론의 시작]*
오일러가 쾨니히스베르크(Königsberg) 다리 문제를 그래프로 품 -> ‘그래프 이론’의 시작
각각의 다리에 a부터 g까 지 이름을 부여하고 도식화해 해결

• Vertex: A부터 D까지의 정점
• Edge: a 부터 g까지의 간선
  

그래프의 종류

방향성 여부

1) 방향 그래프(directed graph 또는 digraph(다이그래프))

• 방향이 있는 그래프임
• 연결선을 화살표로 표시하여 방향을 나타내는 그래프임
• G=(V,E) 로 표시됨
  • V: 정점들의 집합
  • E: 정점등이 순서화된 아크, 즉, 간선
  • 정점 v에서 로 가는 그래프는 v-> w로 표시
• ex)
  
  • 1→ 2 → 3 → 4는 정점 1에서 정점 4로 가는 경로임
  • 선행자(predecessor): v → w인 아크에 대하여 v를 w의 선행자(predecessor)라 하며
  • 후속자(successor): w를 v의 후속자(successor)라고 함

2) 방향이 없는 그래프(undirected graph)

• 방향이 없는 그래프임
• 그래프의 특수한 형태이므로 특별한 언급이 없는 한 그래프는 방향이 없는 그래프를 의미함
• ex) V={1, 2, 3, 4}이며 E={(1, 2), (2, 3), (2, 4)}
  

정점들 간의 연결여부

1) 연결 그래프(connected graph)

• 그래프의 모든 정점들이 연결되어 있는 그래프임

2) 강한 연결 그래프(strongly connected graph)

• 그래프에서 모든 두 정점 a와 b에 대해서 a에서 b로의 경로와 b에서 a로의 경로들이 존재하는 그래프
• 서로 연결
• 특히 방향 그래프에서만 의미를 가짐

[용어]
연결 요소(connectivity component)

• 그래프에서 모든 정점들이 연결되어 있는 부분
  연결 수(connectivity number)
• 그래프 G에서의 연결 요소의 개수를 말함

연결선 개수

1) 단순그래프(simple graph)

• 한 쌍의 정점 사이에 많아도 하나의 연결선으로 아뤄짐
• 자기 자신으로의 연결선이 없음

2) 멀티 그래프(Multi-graph)

• 한 쌍의 정점 사이에 연결선의 개수의 제한이 없는 중복된 연결선을 허용
• 쾨니히스베르크 (Königsberg) 다리 문제를 해결하는 방법은 멀티 그래프를 모델링하는 것임
  

포함 관계

두개의 그래프 \(G=(V,E),G'=(V',E')\)에서,
1) 부분그래프(subgraph)

• \(V'⊆V,E'⊆E\),
• 이 그래프의 정점의 개수가 기준 그래프의 정점의 개수보다 작거나 같아야 함
• 이 그래프의 연결선의 개수가 기준 그래프의 연결선의 개수보다 작거나 같아야 함

2) 생성 부분 그래프(spanning subgraph)

• \(V=V_7^' E^'⊂E\),
• 이 그래프의 정점의 개수가 기준 그래프의 정점의 개수보다 같아야 함
• 이 그래프의 연결선의 개수가 기준 그래프의 연결선의 개수보다 작아야 함

• (2)는 (1)의 부분 그래프이자 생성부분그래프

두 부분집합으로 나눠짐

1) 이분그래프(bipartite graph)

• 그래프 G = (V,E)가 V가 두 부분집합 X와 Y= V-X로 나누어져 각 연결선이 X내의 정점과 Y내의 정점의 쌍으로 연결

1) 완전 이분그래프(complete bipartite graph)

• 이때 X내의 모든 정점들과 Y내의 모든 정점들 사이에서 연결선 존재
• \(K_{m,n}\): 완전이분그래프
  • m: X의 정점의 개수
  • n: Y의 정점의 개수
    

기타

[가중그래프(weight graph)]

• 가중값(weight): 그래프의 연결선에 0보다 큰 수가 할당되었을 때 이 값
• 이와 같은 그래프
  

[동형그래프(isomorphic graph)]

• 이어진 선들이 같음
• 일대일 대응(전단사 함수)
  

[평면그래프(planar graph)]

• 평면상에서 어떠한 연결선들도 서로 교차할 수 없도록 그려진 하나의 그래프
  
• (a): 평면그래프
• (b): 아님
• (위의 동형 그래프): 두개 다 평면 그래프

[완전그래프(complete graph)]

• 그래프 G=(V,E)의 모든 정점들의 쌍 사이에 연결선이 존재
• 즉, 각 꼭지점이 다른 모든 꼭지점들과 연결되는 그래프
• K_{n}: n개의 꼭지점으로 구성된 완전 그래프
• 연결선의 개수: n개의 정점을 가지는 완전 그래프에서의 연결선의 개수는 \((n(n-1))/2\) 개
  • 만약 n=5 인 경우, \((5*4)/2 =10\)개의 연결선을 가짐
    

[정규그래프]

• 그래프 G=(V,E)의 모든 꼭직점의 차수가 k이면
• G를 k차 정규그래프라고 함
  

[방향 비사이클 그래프(Directed Acyclic Graph)(DAG)]

• 사이클이 없는 방향 그래프
• 트리보다 일반적
• 방향 그레트보단 제한적
  

경로(path)

모든 1≤ i <k에 대해 연결선\((v_i , v_{i + 1} )\)이 존재할 때, 정점들의 열(sequence)

• \(v_1, v_2, v_-3, ⋯, v_k\)이 경로
• 경로의 길이: 이때 k ≥ 1이며 이 경로의 길이는 k－1임

[단순 경로(simple path)]

• 경로가 같은 연결선을 두 번 포함하지 않는 경로를 말함

[기본 경로(elementary path)]

• 어떤 정점들도 두 번 만나지 않는 경로를 말함

사이클(cycle) 또는 순회(circuit)

v1 = vk (k ≠ 1)이면 이러한 경로를 사이클이라고 함

• 경로 (v1, v2, , vn) 에서 종점 vn과 시점 v1이 일치하는 경우를 말함
• 자신으로 되돌아 오는 것

[단순 사이클(simple cycle)]

• 같은 연결선을 반복하여 방문하지 않는 사이클을 말함

[기본 사이클(elementary cycle)]

• 시작점을 제외한 어떠한 정점도 반복하여 방문하지 않는 사이클을 말함

deg(v)

• 정점 v의 차수 (degree)
• 정점 v와 연결된 연결선의 개수
• 그래프에서 모든 정점의 차수의 합은 연결선들의 개수의 2배

오일러의 경로(Eulerian path)

멀티 그래프에서 모든 연결선(간선)들을 꼭 한 번씩만 통과하는 경로

• 쾨니히스베르크 다리 문제는 오일러 경로를 찾을 수 있는지 여부와 동치임

오일러 경로를 판별하는 규칙

• 모든 정점에서 그것과 연결된 연결선의 차수가 홀수인 정점(홀수점)의 개수가 0 또는 2개인 경우임
• 그래프가 연결 그래프여야함

오일러 순회(Eulerian circuit)

• 꼭짓점 여러번 가능
• 각 연결선 한번만
• 첫번째로 돌아와야 함
• = 한붓 그리기(traversable)

오일러 순회를 판별하는 규칙

• 모든 정점에서 그것과 연결된 연결선의 차수가 모두 짝수
• 그래프가 연결 그래프여야함
  

오일러의 정리

\(v-e+f = 2\)

• v: 연결된 평면 그래프에서 꼭지점의 수
• e: 연결선의 수
• f: 면의 수 v-e+f = 2 이다.
  • 면의 수는 그래프 바깥의 면도 세어야 함

해밀턴 경로(Hamiltonian Path)

해밀턴 경로는 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로를 말함

• 오일러 경로: 간선을 기준으로 함
• 해밀턴 경로: 정점을 기준으로 함

NP-완전 Complete

해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 대표적인 NP-완전 Complete
(NP 문제 중 NP-난해 Hard 인 문제를 NP-완전 문제라 부른다) 문제임

• 그려서 찾는 방법밖에 없다.
  more learn about NP

해밀턴 순회(Hamiltonian circuit)

원래의 출발점으로 돌아오는 경로

외판원 문제 Travelling Salesman Problem(TSP)

이중에서도 특히 최단 거리를 찾는 문제는 알고리즘 분야에서 유명

• 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 문제
• 즉 최단 거리인 해밀턴 순환을 찾는 문제
• NP-난해 문제로 이론 컴퓨터과학 Theoretical Computer Science 분야의 매우 중요한 문제 중 하나
  
• 각 도시의 위치가 표시된 미국 지도가 있다.
• 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까?
  (만약 도시가 20개라고 할 때) 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 20! 20!=2,432,902,008,176,640,000이다.
  약 240 경 번의 경로를 다녀봐야 가장 짧은 경로를 찾을 수 있음
  문제는 단순하지만 정답 엄청남
  더 알아보기

그래프의 표현

컴퓨터에서의 그래프 활용

• 그래프는 그림을 이용하므로 이해하기 쉬운 방법임
• 컴퓨터는 그래프를 인접 행렬이나 인접 리스트에 의해 표현됨
  • 이를 통하여 컴퓨터 프로그램으로 구현됨
    (1) 인접 행렬(Adjacency Matrix)

• 그래프 G = (V, E)에서

  V

  = n일 때 G의 인접 행렬은 n × n 행렬 A로 나타내어지며,

• 이때 A의 각 원소 \(a_{ij}\)의 정의
  

(2) 인접 리스트(Adjacency List)

• 각 정점에 대해 포인터(pointer) 가 주어지고, 그 점으로부터 연결된 정점들을 차례로 연결 리스트(linked list)로 표시함
• 같은 리스트 내에서는 순서에 관계가 없음