차례

차례...................................... 1

1 GRAPHS AND SUBGRAPHS . . . . . . . . . . . . . . . . . . . . . 2

1.1 Graphs and simple Graphs . . . . . . . . . . . . . . . . . . . . 2

1.2 GraphIsomorphism........................ 2

1.3 The Incidence and Adjacency Matrices . . . . . . . . . . . . . 5

1.4 Subgraphs ............................. 6

1.5 VertexDegrees........................... 6

1.6 Paths and Connection . . . . . . . . . . . . . . . . . . . . . . 9

1.7 Cycles ............................... 11

1.8 The Shortest Path Problem . . . . . . . . . . . . . . . . . . . 11

1.9 Sperner’sLemma.......................... 13

2 Tree.................................... 15

2.1 Trees ................................ 15

2.2 Cut Edges and Bonds . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 CutVertexes............................ 19

2.4 Cayley’sFormula ......................... 20

2.5 THE CONNECfOR PROBLEM . . . . . . . . . . . . . . . . . 21

3 Connectivity ............................... 22

3.1 Connectivity............................ 22

3.2 BLOCKS.............................. 23

4 Euler Tours and Hamilton Cycles . . . . . . . . . . . . . . . . . . . 24

4.1 EulerTours ............................ 24

4.2 HAMILTONCYCLES ...................... 24

5 Matchings ................................ 25

5.1 Matchings ............................. 25

1 GRAPHS AND SUBGRAPHS

1.1 Graphs and simple Graphs

정의1.1 (Graph) 정점과정점을 잇는간선들로이루어진것을그래프라한다.

•V(G) : 정점의집합

•E(G) : 간선의집합

•ψG(en) : 각 간선(en)의정점의쌍

•ν(G) : 정점의갯수

•ε(G) : 간선의갯수

그래프를간선들이교차하지않게그릴수있는것을plannar graph라한다.

plannar graph가아닌것을nonplanar graph라한다.

정점이한개인그래프를trivial graph라고한다.이외의모든그래프는non-

trivial 그래프이다.

loop : 끝이동일한간선. link : 끝이다른간선.

Simple graph : loop가없고두정점쌍에두개이상의간선이존재하지않는

그래프

incident : 한간선에 양 정점 근접adjacent : 두간선에공통된정점 인접

1.2 Graph Isomorphism

정의1.2 (isomophic) 두그래프G와H가전단사함수θ:V(G)−→ V(H)와

ϕ:E(G)→E(H)이성립하면두그래프는동형(isomophic)이다.또한다음이

성립한다.

•ψ(e) = us(e∈E(G), u, s ∈V(G))

•ψ(ϕ(e)) = θ(u)θ(v)

정의1.3 (a special classes of graphs) 특징에따른그래프이름

•complete graph(완전그래프) : 모든정점에간선이연결된그래프정점의

개수가n일때Kn로표현한다.

•empty graph : 정점이한개고 간선이없는그래프

•bipartite graph(이분그래프) : 정점이두집합으로이루어져집합내에는

연결된간선이없는그래프

•complete bipartite graph(완전이분그래프) : 한집합의모든정점이각각

반대집합의모든정점에 연결된그래프두정점 집합의갯수가 각각 m과

n일때Km,n으로표현한다.

•(1.2.9)k-partite graph : 정점이적어도하나포함된k개의부분 집합으로

이루어진그래프이다한부분집합내에 연결된간선은존재하지않고다

른부분집합의정점에만간선이존재할수있다. (원문)a complete k-partite

graph is one that is simple and in which each vertex is joined to every

vertex that is not in the same subset

•(1.2.9)complete k-partite graph : k-partite graph의각정점이포함된부

분집합을제외한모든정점에간선이연결된그래프

(원문)complete k-partite graph is one that is simple and in which each

vertex is joined to every vertex that is not in the same subset.

•(1.2.10)k -cube : 각정점은하나의ordered k-tuple(k-비트이진수)이고,

두정점이1비트만서로다를때두정점간에 에지가있다.

•(1.2.11)여그래프(complement graph) : 모든정점에대해서포함하고있

는존재하는간선은제거,존재하지않는간선을생성해서만든그래프Gc

로표현한다.

•(1.2.11)자기여그래프(self-complementary graph) : 여그래프와자기자

신이동형인그래프

week1

1.2.1

1.2.2

1.2.3

1.2.4

1.2.5

G∼

=H, simple

bijection θ:V(G)−→ V(H)uv ∈E(G)⇔θ(u)θ(v)∈E(H)

정의로부터ψ(e) = us인간선e(e∈E(G))에대해대응되는ψ(ϕ(e)) =

θ(u)θ(v)인ϕ(e)(ϕ(e)∈E(H))가존재함을알수있다.따라서uv ∈E(G)→

θ(u)θ(v)∈E(H)성립,반대의경우도마찬가지로성립한다.

1.2.6

1.2.7

1.2.8

1.2.9

n

2−(m(k+ 1) −n)k

2−(n−mk)k+ 1

2(1)

=n

2−m(k+ 1)k

2−nk

2−(n−mk)k+ 1

2(2)

=n

2−m(k−1)k+ 1

2+nk

2−(n−mk)k+ 1

2(3)

=n

2+nk

2−(n−m)k+ 1

2(4)

=n

2+nk

2−(n−m)k+ 1

2+ (n−1)k+ 1

2−(n−1)k+ 1

2

(5)

=n

2+nk

2−(n−1)k+ 1

2+ (m−1)k+ 1

2(6)

=n2−n−nk +k2+k−nk

2+ (m−1)k+ 1

2(7)

=(n−k)(n−k−1)

2=n−k

2+ (m−1)k+ 1

2(8)

1.2.10

1.2.11

(a):

•Kc

n:간선이없는그래프이다.

•Kc

n,m :두집합사이의 간선이없이두집합이각각 완전그래프인subgraph

를이루고있다.

(b): 자기여그래프가되기위해선일단동형이전에간선의갯수가동일해야하

는데여기서총생길수있는간선의갯수는v(v−1)

2가최댓값이자 그래프의간

선수+여그래프의간선수입니다.그래프의간선수=여그래프의간선수이므

로v나v−1은적어도둘중하나는(적어도지만사실둘다4의배수인경우의

수는존재하지않습니다) 4의배수여야합니다 따라서v(mod 4)는0또는1

•추가문제:

인접성:두그래프가인접성을보존할때,u와v가인접하면θ(u)와θ(v)가

인접하고그역도성립한다.

두그래프G와H에대해서G의정점들을H의정점들에일대일로대응하

면서인접성을보존하는함수f가존재하면두그래프G와H는동형(iso-

morphic)이다.

Proof: E(G)의 임의의 간선e에대해임의의 정점 u, v가인접할때,인접

성이보존되므로θ(u)와θ(v)또한인접한다.θ(u)와θ(v)를잇는간선을

e′이라할때ϕ(e) = e′인ϕ:E(G)−→ E(H)를정의할수있다.따라서

정의에의해G와H는동형이다.

week2

1.3 The Incidence and Adjacency Matrices

(대충그래프를나타내는표현에대한내용)

1.4 Subgraphs

정의1.4 (subgraph) 그래프H,G가V(H)⊂V(G), E(H)⊂E(G), and ψH

is restricton ψG

a일때H⊆G라쓰고H(G)를subgraph(supergraph)라한다.

•H⊆G,H=G이면H⊂G라표기하고,H를G의proper graph라한다.

•V(H) = V(G), H ⊆G이면H(G)를spaning subgraph(supergraph)라한

다.

•spaning subgraph과동시에simple graph이면, undelying simple graph라

한다.

•그래프G가∀v∈V, d(v) = k이면,k-regular이다.완전그래프와 완전이분

그래프(complete bipartite graphs Kn,n), k-cube는레귤러다.

aψH가제한적으로ψG이다.

1.5 Vertex Degrees

정의1.5 (degree(차수)) dG(v)는정점 v에 연결된간선의갯수를나타낸다.그

래프의정점의차수의최솟값을δ(G) , 최댓값을∆(G)로표기한다.

v∈V

d(v)=2ε

k-regular graph(정규그래프) : d(v) = k∀v∈V|A|:집합A의원소의갯수

Theorem 1.1.

v∈V

d(v)=2ε

Proof. 근접행렬M을생각해보자각열은정점으로이루어져있으므로행의합

은해당정점의차수이다.따라서모든행과열의합은X

v∈V

d(v)이며또한2ε이

다.예제1.3.1(a)에따라서각열의합이2이다.

Corollary 1.1.1. 어떤그래프의차수가홀수인정점의갯수는짝수이다.

Proof. 차수가홀수와짝수인V1,V2로정점을나누었을때,

v∈V1

d(v) + X

v∈V2

d(v) = X

v∈V

d(v)

는짝수이다.X

v∈V2

d(v)는짝수이므로X

v∈V1

d(v)또한짝수이다.그러므로|V1|은

짝수이다.

1.5.1

1.5.2

M’는M의전치행렬원표기MT,MM′[vi][vi] =

j=1

M[vi][ej]·M′[ej][vi]

M′[ej][vi] = M[vi][ej]이며simple graph일때각 값은0또는1이기때문에

결과적으로대각선의값은해당정점의차수가된다.

A행렬에서A[vi][vj] = A[vj][vi]

d(i) =

j=1

A[vi][vj] =

j=1

A[vj][vi]이다.마찬가지로simple graph에서A[vi][vj]

은무조건0또는1을가지므로A[vi][vj]·A[vj][vi] = A[vi][vj]이다.

A2에서A2[vi][vi] =

j=1

A[vi][vj]·A[vj][vi] =

j=1

A[vi][vj] = d(i)

1.5.3

k-regular bipartite graph의bipartition(X,Y)이|X| =|Y|라하자.d(v) = |Y|, d(u) =

|X|(v∈X, u ∈Y)d(v)=d(u)이는k-regular graph의조건에모순

1.5.4

두명이상의사람이 있는그룹에서그룹내친구의수(그룹내부의사람으로제

한)가 같은사람이반드시두명이 있음을 보여라

사람이n명일때친구의수는최대n-1명이기때문에비둘기집의원리에의해

친구수가 같은사람이무조건두명이존재한다.

각각의사람을정점,친구관계를간선으로나타낸다면은해당그룹은simple

graph로볼수있으며친구의수는각정점의차수가된다.

따라서해당문제는simple graph일때반드시두정점의차수가 같음을 보이

는것과 같다.

1.5.5

만약G가정점 v1, v2, ..., vn을가질때(d(v1), d(v2), ..., d(vn)) 을그래프G의차

수 수열(degrees sequence)라부른다.

음이 아닌정수들의시퀀스(d1, d2, ..., dn)가어떤그래프의차수 시퀀스임이

i=1

di가짝수임과필요충분조건임을 보여라.

그래프의차수의합은2ε임이 T heorem1.1에이미증명되어있다.따라서차

수 수열의합은짝수이며반대의경우도성립한다.

If G has vertices (v1, v2, ..., vn) the sequence (d(vl), d(v2), ..., d(vn)) is called

a degree sequence of G. Show that a sequence (d1, d2, ..., dn) of non-negative

integers is a degree sequence of some n graph if and only if

i=1

diis even

1.5.6

A sequence d= (d1, d2, ..., dn) is graphic if there is a simple graph with degree

sequence d. Show that

(a) (7,6,5,4,3,3,2) : 정점이총7갠데첫번째정점의간선이7개인것은simple

graph의조건을충족하지못한다. (6,6,5,4,3,3,1) : 총7개의정점중자신을제외

한모든정점에간선을 잇는차수가6인정점이2개이지만차수가1인정점이

있으므로simple graph임이 모순이다.

(b) if dis graphic and d1≤d2≤... ≤dn, then

i=1

diis even and

i=l

di≤

k(k−1) +

i=k+1

min(k, di) for 1 ≤k≤n

그래프가심플그래프일때차수 수열이d1≤d2≤... ≤dn이면,

i=1

di짝

수인것과 다음이 성립함을보이시오

i=1

di≤k(k−1) +

i=k+1

min(k, di) for

1≤k≤n

d는차수수열이므로d의합은2ε이다.

1.5.7

1.5.8

1.5.9

1.5.10

The edge graph of a graph G is the graph with vertex set E(G) in which two

vertices are joined if and only if they are adjacent edges in G.

Show that, if G is simple (a) the edge graph of G has e(G) vertices and

L (d2 (V)) edges; vEVlG) . (b) the edge graph of Ks is isomorphic to the

complement of the graph featured in exercise 1.2.6.

그래프G의엣지그래프는꼭지점집합E (G)가있는그래프로두개의꼭지

점이G의 인접엣지인경우에만결합됩니다.

1.6 Paths and Connection

정의1.6 (walk) 순차적으로이어지는정점,간선의연결을walk라한다.

v0e1v1e2v2...ekvk인walk를v0to vk또는(v0,vk)-walk라한다.

•지나는간선을한번씩만쓴walk를trail이라한다.

•simple graph G의모든간선을지나는trail의길이는ε(W)이다.

•지나는정점을한번씩만쓴walk를path라한다

•그래프G가두정점 u,v의(u,v)-path가존재할때, connected graph라한

다.

•그래프의정점을쪼갠부분 그래프들이모두각각의연결된그래프일때,

부분 그래프들을그래프G의component라한다.

•그래프G의componet의수를ω(G)라쓴다.

1.6.1

(u,v)-walk사이에사이클이존재할경우겹치는정점을중복사용하지않는walk

를짤수있다따라서(u,v)-path가존재한다.

1.6.2

????

1.6.3

한정점을패스의시작정점으로잡았을때δ≤k이기때문에lenth가k인path를

만들기위해서로다른k개의연결된정점을선택해path를생성할수있다.

1.6.4

????

1.6.5

(a) : 최대한적은정점에많은간선을사용한그래프를세팅하기위해,정점 하나

를제외한ε−1개의정점으로ε−1

2개의엣지를사용한완전그래프를 만들

면완전그래프내의정점들로는더이상간선을연결할수없기때문에조건의

그래프는무조건connected가된다.

(b) : 정점 하나를제외한ε−1개의정점으로ε−1

2개의엣지를사용해

완전그래프를 만들면정점하나는연결되어있지않으므로disconnected그래프

이다.

1.6.6

1.6.7

1.6.8

(a)간선e가빠짐으로서하나였던component가두개의component가될요지가

있다.따라서ω(G)≤ω(G−e)≤ω(G)+1가성립한다.

(b) inequality: 부등식반례:V(G) = v1, v2, v3, E(G) = e1, e2, ψH(e1) =

v1v1, ψH(e2) = v2v3v1과v2v3가 각각 연결되어있는ω(G) = 2인그래프이다v1

을제거할때component가하나사라지므로주어진부등식을만족하지못한다.

1.6.9

1.6.10

1.6.11

1.6.12

1.6.13

1.6.14

uv, uw, uw ∈E이면G는complete가되기때문에uw /∈E

1.7 Cycles

정의1.7 (cycle) walk가양의길이이고시작점과끝점이같을때닫혀있다

(closed)고한다.

닫힌트레일을 cycle이라고한다.

Theorem 1.2. 그래프가이분그래프인것과 홀수개의사이클을가지지 않는것은

필요충분조건이다.

Proof.

1.7.1

1.7.2

simple graph가아닌경우루프를포함하는경우v0v0는정의에의해사이클이다.

임의의 정점v0, v1에간선이2개이상인경우v0v1v0사이클을 이룬다

simple graph인경우정점의개수가k인그래프를생각하자.이때v0v1v2...vi

인서로다른정점만최대한이어진연결을생각해볼때v0과vi의차수는명제의

조건에의해서무조건0≤j≤k인정점 vj에 연결이되어있어야한다.따라서

vjvj+1...vk인사이클을 이룬다.

1.7.3

1.7.4

1.7.5

week 3

1.8 The Shortest Path Problem

(대충Dijkstra’s Algorithm에대한내용)

1.8.1

1.8.2

1.8.3

1.8.4

1.8.5

가능한모든경우의수를센다.이때양방향이아닌한방향간선은사이클을형

성하므로최적의경로로서제외해도문제없다.

1. 시작(8,0,0) →2,3

2. (3,5,0) →1,4,5

3. (5,0,3) →1,4,6

4. (0,5,3) →2,3,5

5. (3,2,3) →2,4,7

6. (5,3,0) →3, 8

7. (6,2,0) →5,9

8. (2,3,3) →6

9. (6,0,2) →7,10

10. (1,5,2) →9,11

11. (1,4,3) →10,12

12. 끝(4,4,0) →11,13,14

13. (4,1,3) →12

14. (1,4,3) →12

1→2→5→7→9→10 →11 →12

1.8.6

1.9 Sperner’s Lemma.

2차원평면상의삼각형T에대해서이를작은 삼각형으로쪼갤때교차하는삼

각형이꼭지점또는전체면을공통으로가질때이삼각형을쪼갠것을단순하다

(be simplicial)라고한다.

그다음단순한삼각형의쪼갬에대해서쪼개진각정점에대해서다음이 성

립할때, 0,1,2 세개의분류(labelling)가적절(be proper)하다고한다.

그림1: (a) Asimplicial subdivision of a triangle (b) a proper labelling of the

subdivision

•T의세개의정점에는0,1,2가하나씩붙는다.

•그리고T의정점 사이의 정점에는양끝T의정점의두값만값이붙을수

있다.

각정점을0,1,2로가지는삼각형을구별된삼각형이라한다.

Theorem 1.3 (Sperner’s lemma).적절히분류되고(properly labelled) 단순하게

(simplicial) 삼각형을쪼갠것은내부에홀수개의구별된삼각형을가진다.

Proof. T를T0라하자.그다음T1, T2, ..., Tn을쪼개진삼각형들이라고하자. 0과

1로각각 분류된Ti와Tj가 공통간선일때vi,vj에간선이존재하는정점 집합

{v0, v1, ..., vn}을정의하자.(이정점은T에대응할수있다.)

이그래프에서v0는명백하게차수가홀수값을가진다.(1.9.1) 따라서v1, v2, ..., vn

중에홀수개가 홀수값차수를가지게된다.삼각형이라서이홀수개의차수를가

지는정점들이차수값이오직1만을가짐을알수있다.vi의차수가1임은 Ti가

구별된삼각형인경우만이다.

1.9.1

경계 사이의 정점의갯수를n이라하고수학적귀납법을적용한다.사이에정점이

없다고생각해보자.그러면0−1로v0의차수는1이다.경계 사이의 정점이N

에서v0의차수가홀수임이 성립한다치고N+ 1일때를N에정점 한개를삽입

할때양끝정점은네가지경우가나온다.

•0−1

•0−0

•1−0

•1−1

1−0, 0 −1는대칭이므로똑같이생각해도되며1−1과0−0또한대칭이다.

1−1일때는가운데에0을삽입할경우에차수가+2가되며1일때는그대로

홀수이다. 0−0일때도마찮가지1−0일때는가운데에0을삽입할경우1−0−1

연결되는간선은달라졌지만차수는그대로다1을삽입해도마찮가지이며0−1

일때도마찮가지이다.따라서N+ 1에서도홀수임이 증명되어수학적귀납법에

따라v0는항상홀수이다.

week 4

2 Tree

2.1 Trees

정의2.1 (tree) connected acyclic graph

acyclic graph(forest) : 사이클이없는그래프

Theorem 2.1. 트리에서두정점은서로유일한경로를가진다.

Proof.

Theorem 2.2. 그래프G가트리이면ϵ=ν−1

Proof.

Corollary 2.2.1. 정점이한개가 아닌트리(nontrivial tree)는적어도두개의정

점의차수가1이다.

2.1.1

2.1.2

2.1.3

2.1.4

2.1.5

Let 0 be a graph with v-I edges. Show that the following three statements are

equivalent: (a) G is connected; (b) G is acyclic; (c) G is a tree.

연결된acyclic graph는정의에의해tree임이 자명하므로간선의개수가ν−1

일때, acyclic graph일때connected한것과 connected graph일때acyclic 그래프

임이 필요충분조건임을 보이는것으로충분하다.

acyclic →connected graph

acyclic그래프가connected graph가아니라고 가정해보자.

그러면각component는connected graph이므로트리이다.각component의

간선의갯수의합은v(G1)−1 + v(G2)−1 + ... +v(Gn)−1=v(G)−1따라서

가정에모순다음명제가성립한다.

connected graph →acyclic

acyclic graph가아니라고하자cycle이형성된곳의간선을하나씩제거해서

acyclic 그래프가되도록만들면트리가된다.ν−1−n=ν−1가정에모순이라

다음명제가성립한다.

2.1.6

2.1.7

2.1.8

A centre of G is a vertex u such that max d(u, v) is as small as possible.

Show that a tree has either exactly one centre or two, adj acent, centres.

G의중심은최대d(u, v)가 가능한 한 작은 꼭지점u이다.

트리하나가정확히하나의중심또는두개의 인접한중심을가지고있음을

보여라

2.2 Cut Edges and Bonds

정의2.2 (cut edge) 그래프G에대해ω(G−e)> ω(G)인간선e를절단간선

(a cut edge)이라고한다.

Theorem 2.3. 그래프G의간선e가사이클에속하지않으면간선e는절단간

선이다.

Proof.

Theorem 2.4. 모든간선이절단간선이면연결된그래프는트리이다.

Proof.

정의2.3 (spanning tree) 그래프G의트리인spanning subgraph를G의신장

트리(spaning tree)라고부른다.

Corollary 2.4.1. 그래프G가connected graph이면G의cennected spanning

subgraph가존재한다.

Proof. 그래프H를G의최소한의connected spanning subgraph라하자.이때

H가acyclic가아니라고 가정해보자.그래프H가사이클이존재하는경우,간선

사이클경로의 임의의 인접한정점 u, v를잡았을때u, v의간선을제거해도u, v

는여전이연결되어있다.이는최소한의connected spanning subgraph라는것

에모순이다.따라서그래프H는connected spaning graph이며acyclic함으로

스패닝트리이다.

Corollary 2.4.2. 그래프가연결되어있으면ϵ≥v−1

Proof.

Theorem 2.5. 연결된그래프G의스패닝트리를 T라하자e를T에속하지않은

그래프G의간선이라할때T+e는유일한사이클을가진다.

정의2.4 (an edge cut) •[S, S′] : S, S′≤V이고,정점이각각 S,S′에하

나씩있는간섭집합을에있는것을[S, S′]라표현한다.

•An edge cut of G:S는비어있지않은적절한V의부분 집합이고,¯

V/S인[S, ¯

S]를G의간선절단(an edge cut of G)이라고한다.

•Bond : 최소한의비지않은G의간선절단을본드(bond) 라고한다.

•¯

H(G) : H를G의부분 그래프라고할때¯

H(G)를G−E(H)라고한다.

•cotree :연결그래프G에서,스패닝트리T의¯

T형태를G의cotree라고한

다.

Theorem 2.6. T를그래프G의스패닝트리라고할때,e를T의어떤간선이라

고하자.그러면

•cotree ¯

T는G의본드를가지고있지않다.

•¯

T+e는G의 유일한본드를가지고있다

Proof.

2.2.1

포레스트G의컴포넌트는트리이므로트리의간선은컷엣지이따라서그래프의

모든간선또한컷엣지이다.반대로모든간선이컷엣지임은 연결된각각의그

래프를모으면트리가되며이를모아포레스트를형성할수있다.

2.2.2

(a)e가컷엣지가일때간선e가모든스패닝트리에속하지않는다고생각하자.

그러면e가속하지않은스패닝트리는e에인접한두정점 a,b에이르는경로가

하나더있다.하지만컷엣지e에인접한a,b는e를유일한경로로 가지므로모

순이다.

(b) e가루프일때스패닝트리에속한다고하자.하지만e는자체만으로사이

클을형성하므로트리의정의에위배된다.반대로트리는루프를간선으로가

질수없다.

2.2.3

2.2.2(a)에의해스패닝트리에사용되는모든간선이컷엣지일시에스패닝트리

는 단 한개만을가지며2.2.2(b)에의해루프인간선은스패닝트리의간선이될수

가없다.따라서루프가없고모든간선이컷엣지인그래프는Theorem2.4에의해

그자체로트리가된다.

2.2.4

maximal forst : 그래프G에서간선뗄거떼서트리로만들어G자체가컴포넌트

가있음을 가정해가장큰포레스트로만드는것

(a) 트리는그자체로스패닝트리를 가진다. forest의정의에따라F의모든

component는스패닝트리이다.F∩H이교집합은H의스패닝트리를 나타낸

다.

(b): 2.2.5와증명이같다.

2.2.5

한component i의간선의갯수를ϵi,정점의갯수를vi라하자 이때Corollary2.4.2

에의해ϵi≥vi−1이성립한다.모든컴포넌트에의해성립하므로이를모두더

하면ϵ≥v−ω가성립한다.v−ω보다큰간선의갯수하나마다사이클을무조건

형성하므로따라서최소한의만들어지는사이클의갯수는ϵ−v+ω이다.

2.2.6

(a) : 모든차수가짝수일때,컷엣지가존재한다고하자.그러면해당컷엣지를

제거했을때컷엣지의 인접한두정점은차수가홀수가된다.이때corollary 1.1

에의해각각의component는홀수의정점을무조건한개씩더가져야하는데이

는모든차수가짝수임에모순이다. (b) :

2.2.7

2.2.8

2.2.9

2.3 Cut Vertexes

정의2.5 (cut vertex) E가두개의비지않은부분집합정점 v만을 유일하게 가

지는G[E1],G[E2]로분할될수있을때정점 v를절단정점(a cut vertex)라한다.

G가loop간선이없고nontrivial일때,ω(G−v)> ω(G)인정점 v를절단정

점이라한다.

Theorem 2.7. 트리G에대해d(v)>1일때v는절단정점이다.

Proof.

Corollary 2.7.1. 모든nontrivial,loopless 연결그래프는절단정점이아닌정

점을적어도두개이상가진다.

Proof.

week5

Theorem 2.8. T가연결된그래프G의스패닝트리라고하고e를T에속하지

않은G의에지라고하자.그러면T+e는유일한사이클을가진다.

Proof. ψG(e) = xy라할때,유일한사이클이아닌두개이상의사이클이생성될

경우e의에지추가하기전의x, y 유일한경로가아닌두개이상의경로가있다는

것을 의미하는데트리는유일한경로임이 이미증명되었으므로유일한사이클을

가진다.

2.4 Cayley’s Formula

정의2.6 (contract) 그래프G의한에지e를수축한다는 것은에지e를그래프

에서삭제하고양끝점을하나의정점으로합치는것이다.그결과 만들어지는

그래프를G·e로표시한다.

•ν(G·e) = ν(G·e)−1

•ε(G·e) = ε(G·e)−1

•ω(G·e) = ω(G)

•T가트리이면T·e도트리이다.

•그래프G의스패닝트리의개수를τ(G)로표시한다.

Theorem 2.9. 2.8 그래프G의 임의의 에지e에대해서τ(G) = τ(G−e) +

τ(G·e)이성립한다.

Proof. 그래프G에서에지e를포함하지않는스패닝트리는G−e의스패닝트

리또한된다.따라서τ(G−e)는그래프G에서에지e를포함하지않는스패닝

트리의개수와같다.에지e를포함하는G의 임의의 스패닝트리T는G·e의

스패닝트리T·e에일대일대응한다.(추가적인논리필요)따라서τ(G·e)는G

에서에지e를포함하는스패닝트리의개수이다.따라서정리가성립한다.

Fortunately, and rather surprisingly, there is a closed formula for T(G)

which expresses T(G) as a determinant; we shall present this result in chapter

12.

Theorem 2.10. Cayley′sf olmula :τ(Kn) = nn−2

Proof. Kn의정점 집합을N={1,2, ..., n}라놓자.그러면nn−2는N으로부

터길이가n−2인수열1을만드는수로볼수있다.따라서이수열이Kn의

spanning tree와1:1대응을 하는걸로이증명이완성된다.Kn의spanning tree

T에대해서특정수열t1, t2, ..., tn−2과연관지으려한다.N을정렬된셋이라가

정하고,s1은T의차수가1인첫번째정점이라하자.s1은t1과인접한정점이다.

그다음에s1를T에서제거하자그다음T−s1에차수가1인정점 한개를s2라하

자 이 짓거리를 tn−2가지워져두정점이남을때까지반복한다.총반복은n−2

1P r¨uf er sequences라한다.

번 반복한다.따라서spanning tree가수열에 대응함을보였다.수열이spanning

tree에대응함을보이자. sequence P에 없는1에서n중가장 작은 숫자를찾아

P의첫번째숫자에 연결한다.그후P의첫번째숫자를제거한다. P가존재하지

않을때까지반복한다.마지막연결되는숫자는n이다.이렇게함으로써수열이

트리에대응됨을보일수있다.수열의갯수가nn−2개이므로트리의개수도nn−2

개이다.

2.5 THE CONNECfOR PROBLEM

(대충크루스칼알고리즘에대한내용)

3 Connectivity

3.1 Connectivity

정의3.1 (Connectivity) Connectivity

•A vertex cut : G−V′가연결되지않은그래프인V의부분 집합V′를정점

절단(A vertex cut) 이라고한다.

•k-vertex cut : k개의원소를가진정점 절단.완전그래프(complete graph)

는정점 절단을가지지 않는다.

•스패닝서브그래프로서완전그래프를가지는그래프는정점 절단을가지

지않는다.

•connectivity κ(G) : 그래프G가 가지는k−vertexcut의최소값k를κ(G)

라고한다.그래프G가trivial이거나연결되지않은그래프일때κ(G) = 0

이다.

•k−connected :κ(G)≥k일때그래프G는k−connected이다.

•모든nontrivial connected graph는1−connected이다.

정의3.2 (Edge connectivity) Edge connectivity

•k-edge cut : k개의원소를가지는간선절단(edge cut).

•Edge connectivity κ′(G) : nontrivial 그래프G의k-edge cut E′G−E′

는연결되어있지않다.k−edgecut를가지는G의최소한의k를κ′(G)라

표현한다.G가trivial이거나연결되지않은그래프일때,κ′(G)=0이다.

•κ(G)≥k일때G는k-edge-connected이다.

•그래프G가연결된그래프일때κ′(G) = 1이고모든nontrivial connected

그래프는1-edge-connected이다.

Theorem 3.1.

3.1.1

(a) Show that if G is k-edge-connected, with k > 0, and if E’ is a set of k.

edges of G, then w(G−E′)<2

ω(G)=1

case 1) k′(G)> k →ω(G−E′) = 1

case 2) k′(G) = k→ω(G−E′) = 2

∴ω(G−E′)≤2

(b) .For k > 0, ﬁnd a k -connected graph G and a set V’ of kvertices of

G such that ω(G−V′)>2.

모래시계모양에 가운데정점에추가한간선에다른한정점이 이어진모양

3.1.2

Show that if G -is k-edge-connected,.then ϵ > kv/2.

Theoream 3.1에의해k≤δ따라서k×v≤2ϵ

3.1.3

(a) :

case 1) δ=v−1

csae 2) δ=v−2

(b) : 모래시계

3.1.4

(b) : 모래시계 가운데정점이나뉘어져가운데간선이하나있는경우

3.1.5

3.2 BLOCKS

정의3.3 (Blocks) Block : 절단정점들이존재하지않는연결된그래프를block

이라한다.적어도세개이상의정점을가진모든블록은2-connected이다.그래

프의블록은최대로블록의성질을가질수있는상태이다.(대충블록이또블록

으로쪼개지는경우는생각안한다는것.)

Theorem 3.2.

4 Euler Tours and Hamilton Cycles

4.1 Euler Tours

정의4.1 (Euler Tours) Euler는7개의Konigsberg 다리를 마을을 한번만거쳐

서갈수없음을 보였다

•Euler trail : 모든간선을지나는trail

•tour : 적어도하나의간선을가지는 닫힌(closed) walk

•Euler tour : 각 간선이정확히한번사용된tour

•eulerian: Euler tour을가지는그래프

Theorem 4.1. 홀수차수의정점을가지지않는비지않은연결된그래프는eu-

lerian이다.

Proof.

4.2 HAMILTON CYCLES

Hamilton이Graves에게보낸편지에서유래했다.

정의4.2 (Hamilton cycle) hmm..

•Hamilton path : 모든정점을포함한 path

•Hamilton cycles : 모든정점을포함한 cycle

5 Matchings

5.1 Matchings

정의5.1 (Matching) E의부분 집합M이각원소가link이고그래프G에서

서로인접하지않으면G의매칭(matching)이라고한다.

•M의간선의양끝을M에일치되어있다(be matched under M)라고한다.

•saturated : M의간선이정점 v에인접할때v를포화되었다(be Saturated)

라하고,매칭M이정점 v를포화시킬때,v를M-saturated 되었다(be M-

saturated) 라고한다.반대는M-unsaturated라한다.

•모든정점이M-saturated 되었을때, M을완전(perfect)이라고한다.

•M-alternating path : E/M과M의간선을교대로선택한path

•M-augmenting path : 처음과끝이M-unsaturated인M-alternating path

Theorem 5.1. 매칭M은맥시멈매칭이다와G가M-argumenting path를가지

지않는다 는 필요충분조건이다.

Proof.

5.1.1

(a) : (b) : K2n:

k=1

(2k−1)

Kn,n =n!

5.1.2

case 1: V갯수가홀수인경우퍼펙트매칭을가질수없음. case 2: V갯수가짝

수인데홀수개인차수를가지는정점이 있는경우

5.1.3

5.1.4

5.1.5