[이산수학] (11) Coloring
G의 K-coloring은 k가지 색상으로 vertices를 칠하는 경우를 뜻한다. def) 만약 uv in E(G)의 u,v가 f(u) != f(v)라면 G의 K-coloring은 proper하다. 즉 adjacent한 vertices의 색상이 다르면 proper coloring이다. prop) G가 V(G)=n인 그래프라면, proper n-coloring이 존재한다. pf) |V(G)| = n, V(G)={v1, ..., vn}, f:V(G) -> {1,...,n}일때, vivj in E(G)의 vi, vj가 f(vi) = i != j = f(vj)이기 때문에 n-coloring of G가 proper하다. G가 graph일 떄, G의 Chromatic #는 kai(G)라고 표기하고, kai(G) ..
2022. 6. 14.
[이산수학] (7) Connection
그래프 G에서 Walk란 모든 vertices가 그다음 vertices에 대해 adjacent(ex. v0~v1~v2~...~ve)한 sequence다. 예를 들어 w1 = (v1,v2,v3,v2,v4,v5,v6,v4,v6,v7)은 (v1,v7), 길이 9의 walk다. walk의 vertices는 중복되어도 상관없다. 만약 vertices가 중복되지 않은 walk라면 이는 path다. 위 예시에서 w3은 path다. 그래프 G에서 (x,y) walk가 있다면, (x,y) path는 반드시 존재한다. 가령 walk가 v0~v1~ ... ~ vi ~ u ~ (... ~ u) ~ vj ~ ... ~ ve 이고, (... ~ u) 와 같이 중복되는 부분을 모두 잘라내면 path가 된다. V(G)의 x,y가 존..
2022. 5. 18.
[이산수학] (5) Handshaking Lemma
G가 graph일 때, 모든 vertices에 대한 sigma sum of d(v)는 2*|E(G)|다. 이를 handshaking lemma라 부른다. 여기서 파생된 corollary: 홀수인 d(v)의 갯수는 짝수여야만한다. 예시1. 홀수인 degree of vertices가 4개다. 예시2. 홀수인 d(v)가 6개다. corollary를 증명하기 위해서, 2|E(G)|는 mod2일때 remainder=0 or 1로 나뉜다. 2|E(G)|의 mod2는 0이고 remainder = 0일때도 0, degree seq은 (0,1,2,2,2,2,2,3)과 같이 특정 그래프의 degree를 나열한 수열이다. 예시 Handshaking Lemma의 cor에 의해 홀수 degree의 갯수는 짝수다. 그래프의 de..
2022. 4. 20.
[이산수학] (4) Fundamentals of Graph Thoery
Graph Theory에 대해 알아보자. graph G는 (V(G), E(G))다. V(G)는 유한개의 꼭짓점(vertices) 집합이고, E(G)는 V(G)의 원소 중 두개로 구성된 변(edges)이다. 1번예시를 살펴보자. V(G)가 v1, v2, v3, v4, v5로 구성된 유한개의 집합이고, E(G)는 V(G)의 원소 2개로 구성된 부분집합이다. 이 때 G=(V(G), E(G))는 그래프라 한다. 사실 이렇게 기호로 나열하는 것보다 그림을 그리는 것이 좋다. vertices의 위치가 정의된 것이 아니기에 다양한 종류의 그래프가 그려질 수 있지만 모두 같은 그래프로 간주한다. 좌우측 그림 모두 같은 그래프다. 그래프에 대한 몇가지 특성을 살펴보자. 첫째, edge에는 방향성이 없다. {r1, r2}..
2022. 4. 20.
