[자료설명]
- 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
|