[이산수학#9,10] 그래프

1. 기본사항

그래프는 꼭지점과 변으로 구성

병렬변 : 두 꼭지점을 연결하는 변이 복수개

루프 : 동일한 꼭지점을 연결하는 변

고립된 꼭지점 : 어떠한 변도 연결 X 꼭지점

 

동형 : 꼭지점과 변의 이름을 제외하고는 모두 동일한 그래프

방향 그래프 : 변이 방향을 가지는 그래프

무향 그래프 : 변이 방향이 없는 그래프

단순 그래프 : 루프와 병렬 변을 가지지 않는 무향 그래프

 

𝑮 = 𝑽, 𝑬 , 𝑯 = (𝑽 ′ , 𝑬′)

(1) 𝑽 ′ ⊆ 𝑽, 𝑬 ′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 부분 그래프(subgraph)

(2) 𝑽 ′ = 𝑽, 𝑬 ′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 신장 부분 그래프 (spanning subgraph)

 

총 차수 : 인접한 변의 개수

진입차수 : 들어오는 변의 개수

진출차수 : 나가는 변의 개수

 

path ⊂ trail ⊂ walk

워크 : 꼭지점과 변들을 순서대로 나열

트레일 : 변들이 서로 다른 것

경로 : 꼭지점이 모두 다른 것

 

2. 그래프 종류

완전 그래프 : 임의의 두 꼭지점을 연결하는 변이 항상 존재

이분 그래프 : 연결 성분이 분할되어 모든 변들이 꼭지점을 인접시키는 경우

완전 이분 그래프 : 완전한 이분 그래프

k-정규 그래프 : 모든 꼭지점들이 동일한 수의 인접한 꼭지점을 갖는 그래프

 

3. 그래프 표현

발생 행렬 : 꼭지점을 행으로 변을 열로 하여 발생관계를 표현

인접 행렬 : 꼭지점을 행과 열로 하여 꼭지점과 꼭지점 사이의 인접관계를 표현

인접 리스트 : 각 꼭지점에 인접하는 꼭지점들을 차례로 연결 리스트로 표현

 

4. 그래프의 탐색

평면그래프 : 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프 (정규, 완전 그래프)

ex) 오일러의 공식, 4색 정리

 

오일러 투어 : 모든 변들을 각각 한번만 지나는 트레일

- 연결 그래프가 오일러 투어를 가지기 위해서는 모든 꼭지점의 차수는 짝수

 

해밀턴 경로 : 모든 꼭지점들을 한번씩만 지나는 경로

 

5. 그래프의 활용

가중 그래프 : 그래프의 각 변에 실수값(가중치)이 붙여진 그래프

ex) 최단 경로 문제, 최소 신장 트리 문제