이산수학 9강 :: 그래프(1/2), 용어, 종류

이산수학 9강을 보며 배운내용

 

 

한 붓 그리기
홀수 점이 없거나, 2개인 경우만 가능

 

 

그래프 용어를 정리하자

꼭지점(vertex)와 변(edge)로 구성

• 변: 두 꼭지점을 연결
• 인접(adjacent): 연결된 두 꼭지점을 인접한 꼭지점라고 한다
• 병렬변(parallel edge): 두 꼭지점 사이에 변이 여러 개 일때
• 루프(loop): 자기 자신을 가리키는 변
• 고립된 꼭지점(isolated vertext): 어떤 변이랑도 연결 안된 것

• 방향 그래프: 방향이 있는 그래프
• 무향 그래프: 방향이 없는 그래프
• 단순 그래프: 루프와 병렬변이 없는 무향 그래프

 

그래프에서 총 차수는 항상 짝수다!
변은 항상 2개의 꼭지점을 발생시키니까

 

그래프 탐색정의 그리고 워크, 트레일, 경로

기본 가정

 

정의 1

 

정의 2

워크 W의 변들이 모두 다르면 W를 트레일(trail)이라고 부른다

 

정의 3

트레일 W의 꼭지점이 모두 다르면 W를 경로(path)라고 부른다

 

워크 vs 트레일 vs 경로

다음과 같은 그래프에서 워크, 트레일, 경로를 알아보자

 

• 워크: e1 e2 e2 e3 e4
• 트레일: e1 e2 e3 e4
• 경로: e1 e3 e4

 

 

그래프의 종류 이런 것들이 있다

완전 그래프

각 꼭지점이 다른 모든 꼭지점들과 연결되어 있는 그래프

임의의 두 꼭지점을 연결하는 변이 꼭 존재하는 그래프

변의 개수: n(n - 1) / 2

각 꼭지점의 차수: n - 1

 

이분 그래프

밑의 그림에서 위의 꼭지점은 V1, 아래 꼭지점은 V2라고 하자,

V1 끼리 혹은 V2 끼리 연결되어 있지 않다

하지만, V1과 V2는 연결되어있다

이런걸 이분 그래프라고 한다

 

k-정규 그래프

G = (V, E) 그래프

G의 모든 꼭지점이 동일한 수의 인접한 꼭지점을 갖는다

 

예시

 

위의 3-정규 그래프는 각 꼭지점을 연결하는 변이 모두 존재한다
=> 완전 그래프  

 

 

Link by Shreya Thomas @unsplash