[2015 개정 교육과정]고급 수학 １ - Ⅳ. 그래프

 

 

1. 그래프와 행렬

$(1)$그래프의 뜻

 

①그래프란 무엇인가?

-그래프: 점과 선으로 이루어진 도형    ⇒    이산수학 그래프

-꼭짓점: 그래프에서 점

-변: 그래프에서 꼭짓점을 연결한 선

-그래프에서 꼭짓점의 위치를 바꾸거나, 변을 구부리거나 늘이거나 줄여도 두 그래프는 같은 그래프임

-두 그래프가 같은 그래프이면 꼭짓점의 집합과 변의 집합이 각각 같음

 

$(2)$꼭짓점의 차수와 합과 변의 개수 사이의 관계

 

①그래프의 꼭짓점의 차수란 무엇인가?

-차수: 한 꼭짓점에 연결된 변의 개수

-모든 꼭짓점의 차수의 합 $=$ 그래프의 변의 개수 $× 2$

-완전그래프: 서로 다른 두 꼭짓점 사이에 항상 변이 오직 한 개 있는 그래프

                  : 꼭짓점의 개수 $= n$

                  : 각 꼭짓점의 차수 $= n-1$

                  : 변의 개수 $= \displaystyle {n(n-1) \over 2}$

 

$(3)$인접행렬

 

①경로란 무엇인가?

-경로: 한 번 지난 변을 반복하지 않으면서 연결된 변을 따라 순서대로 꼭짓점을 나열한 것

-경로의 길이: 경로에서 지나는 변의 개수

-회로: 한 꼭짓점에서 출발하여 출발한 꼭짓점으로 돌아오는 경로

-회로의 길이: 회로에서 지나는 변의 개수

-인접행렬: 그래프의 두 꼭짓점이 한 변으로 연결되어 있으면 $1$, 연결되어 있지 않으면 $0$으로 하여

                그래프의 두 꼭짓점 사이의 관계를 나타낸 행렬

-인접행렬의 모든 성분의 합 $=$ 그래프의 변의 개수 $× 2$

-어떤 그래프의 인접행렬 $A$에 대하여 행렬 $A^2$의 $(i, j)$성분이 나타내는 의미는

 $i$번째 행에 해당하는 꼭짓점에서 한 개의 꼭짓점만을 거쳐 $j$번째 열에 해당하는 꼭짓점으로 가는 방법의 수임

 

 

 

2. 평면그래프와 수형도

 

$(1)$평면그래프

 

①평면그래프란 무엇인가?

-평면그래프: 평면에서 변들이 꼭짓점에서만 교차하는 그래프
                  : 꼭짓점의 개수 $v$ - 변의 개수 $e$ + 면의 개수 $f$ $= 2$

-면: 평면그래프에 의해 평면이 나누어지는 영역

 

$(2)$오일러그래프와 해밀턴그래프

 

①오일러그래프란 무엇인가?

-오일러 경로: 연결된 그래프의 모든 변을 지나며 한 번 지난 변을 다시 지나지 않는 경로
                     ⇒ 그래프의 모든 꼭짓점의 차수가 짝수이거나, 단 두 개의 꼭짓점의 차수만 홀수임(이 두 개의 꼭짓점이 시작과 끝임)

-오일러 회로: 연결된 그래프의 모든 변을 지나며 한 번 지난 변을 다시 지나지 않는 회로

                     ⇒ 그래프의 모든 꼭짓점의 차수가 짝수

-오일러그래프: 오일러 회로를 가지는 그래프

②해밀턴그래프란 무엇인가?

-해밀턴 경로: 연결된 그래프의 모든 꼭짓점을 한 번씩만 지나는 경로

-해밀턴 회로: 연결된 그래프의 모든 꼭짓점을 한 번씩만 지나는 회로

                     ⇒ 그래프의 꼭짓점의 개수가 $n$개$(n≥3)$이고 각 꼭짓점의 차수가 $\displaystyle {n \over 2}$ 이상임

-해밀턴그래프: 해밀턴 회로를 가지는 그래프

 

$(3)$수형도

 

①수형도$($트리$)$란 무엇인가?

-수형도: 회로를 가지고 있지 않은 연결된 그래프
           : 꼭짓점의 개수 $v$ - 변의 개수 $e$ + 면의 개수 $f$ $= 2$
           : 수형도에서 면의 개수는 $1$

           : 꼭짓점의 개수 $v$ - 변의 개수 $e$ $= 1$

           : 모든 꼭짓점의 차수의 합 $=$ 그래프의 변의 개수 $× 2$

②생성수형도란 무엇인가?

-생성수형도: 연결된 그래프에 회로가 포함된 경우 변을 일부 제거하여 수형도가 되면, 그 그래프의 생성수형도라고 함

                  : 즉, 그 그래프의 변의 일부분과 모든 꼭짓점으로 이루어진 수형도