[정보올림피아드 대비]18.그래프 관련 문제(한붓그리기외)

1. 그래프란?

그래프 : G=(V,E)

여기서 V는 정점(Node 라고도 하며 꼭짓점이라고도 한다.), E는 엣지( Vi~Vj 를 연결하는 모서리)라고 하며

그래프는 정점과 모서리의 집합으로 구성된 구조를 의미한다.

예)

위와 같은 형태가 그래프이다.

 

2. 그래프 인접(Adjacent),근접(Incident),루프(Loop)

- 인접(Adjacent),근접(Incident) 

그래프 G=(V,E)에서 꼭짓점 a와 b를 연결한 모서리 ab가 있을 때 꼭짓점 a와 b는 서로 인접하고 모서리 ab는 꼭짓점 a와 b에 근접한다.

 - 루프(Loop)

인접하는 꼭짓점이 하나인 모서리 e

 

3. 방향그래프

화살표로 모서리를 표현해 인접하는 꼭짓점 간의 순서를 알 수 있는 그래프

G = <V,E> 로 표현하며 인접하는 꼭짓점 사이에 순서가 존재

V={a,c,d}

E={<d,a>,<d,c>,<c,d>} 

와 같이 표현

 

4. 가중치 그래프

G=(V,E) 에서 각 모서리에 가중치가 부여된 그래프

위와 같이 경로에 가중치가 부여 되어 있다.

이러한  가중치를 표현하는 방법은 테이블 형태로 표현 할 수 있다.

	a	b	c
a	0	3	5
b	6	0	8
c	INF	INF	0

 

5. 그래프의 차수(Degree)

차수(Degree)란?

꼭짓점 v에 근접하는 모서리의 수

• 홀수점(odd Degree) : 차수가 홀수인 꼭짓점
• 짝수점(even Degree) : 차수가 짝수인 꼭짓점

방향 그래프에서는

• 외차수(out degree): 꼭짓점 v를 시작으로 하는 화살표의 수
• 내차수(in degree) : 꼭짓점 v를 끝으로 하는 화살표의 수

위와 같은 그래프에서 차수를 확인하면

1의 차수 : 1

2의 차수 : 3

모두 홀수점을 가지고 있다.

차수에 대한 정리 (정보올림피아드 유형에서 자주 출제된다.) 그래프 G=(V,E)에서 모든 꼭짓점의 차수의 합은 모서리 수의 두배이다. (당연한 이야기 이지만 모서리 하나에는 꼭짓점 2개를 연결하므로 차수의 합은 모서리의 2배이다.) 그래프 G=(V,E)에서 차수가 홀수인 꼭짓점의 수는 짝수이다. (잘 생각해 보면 모서리가 없을때 차수가 (0,0,0,...0) 부터 시작하는데 모서리가 하나가 생긴다면 (1,1,0,0...,0) 과 같이 생기고 다음 모서리 연결 과정에서 홀수와 홀수,홀수와 짝수, 짝수와 짝수를 연결하는 세가지 형태밖에 없다. 이때 홀수의 갯수는 짝수개가 될 수 밖에 없다.)

 

6. 부분그래프와 부분 신장그래프

부분그래프란?

G=(V,E)가 있을 때 V' 는 V의 부분집합이고, E'는 E에 부분집합인 G' =(V',E') 그래프

즉 어떤 그래프 G에 포함되는 일부 꼭짓점과 모서리로만 그린 그래프

예)

위와 같이 V={A,B,C,D},E={(A,B),(B,C),(B,D),(A,D)} 와 같은 G=(V,E)로 되어 있는 그래프와

V'={A,B,D},E'={(A,B),(B,D),(A,D)} 와 같은 G'=(V',E') 그래프가 있다면 G'는 G의 부분 그래프라고 한다.

 

부분 신장 그래프란

부분그래프 중에서 그래프 G의 꼭짓점을 모두 포함하지만 모서리는 일부만 포함하는 그래프

예)

위와 같이 V={A,B,C,D},E={(A,B),(B,C),(B,D),(A,D)} 와 같은 G=(V,E)로 되어 있는 그래프와

V'={A,B,C,D},E'={(A,B),(B,D),(B,C)} 와 같은 G'=(V',E') 그래프가 있다면 G'는 G의 부분 신장 그래프라고 한다.

여기서 꼭짓점을 모두 포함 되는 것을 판단하면 된다.

 

7. 연결그래프(Connected Graph)

그래프 G =(V,E) 내에 있는 임의의 꼭짓점 u,v 간의 경로가 있는 그래프

예)

그래프A는 어떤 임의의 꼭짓점간에도 모두 경로가 있지만

그래프B는 어떤 임의의 꼭짓점 b와 e를 선택하면 경로가 없다.
따라서 그래프A는 연결그래프이고 그래프B는 연결그래프가 아니다.

 

8. 완전그래프(Complete Graph)

그래프 G=(V,E) 내에 있는 모든 n개의 꼭짓점 사이에 모서리가 있는 그래프

예) 꼭짓점이 5개인 완전 그래프

 

9. 경로에 관련한 개념

순환(Cycle) 또는 회로(Circuit) : 시작하는 꼭짓점과 끝나는 꼭짓점이 같은 경로

예)

왼쪽의 그래프에서 Cycle을 찾으면 오른쪽 빨간색 경로가 된다.

 

10.오일러 그래프

- 오일러 경로(Eulerian Path) : 그래프 G=(V,E)의 모든 모서리를 꼭 한 번씩만 지나는 경로

- 오일로순환(Eulerian Cycle) 또는 오일러회로(Eulerian Circuit) : G=(V,E)의 꼭짓점 v에서 시작해 모든 모서리를 꼭 한번씩만 지나 v로 다시 돌아 오는 경로

- 오일러그래프(Eulerian Graph) : 오일러순환을 가지는 그래프

예)

a 또는 d에서 시작해 모든 모서리를 한번씩 거쳐서 다른 d 또는 a 에 도착하는 오일러 경로를 가지는 그래프 이지만 오일러 순환은 아니다.

어떤 정점에서 시작하더라도 모든 모서리를 한번씩 거쳐서 자신에게 올 수 있다. 오일러 순환을 가지므로 오일러 그래프이다.

오일러 그래프에 대한 정리 1) 연결그래프 G=(V,E)의 모든 꼭짓점의 차수가 짝수이면 오일러 그래프를 만들 수 있다. 2) 연결그래프 G=(V,E)의 꼭짓점 중 차수가 홀수인 꼭짓점의 수가 0 또는 2개인경우는 오일러 경로를 만들 수 있다.

 

 

[역대기출문제]

docs.google.com/forms/d/e/1FAIpQLSe6aAYizQWUXD30zyQ0skt2Y3ky4aM187PtkjAv8qycEFy-sA/viewform

19-1. 그래프 관련 문제풀이(한붓그리기외)-초등부

docs.google.com/forms/d/e/1FAIpQLSeJC6ckGFsLPSInI_hQDVBpM3DDT595cS_nIsku6CgW5sp8dA/viewform

19-2. 그래프 관련 문제풀이(한붓그리기외)-초등부

docs.google.com/forms/d/e/1FAIpQLSfzC3rL959fE6wcjQb2Fr4vyBUmaE7uSIVF_cTQpXErFRNo9Q/viewform

19-3. 그래프 관련 문제풀이(한붓그리기외)-중고등부

docs.google.com/forms/d/e/1FAIpQLSczZwYTrXNFab0PZzgbBflBhrzveZN-Sc7bbf_-cyWQq28yWQ/viewform

19-4. 그래프 관련 문제풀이(한붓그리기외)-중고등부