[이산수학] (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.
[이산수학] (2) Relations
Relation(관계)에 대해 알아보자. A가 공집합이 아니라면, '관계'는 순서가 정해진 A 내부 원소의 pair를 뜻한다. 예를 들어 A가 모든 정수들의 집합이라면 (1,2), (1,3), (0,3), (-1,4)를 원소로 갖는 R은 A와 A 사이의 relation이다. 원소간의 순서가 존재하기 때문에 이는 relation이라 봐야한다. 가령 (1,2)은 R에 속하는 원소지만, (2,1)은 아니다. (1,2)가 R의 원소라면, 1은 2에 related되어있다고 표현한다. 그러나 2가 1에 related된 것은 아니다. (2,1)이 R의 원소가 아니기 때문이다. 아래 2번 예시도 같은 얘기를 담고 있다. (a,b)가 R의 원소라면, 즉 a가 b에 related되어있다면 aRb로 표현한다. 4번 예시를 ..
2022. 4. 19.
