- KMO/과학고/영재고 대비를 위한 그래프이론 교재(1권)입니다.

차 례
머릿말 v
List of Theorem ix
제 1 장 그래프 이론 1
1 그래프란 무엇인가? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 방향 그래프와 무방향 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 방향 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 무방향 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 기본 용어들 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4 꼭짓점의 차수 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5 고립된 꼭짓점과 펜던트 꼭짓점 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
제 2 장 그래프의 유형 19
1 그래프의 유형 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.1 공 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2 완전 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3 정규 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4 순환 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5 휠 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6 플라톤 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.7 N– 큐브 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 부분그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1 생성 부분그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 꼭짓점과 모서리 제거 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 유도 부분그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 그래프 동형 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

제 3 장 그래프의 연산 41
1 합집합 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2 교집합 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 두 그래프의 합 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 환의 합 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5 그래프의 곱 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6 그래프의 합성 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7 여 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8 융합 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
9 연결 그래프와 비연결 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
9.1 경로 그래프와 순환 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.2 계수와 퇴화차수 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
제 4 장 보행과 경로와 회로 59
1 보행 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2 경로 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3 회로 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4 길이 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 오일러 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.1 오일러 경로 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 오일러 회로 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6 플뢰리 알고리즘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
제 5 장 해밀턴 그래프 85
1 해밀토니안 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
2 디렉 정리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
제 6 장 트리 99
1 트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
1.1 비순환 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
1.2 트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
1.3 숲 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2 생성 트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.1 트리의 가지와 호 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3 루트 트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.1 코 – 트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4 이진 트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.1 이진트리의 경로의 길이 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.2 일반트리의 이진트리 표현 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.3 이분 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
제 7 장 트리의 개수 129
1 케일리 정리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
2 도달 가능성 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
2.1 거리와 지름 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3 최소 생성트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.1 가중 그래프 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.2 최소 생성트리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.3 최소 생성트리를 위한 알고리즘 . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.4 크러스컬 알고리즘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139