Lecture 1: 컴퓨터 과학과 그래프 이론

Lecture 1: 컴퓨터 과학과 그래프 이론 ^∗

1.1 강의 개요와 목표

그래프 이론은 컴퓨터 과학의 가장 기본적이며 중요한 도구이다. 그래프 이론은 문제의 모형만들기와 그 해결에 사용되고 있다. 강의의 목표는 2가지인데 하나는 그래프 이론 자체에 대한 이해로서 수학적인 접근을 해야 한다. 그 다음에는 실제 현실적인 문제를 그래프로 모형화하고 이것을 해결하는 그래프 알고리즘을 개발하는 것이다. 실제 이 그래프 알고리즘을 우리는 프로그래밍 언어로 구현해볼 예정인데 제시될 과제는 Boost를 이용하여 구성해야 한다. 그리고 요즘 많이 주목을 받고 있는 Social Network에 관련된 이론 중 그래프와 관련된 내용을 강의 말미에 몇 가지 선택해서 다루어 볼 예정이다.

그래프 알고리즘은 대부분 NP-complete인데 이번 강의에는 그래프 문제를 위한 다양한 heuristics algorithm을 살펴볼 예정이다.

1. 강사 : 조 환규, hgcho@pusan.ac.kr

2. 강의록은 강의가 있는 전 주에 강의 홈페이지로 배부됨.

3. URL http://topaz.cs.pusan.ac.kr/~graph2019

4. Text: Introduction to Graph Theory by Douglas West (2nd edition) 2010 (pdf 판이 있음.)

5. Text: Introduction to Graph Theory by Robin J. Wilson (4th edition) 1996 (pdf판이 있음.)

6. SubText : Networks, An Introduction, 2011, M.E.J Newman, Oxford Press (a) Empirical Study of Networks

(b) Fundamentals of Network Theory

(c) Math. of networks, Measures and metrics (d) The Large Scale Structure of Networks (e) Network Models

∗2013년 강의록을 fancyhdr 형식으로 전면 개정함. 2011년 이후 Social Network Theory를 추가하고 Random Graph Chapter를 추가함. 2015년에는 graph programming 과제를 충분히 넣어 실제 그래프 프로그래밍을 강조하기로함. max-flow를 앞 당겨 강의하기로함. 2017년에는 Social Network을 보강함.

2019년에서 그래프 알고리즘 최신 동향 추가할 예정

1

1.1 강의 개요와 목표

2

(f) Processes on Networks

7. SubText : Introducing Social Networks, 1999 SAGE Publication (a) Social Relationships and Network

(b) Personal Networks and Local Circles (c) Equivalence and Cohesion

(d) Power and Centrality (e) Dynamics

8. SubText : Graph Theory (pdf book is available), written by Diestel, Springer- Verlag

(a) Basics (b) Matching (c) Connectivity (d) Planar Graph (e) Coloring

(f) Flows

(g) Substructure and Dense Graph (h) Sparse Graph

(i) Ramsey Theory (j) Hamilton Cycles (k) Random Graphs

(l) Minors, Trees, and WQO(Well-Quasi Ordering)

9. SubText : Algorithmic Graph Theory and perfect Graph, Academic Press (아 주 중요한 책)

(a) Perfect graph (b) Triangulated graph (c) Comparability graph (d) Split graph

1.1 강의 개요와 목표

3

(e) Permutation graph, interval graph

그래프 이론의 강의는 크게 3가지이다. 하나는 그래프 이론 자체를 연구하는 것, 다른 하는 이미 연구된 그래프 이론의 결과를 활용하여 응용하는 것, 그리고 실제 도구를 이용하여 그래프 문제를 풀어보는 일이 있다.

이번 강의의 목적은 컴퓨터 과학 (공학) 에서 흔히 볼 수 있는 여러 계산문제를 그 래프에 기반하여 모델링하고, 이를 바탕으로 이미 개발된 그래프 알고리즘을 활용하여 해결하는 것이다. 따라서 강의는 그래프 이론을 어떻게 응용하는 가를 다루는 것이지 그래프 이론 그 자체를 탐구하지는 않는다. 수강생들의 각자 자신의 분야에서 그래프 이론을 활용하여 해결할 문제에 최대한 집중해야 한다.

강의순서는 다음과 같다. 먼저 그래프 이론의 일반적인 내용에 대해서 약 8-9 주간에 걸쳐서 설명을 한다. 이것은 첫번째 교재 (Prentice Hall) 를 이용해서 진행된다. 학생들 은 이 과정에서 교재에 제시된 문제중에서 선택된 문제를 빠짐없이 풀어야 할 것이다. 그 도중에 앞서 말한 SIAM 교재를 이용하여 개별적인 application를 선택하여 (학생들이 흥미를 가질 수 있는 몇가지 문제) 설명한다. 이 후 시간이 되면 최근에 소개된 그래프 이론의 최신경향과 관련 논문들에 대해서 살펴본다.

그리고 그래프 알고리즘을 실제 프로그래밍 언어를 이용해서 구현해보는 일은 LEDA나 Stanford GRAPHBASE를 이용하면 된다. 스탠포드 그래프 베이스는 그래프 이론에 관한 각종 subfunction을 KNUTH가 구현한 것으로 매우 유용하다. 책으로도 나와 있으며, 수강생은 아래 사이트를 참조하여 관련 material을 받아서 자신이 프로그램 하기 좋은 환경에 설치하여 구동시킬 수 있다. 아래를 참조하시오.

http://www.cs.sunysb.edu/~algorith/implement/graphbase/implement.shtml 그리고 또 다른 알고리즘 resource가 있는데 SUNY(State University of NYork)에서 운영하고 있는 SUNY algorithm repository 알고리즘 모음집 (repository) 을 활용할 수 있다. 위치는 http://www.cs.sunysb.edu/~algorith/ 이며 세부내용은 다음과 같다. 두개의 내용이 있는데 하나는 polynomial graph algorithm이며 다른 하나는 hard graph algorithm(주로 class NP인 류의 문제) 가 있다.

이번 2017년도 학기에는 Boost package를 이용해서 모든 그래프 문제를 해결한다.

따라서 수강생들은 기본적인 Boost, STL에 관하여 잘 숙지하고 있어야 한다. 프로그래 밍 과제는 매주 한 개씩 제시될 예정이다.

1. Connected Components 2. Topological Sorting 3. Minimum Spanning Tree 4. Shortest Path

1.1 강의 개요와 목표

4

5. Transitive Closure and Reduction 6. Matching

7. Eulerian Cycle and Chinese Postman 8. Edge and Vertex Connectivity 9. Network Flow

10. Drawing Graphs Nicely 11. Drawing Trees

12. Planarity Detection and Embedding

그리고 주로 NP-Complete 류의 문제들에 대한 알고리즘도 이미 이곳에 상당한 수준으로 구현되어 있다. 따라서 NP-complete에 관란 각종 알고리즘은 이 쪽에 있는 library code를 이용해서 풀어야 한다. 그 안에 들어 있는 NP-complete관련 프로그램은 다음과 같다.

1. Clique

2. Independent Set 3. Vertex Cover 4. Traveling Salesman 5. Hamiltonian Cycle 6. Graph Partition 7. Vertex Coloring 8. Edge Coloring 9. Graph Isomorphism 10. Steiner Tree

11. Feedback Edge and Vertex

문제 1.1.1 SUNY에서 제공하는 코드나 LEDA, Boost를 사용하는 것과 직접 구현하는 일을 비교 평가하시오. □

1.2 Drawing Tool : GraphViz과 NetworkX

5

수강생들은 자신이 처음부터 모든 것을 설계, 구현하는 식으로 코드를 작성하려고 생각하지말고 알고리즘의 기본적인 원리를 습득한 뒤에 이들 이미 개발된 알고리즘를 활용하여 보다 높은 차원의 문제를 해결하면 실제 현장에서 효율적이다. 중간고사와 기말고사는 따로 실시할 예정이며 문제는 주로 교재에 있는 문제로 출제된다. 그리고 Quiz는 매 시간마다 강의가 끝난 후에 주어지고 수강생들은 이 문제를 한 시간내에 풀어서 제출해야 한다. 이후 이 문제는 채점후에 돌려준다. 그 다음 시간에는 가장 좋은 답안을 작성한 사람이 나와서 풀이를 한다. 이 과정에서 약간의 질문과 토론이 있을 것이다. 관련 handout은 ALDE¹ Lab의 pearl이나 다른 적당한 site통해서 Postscript file의 형식으로 게시되므로 수강생들은 강의가 있는 날 12시 경에 그 Postscript 화일을 출력해서 준비해야 한다. 강의에 참석하지 못할 경우에는 메일을 통하여 강사에게 미리 알려야 한다. 모든 과제와 프로그램은 향후 게시될 Web을 통하여 배부되고 이를 통하여 과제를 제출해야한다.

이번 강의에서 사용될 표준 그래프 입력형식의 정의가 필요하다. 이것을 위해서 어떤 형식이 필요한지 토론해보기로 하자. 그 형식은 먼저 Self-documentary 기능이 있어야하고, 가능하다면 self-error checking 기능이 있으면 좋다. 그리고 어디까지 의 그래프 형식을 지원할 수 있는지를 먼저 정의해야 한다.

문제 1.1.2 먼저 K₄를 자신이 만든 형식으로 정의해보시요. 각 edge의 weight는 정수 1 로 한다. 만일 directed graph라면 어떻게 표현할 것인가를 생각해보자. 또는 geometric graph(Plane graph) 라면 어떻게 표현할 것인지 생각해보자.

1.2 Drawing Tool : GraphViz과 NetworkX

그래프 그리기 (Graph Drawing) 은 매우 번잡스러운 일이다. 특히 노드의 수가 15여개를 넘을 경우 이를 사람이 인식하기 쉽도록 그리는 것은 상당히 어렵다. 먼저 가장 간단한 문제를 풀어보자.

문제 1.2.1 3개의 노드로 구성된 서로 다른 그래프를 모두 그려보시오. 그래프의 종류는 unlabeled graph, labeled graph, directed graph, undirected graph에 따른 4종류이다.

(단 isomorphics한 것은 같은 것으로 취급한다. ) □

문제 1.2.2 Hyper Graph란 무엇인지 설명하고 어떤 모델을 설명하는게 좋은지 한 예를 제시해 보시요. □

12015년 이전 GALAB에서 Algorithm and Data Engineering Lab. 으로 개명하였음

1.2 Drawing Tool : GraphViz과 NetworkX

6

문제 1.2.3 어떤 그래프를 평면에 그린 두 개의 graph layout L₁과 L₂가 있다고 하자. 이 둘 중에서 어떤 것이 더 ” 좋은 것” 인지 그 기준을 설정하고, 왜 그 기준을 선택하였는지 설명하시오. □

현재 알려져 있는 그래프 그리기 도구는 매우 많으며 어떤 것은 상용으로 판매되기도 한다. 무료로 쓸 수 있는 것 중에서 가장 보편적인 것으로 GraphViz가 있다. 이 도구는 다소 사용자 인터페이스가 허접하기는 하지만 튼튼하며 유연하여 사용하기에 적절하다.

또한 다양한 제한조건의 그림을 그리는데에도 적절하여 실제 그래프 관련 논문을 쓸 때 활용하면 아주 좋다. 이 프로그램을 구할 수 있는 위치는 http://www.graphviz.org/

에 있다.

GraphViz은 어떤 그래프 형식을 입력으로 받아서 그에 해당되는 그래프를 그려준다.

이를 위해서 ASCII화일인 *.dot 파일을 준비해야 한다. 예를 들면 다음과 같다. 그리고 dot 프로그램으로 ps(postscript 화일) 를 만들어 내야 한다. 이 명령은 shell 상태에서 dot 프로그램을 사용해서 만들 수 있다.

dot -Tps sample.dot -o sample.ps

graph G { digraph G {

run -- intr; main -> parse -> execute ; intr -- runbl; main -> init ;

runbl -- run; main -> cleanup ; run -- kernel; execute -> make_string kernel -- zombie; execute -> printf ; kernel -- sleep; init -> make_string ; kernel -- runmem; main -> printf ; sleep -- swap; execute -> compare ; swap -- runswap; }

runswap -- new;

runswap -- runmem;

new -- runmem;

sleep -- runmem;

}

이렇게 만들어진 ps 화일을 해당 문서에 집어 넣으면 그림을 포함시킬 수 있다. 단 일반적인 tex 화일에서 raw ps화일을 집어 넣기는 힘들기 때문에 (과정이 복잡) 다음과 같디 Encapsulated PS 화일을 PostScript (주로 GhostScript를 사용) 로 변화해야 한다.

이 프로그램으로 그려진 그림을 다른 도구를 이용해서 사용자가 editing할 수 도 있다.

예를 들어 dotty, lefty, neato 등을 이용해서 그림을 게선할 수 있다. 이 사이트의 갤러리 코너에 들어가면 다양한 예가 있다. 이 예를 사용하면 보다 쉽게 이해할 수 있다.

1.2 Drawing Tool : GraphViz과 NetworkX

7

run

intr kernel

runbl zombie sleep

runmem swap

runswap

new

Figure 1: 왼쪽 simple graph

과제물 1.2.1

[GraphViz]

Python 을 이용하면 보다 쉽게 그래프를 그릴 수 있다. 사용할 경우에는 미리 Graphviz를 설치해서 다음과 같이 사용하면 된다.

1 import graphviz as gv

3 g1 = gv. Graph ( format ='jpg ') g1.node('Apple ')

1.3 Boost Package와 그래프 알고리즘

8

main

parse

init

cleanup

printf execute

make_string compare

Figure 2: 오른쪽 directed graph

5 g1.node('Book ') g1.node('Coke ') 7 g1.node('Dish ')

g1.edge('Apple ', 'Book ') 9 g1.edge('Apple ', 'Dish ') g1.edge('Apple ', 'Coke ') 11 g1.edge('Coke ', 'Dish ')

print (g1. source ) 13 g1.view ()

1.3 Boost Package와 그래프 알고리즘

모든 자료는 http://www.boost.org/에서 구할 수 있다. Boost는 기초 자료구조부터 그래프 알고리즘까지 제공하고 있다.

1.4 Combinatorica와 LEDA

Mathematica의 application으로 Skiena가 만든 Combinatorica가 있다. 아마도 인간이 만든 인공물 중에서 가장 위대한 것을 꼽으라면 강사는 TEXSystem과 Mathematica 를 꼽겠다. Combinatorica 이용하면 대부분의 그래프 계산은 바로 할 수 있다. Clique Finding등 중요한 함수는 모두 구성되어 있다. 단 한가지 문제라고 한다면 그래프 사 이즈가 큰 경우에 exponential time algorithm을 수행하면 시간이 아주 많이 소용된다.

하지만 그래프 layout이 모두 가능하므로 간단한 그래프 계산은 쉽게 할 수 있는 편리한 점이 있다.

주의해야 할 것은 Mathematica에 들어가서 처음에 Combinatorica package을 불 러야 한다. 해당 package를 부를 경우에는 반드시 back quotation mark를 이용해야

1.5 프로그래밍 실습 준비

9

한다. 간단한 manual에 강의 게시판에 있으니 한번 사용해보기 바란다.

계산량이 많은 작업을 할 경우에는 LEDA를 사용하는 것이 좋으나 빠르게 특성을 실험적으로 규명하고자 할 경우에는 Combinatorica를 사용하면 빠르게 점검할 수 있다.

LEDA의 가장 큰 특징은 알려진 알고리즘 중에서 최신 (거의) 의 알고리즘과 자료구조를 이용해서 매우 robust하게 구현이 되어 있다는 것이다. 따라서 실제 공학의 문제에 있어서 이미 안전성이 증명된 LEDA를 사용하지 않는다는 것은 그 알고리즘의 정답의 정확성에도 의심을 받게 된다.

특히 큰 수치 데이터, 각종 특수한 경우(degenerated case)까지를 모두 고려한 LEDA implemetation은 어떤 공학적 프로그래밍에서 아주 유용한 결과를 보장해주는 최고의 도구이다.

LEDA의 구조는 Built-in 자료구조, Built-in 알고리즘, 그리고 Window Interface 로 구성되어 있다. 단 sample로 주는 Window Interface는 LEDA의 성능을 그야말로 간단히 demo를 보이는 정도의 내용이므로 실제 massive한 data를 사용할 경우에는 Built-in 자료구조를 이용해서 직접 작성해야한다.

1.5 프로그래밍 실습 준비

문제 1.5.1 (Boost 실습문제) Boost 프로그래밍은 Boost(pdf로 자료실에 올라와 있 음) manual을 참조하면 된다. 아래 “가오리” 그래프를 Boost로 구성하시오. 그리고 사용자의 입력을 받아서 인접한 vertex와 인접한 edge를 출력하는 프로그램을 작성하시 어. interaction은 다음과 같다. 단 그래프를 visualize할 필요는 없다.

Boost> input : v 1

Boost> N(1) = { 2,3,4,5 } Boost> input : e 5 6

Boost> N((5,6)) = { (1,5), (3,5) } Boost> input : e 1 6

Boost> Edge (1,6) does not exist Boost> input : v 6

Boost> N(6) = { 5 } Boost> quit

1.6 균형 그래프 (Balanced Graph) 과 응용

어떤 사회든 인간관계는 서로 호감을 가지는 좋은 관계 (+), 또는 나쁜 관계 (−), 그리고 아무런 관심이 없는 (indifference) 관계 (Null) 로 구분된다. 그런데 이런 어떤 공통의

1.6 균형 그래프 (Balanced Graph) 과 응용

10

1

2

3 4

5 6

Figure 3: 가오리 그래프를 Boost로 구현하고 인접 edge, vertex를 출력해보기

목적을 가진 팀에서 관계에 따라서 내부의 균형이 잘 잡히는 경우와 아닌 경우로 나뉘게 된다.

문제 1.6.1 어떤 회사에서 연구원을 2개 이하의 팀으로 편성하고자 한다. 아래 그림에서 John, Jack, Jillda의 경우 팀 내 화합이 잘 되는지를 그래프 이론적으로 설명하고 그 아래 4개의 그래프G_a, G_b, Gc, G_d의 경우 Social Balance가 성립하는지 판별하시오. □

John John John

Jack Jack Jack

Jillda Jillda

+

+ - + +

-

-

+ +

+ +

− −

− − −

−

− −

−

+ +

+ + + +

+

+

Ga Gb Gc Gd

A B

C D

Figure 4: 사회적 관계가 균형이 가능한지를 따져볼 Social balance graph의 예. 단 팀은 2개 이하.

1.6 균형 그래프 (Balanced Graph) 과 응용

11

어떤 사회이든지 각자 독립적으로 작업하게 하면, 즉 팀의 수를 |G| 와 같게하면 균형을 잡을 수 있다. 만일 하나의 - edge가 있으면 한 팀으로는 불가능하다. 우리는 k 이하의 팀으로 균형을 잡을 수 있는지 따져보고자 한다.

문제 1.6.2 아래 signed graph에서 2개 이하의 팀으로 Social Balance가 맞는지를 판별 해보고, 만일 아닌 경우 어떻게 이 문제를 대처하면 되는지 그 해결책을 그래프 이론적 으로 제시해 보시오. 아래 그림에서 Jack과 Mary 사이에는 아무런 호오관계가 없다. □

John

Jack

Mary

Jillda

+

− − +

+

Figure 5: 4 명의 팀원으로 구성된 관계가 안정적인지를 판별하시오.

문제 1.6.3 다음 부호 그래프 (signed graph) 가 balanced graph인지를 밝히고, 만일 아닐 경우에는 최소 갯수의− edge를 +로 바꾸어서 전체를 balanced 되게 하려고 한다. 그 때 필요한 부호를 바꾸어야할 edge의 최소 갯수를 구하는 방법을 제시하시오.

문제 1.6.4 부호 그래프 (signed graph) 에서 단순한 부호만 아니라 weight까지 같이 고려할 수 있다면 이 문제를 어떻게 발전시킬 수 있는지 설명해 보시오.

문제 1.6.5 이 문제는 대화에서 서로 존댓말로 대화하는 경우 (a ↔ b), 서로 반말로 하는 경우 (a↭ b), 한쪽은 존댓말, 다른 한쪽에서는 하대를 하는 경우, a가 b에게는 존대를 하고 b는 a에게 하대를 하는 경우 (a→ b)가 있다. balanced graph를 이용해서

1.6 균형 그래프 (Balanced Graph) 과 응용

12

+ +

+

+

+ +

+ +

+

−

−

− +

−

−

− +

+ +

+ +

+ −

+

−

−

+

− +

−

+

+

− a

b

c

d

e

f

g h

k l

m n

1 2

3 4

5

6 7

8 9

11 10

Figure 6: 두 개의 그래프를 k = 2 이하의 그룹을 가진 균형그래프인지 판별하시오.

이 문제를 formulation 해보고 사람들이 이런 관계에 있을 때 언제 ” 어색 (awkward)”

한지를 판별하는 그래프 알고리즘을 제시하시오. 다음 그림에서 어떤 모임이 어색한지 아닌지를 판별하시오.

1.7 Compatibility Graph의 응용

13

a

b c

d

e f

g

a b

c

d f e

g

Figure 7: 다음 모임에서 어색한 대화가 생기는 경우를 찾으시오. 화살표는 반말, 무방향 edge는 상호 존대말.

1.7 Compatibility Graph의 응용

다음은 어떤 3각 교차로의 상황을 나타낸 그림이다. 이교차에서 우리가 관찰하는 것은 6개의 주행선이다. 이 교차로는 각 주행선마다 방향이 지정되어 있어 만일 오른쪽에 서 들어와 아래쪽 방향으로 가려고 한다면 반드시 b 주행선에 들어와서 준비를 해야 한다.

a b

d c

e f

Figure 8: 진입 방향이 3개인 교차로에 준비된 6개 { a, b, c, d, e, f, } 주행선

1.7 Compatibility Graph의 응용

14

문제 1.7.1 그 상황에서 어떤 2개의 주행성이 동시에 진행될 수 있으면 이 두 주행선은 서로 compatible 하다라고 이야기한다. 6 개의 주행선을 node로 하는 Compatibility Graph를 구성해 보시오. 그리고 우리는 1분 주기로 신호등을 조작해서 소통을 원할하게 하려고 한다. 그 원할의 정도는 각 lane에서 자기 신호를 위하여 기다리는 시간 (waiting time) 의 합으로 표시될 수 있다.

이 때 가장 무식한 방법은 6개의 lane마다 각 10초씩 자기 시간을 배당하는 것인데 이렇게 되면 모든 lane은 최대 50초 (seconds) 씩 기다려야 한다. 이것을 개선하는 방법을 그래프 이론적으로 제시하시오.

문제 1.7.2 Combinatorica를 보면 random graph가 있다. 즉 Random Graph에는 임의 의 edge가 만들어질 확률이 p라고 한다면 대략 O(p·n²/2)개의 edge가 임의로 만들어지는 그래프이다. 우리는 Random(p) Graph가 연결될 확률을 simulation으로 구하고자 한다.

이것을 random graph 만개를 만들어서 수행하는데 그때마다 연결확률 p 를 조정해서 구해보아라. 그리고 어떤 값에서 critical 하게 변하는지 그 값을 추적해보시오. □

문제 1.7.3 다음 4개의 그림은 어떤 철골구조를 보여주고 있다. 철골구조의 각 교차점 (crossing points) 에는 단 하나의 볼트만 설치되어 있다. 따라서 단위 rectangle은 외부 압력에 마음대로 움직인다. 그러나 그 대각선 지지대를 설치하면 튼튼하게 버틸 수 있다.

우리의 가정은 각 단위 철골은 늘어나거나 줄어들 수 없다는 가정을 한다. 즉 이중에서 RIGID(튼튼) 한 것과 그렇지 않은 것을 구별하고, 튼튼하지 않을 경우 그 변형된 모습을 그려보시오. □

1.7 Compatibility Graph의 응용

15

(a) (b)

(c) (d)

문제 1.7.4 이 문제를 그래프 이론으로 모델링하고, 앞서 말한 문제에서 말한 rigidity 의 특성을 이론적으로 제시하시오. □

그래프 이론으로 모델링을 한다는 것은 주어진 문제를 그래프로 바꾸고, 해당 문제의 답이 그래프에서 어떤 특성 (subgraph) 을 찾는 문제로 귀납되는지를 결정하는 것이다.

가장 기본적인 해당 문제의 어떤 개체를 vertex, edge로 mapping 해야하는지를 결정하는 것이다.

문제 1.7.5 다음에 제시된 구조 (a), (b), (c) 와 (d) 중에서 각각의 철골 구조가 rigid 한 지를 구별해내고 그 경우, 즉 rigid하다면, 제시된 cross bar의 갯수 최소로 필요한 갯수인지를 밝히시오. □

문제 1.7.6

Research Problem on 3d mesh rigidity

문제 1.7.7 다음에 제시된 두 그래프 G_a와 G_b가 같은 (isomorphic) 그래프인지 다른 그래프인지 판단하여 그 답과 그 근거와 함께 제시하시오. □

1.8 그래프 이론의 다양한 응용

16

(a) (b)

(c) (d)

G

G

문제 1.7.8 무용이나 피겨 스케이팅의 동작을 보면 여러 기본동작으로 구분되고 각 기본동작 사이에는 서로 연결이 가능한지의 여부로 연결성을 edge로 정의할 수 있다. 이 무용 그래프, 피켜 스케이팅 그래프를 이용해서 동작을 기록하고 분석하는 일을 그래프 이론적으로 한다면 어떤 특성을 규명해 볼 수 있는지 말해보시오. ² □

1.8 그래프 이론의 다양한 응용

고고학 연구자들이 어떤 장소에서 발굴한 유물들이 있다. 예를 들어 한 무덤역에서 발견된 유뮬이 G_i= {1,2,3,4} 라고 하자. 한 곳에서 발견된 유물은 특정 기간 동안 사용된 유물이라고 할 수 있다. 또 다른 무덤에서 발견된 유물이 G_j= { 2, 9, 6, 10}

22015년 강의 중에 나온 아이디어를 추가

1.8 그래프 이론의 다양한 응용

17

이라고 하면 이 둘은 2라는 유물은 공유하기 때문에 이 두 무덤은 시점은 겹친다고 볼 수 있다.

1. b = 단위 구역내에 박테리아의 정도 2. c = 도시로 유입되는 사람의 수 3. d = 발샹한 질병의 수

4. m = 현대화 (modernization) 의 정도 5. p = 도시 거주 인구의 수

6. s = 위생 시설의 정비, 설치 정도 7. w = 도시에서 베출되는 쓰레기의 양

+

+

+

+ +

+

+

−

−

−

c p

w

b

d

s

m

Figure 9: 쓰레기 처리에 관한 feedback cycle

음악에도 그래프 활용된다. 서양음악의 화성법은 다양한 화음 (Key) 의 진행에 관한 학문이다. 화성 중 가장 잘 알려진 것은 장조 (major) 와 단조 (minor) 가 있다. C장조는 도 (do) 에서 시작하여 온음인 레 (re), 미 (mi), 그리고 여기에 반음인 파 (fa) 이렇게 쌓아 올려진 음계이다. 같은 방식으로 F장조는 F부터 시작해서 옴음, 온음, 반음, 온음...

쌓아 올려진 음계이다. 그런데 C장조와 F 장조는 f, g, a, (b, b♭), c가 동일하여 주 음계는 매우 자연스럽게 어울린다. 이렇게 C장조와 어울리는 조는 G장조이다. 따라서 C장조의 기본 화성은 C, F, G로 구성되어 있고 이렇게 서로 어울리는 (with common tones) 조들끼리 edge를 주어서 그래프로 만들면 아래 그림이 된다.

1.8 그래프 이론의 다양한 응용

18

C C♯

D

D♯ = E♭

E

F F ♯ = G♭

G G♯ = A♭

A A♯ = B♭

B

Figure 10: Major Graph with dominant and subdominant key

C

F G

D a

B

= A

d

g

e

b

Figure 11: 24-Harmonic Circle