[이산수학] 그래프 간선 정점 완전 차수 오일러 싸이클 동형

그래프란?

실생활에서 서로 관련되는 두 가지 또는 그 이상의 양의 관계를 정점과 간선을 이용하여 그림으로 나타낸 것입니다. 그래프는 자료 요소들의 관계가 비선형 구조로 나타날 때 사용되는 자료구조입니다. 

 

 각각의 간선 e가 존재하면 e = (v,w) 혹은 e=(w,v)라고 나타냅니다. 여기서 (v,w)는 무방향 그래프에서 정점 v와 w간의 간선을 나타내며 방향이 있는 쌍이 아닙니다. 

 

그래프의 설명

그래프 g는 정점의 집합 v와 간선의 집합 E로 구성되어 있고, 각각의 간선 E는 순서가 없는 정점의 쌍으로 나타냅니다. 

 

만약 정점 v와 w를 연결하는 유일한 간선 e가 존재하면 e = (v,w) 또는 e= (w,v)라고 나타냅니다. 여기서 (v,w)는 무방향 그래프에서 정점 v와 w간의 간선을 나타내며 방향이 있는 쌍이 아닙니다. 

 

방향그래프 G는 정점의 집합 v와 간선의 집합 e로 이루어져 있고 각각의 간선 e 는 순서가 있는 정의 쌍으로 나타냅니다. 

 

G가 정점 V와 간선 E가 가지는 그래프이면 ,G = (V, E)라고 표기합니다. 

 

 

병렬 간선

2개 이상의 쌍이 존재하는 간선들의 합입니다. 

 

LOOP는 자기 자신으로 돌아오는 것입니다. 

 

단순그래프

루프도 없고 parallel edges도 없는 것을 의미합니다.

 

가중치 그래프

각각의 간선에 수치값이 있는 것을 말합니다. 

 

경로

경로는 정점 v0에서 시작해서 v1 정점으로 이동 ... 이런 과정을 거쳐서 정점 vn에 도착하는 것을 v0 to vn의 경로라고 정의를 하게 됩니다. 

 

무방향그래프의 경로의 길이는 간선의 개수라고 봅니다. v0에서 vn으로 가는 경로를 보면 경로를 속하는 간선을 세워보면 3개의 간선을 통해서 도달을 하는 것이 있다고 보면 경로의 길이는 3이 됩니다. 

 

가중치 그래프인 경우에 경로의 길이는 경로에 속하는 간선의 가중치의 합입니다. 따라서 동일하게 경로가 3번 주어졌지만 가중치가 8, 4, 5로 나온다면 이는 17이 되는 것입니다. 

 

정점의 차수

Degree 차수라고 얘기하는 이것은 deg(v)로 표기합니다. 

 

정점에 결합된 간선 v의 개수를 degree라고 정의합니다. 

위와 같은 경우 a에 결합된 간선은 총 4개입니다. 

deg(b) = 3, deg(c) = 4, deg(d) = 6 ... 이런 식으로 정점의 차수는 그 정점에 연결된 간선의 개수라고 보시면 됩니다. 

 

그래프의 속하는 모든 정점들의 차수의 값은 짝수입니다. 

완전 그래프

하나의 간선에 의해서 연결이 되면 완전 그래프가 됩니다. 

이분그래프

 

정점의 집합이 V1과 V2 두 개의 집합이 분할이 되는 것

 

 

완전 이분 그래프

V1에 속하는 정점과 V2에 속하는 정점 사이 완전히 간선이 존재할 때 완전 이분 그래프라고 합니다. 

V1은 모든 V2에 V2는 모든 V1에 간선이 존재하는 것을 말합니다. 

 

경로와 싸이클

경로의 정의는 v0 정점에서 vn에서 n인 경로를 말합니다. 

 

경로는 n + 1개의 정점 그리고 n개의 간선을 교차하는 수열을 말합니다. v0에서 vn으로 끝나는데 정점간선 형태로 교차되어서 표기되는 수열을 말합니다. 

 

정점의 개수는 n + 1 간선의 개수는 n개가 됩니다. 각각의 간선 ei는 vi-1과 vi를 결합시키는 간선입니다. 

 

 

그래프 g가 연결되어 있따는 것은 v와 w에 대해서 경로가 존재하는 것을 그 그래프가 연결되어있다 라고 봅니다. 

 

부분 그래프

Let G = (V, E) be a graph

 

Simple path

v에서 w로의 단순 경로는 중복된 경로를 가지지 않는 것을 단순 경로라고 합니다. 

 

Cycle

v에서 v로의 길이가 0이 아닌  경로를 말합니다. 이는 중복된 간선을 가지지 않아야 합니다.

 

Simple cycle

중복되는 정점을 가지지 않는 simple cycle입니다. 출발과 도착을 제외하고 중복을 가지지 않아야 합니다. 

 

오일러 사이클

모든 간선을 정확하게 한번 통과하는 사이클

오일러 사이클을 가지면 CONNECTED가 되며 그 그래프 G는 연결된 그래프이면서 모든 정점이 짝수 차수를 가지는 것입니다. 

정점들의 차수를 계산하면 다 짝수이며 오일러 싸이클을 가지는 것을  알 수 있습니다. 

 

오일러 싸이클이 되는 조건

1. 연결된 그래프인지
2. 정점의 차수가 모두 짝수인지

해밀턴 싸이클의 조건

-모든 정점을 정확하게 한번 방문하는 것

8.3.4 그래프틑 7개의 정점을 가지고 있으며 해밀턴의 간선은 7개가 되어야합니다. 각 정점의 차수는 2가 되어야 합니다. 해밀턴 싸이클을 가지는 것을 확인할 수 있습니다. 

 

하지만 8.3.5 그래프 같은 경우는 간선이 2개가 되도록 만들면 즉 정점의 차수가 2가 되도록 하면 간선이 4개가 남게 됩니다. 하지만 해당 정점은 5개이므로 간선또한 5개가 되어야 하는데 그것을 만족하지 않으니 해밀턴 싸이클을 가질 수 없습니다. 

 

Traveling salesperson problem

가중치 그래프 G에서 최소 길이를 찾는 해밀턴 사이클을 찾는 문제 

이 링 모델을 그래프와 싸이클로 알아보도록 합시다.

 

Grayt code (그레이 부호)

s1, s2 , ... , s2n 에서 

 

n비트 스트링으로 표현될 수 있는 스트링이 나타납니다. k번째 수와 k+1번째 수와 1비트가 다릅니다. 그리고 제일 마지막 번째와 첫 번재 수 또한 한비트가 다르다면 그레이부호라고 얘기를 합니다. 

 

그레이부호는 해밀턴 싸이클에 해당이 됩니다.

 

각 비트는 3비트로 표현되는 이진수 입니다. 

 

3비트 그레이 코드를 연결하면 

G3 : 000     001    011    010    110    111    101    100

이 나오게 됩니다. 이것이 해밀턴 싸이클이 되는데요. 3비트 그레이 코드는 마지막과 처음이 1비트 차이가 나고 연속되었기에 가능한 것입니다.

 

Dijkstra's algorithm

경로를 찾는 가장 빠른 방법

 

인접행렬

행과 열은 정점으로 표현을 하고 행렬의 값은 0 아니면 1의 값으로 합니다. 즉 row와 column에 간선이 존재하면 1 없으면 0으로 합니다.

결합행렬

결합행렬의 표현방법은 행은 정점 열은 간선으로 표기를 합니다. 이 간선이 정점에 연결되어 있으면 1의 값, 없으면 0의 값으로 표현하면 됩니다. 

 

동형그래프

그래프 G1와 G2가 동형이라는 것은 두 그래프가 

1. one - to - one
2. onto functions

이면 됩니다. 

 

v(g1) -> v(g2) 그리고 e(g1) -> e(g2) 

함수 f가 존재하고 g1 g2를 만족하는 g가 존재하면  onto, one-to-one이면 두 그래프는 isomorphic이라고 합니다. 

G1에서의 간선을 G2에서의 간선으로 매핑시키고 a정점과 e정점을 연결하는 간선 x1 이 성질을 만족하는데 g2에서 A 정점, E 정점을 보면 x1 과 y1과 매핑되는 것을 볼 수 있습니다. 

 

이렇게 그대로 보존이 되는 걸 Isomorphic 된다고 합니다. 모양은 다르지만 그래프의 성질이 똑같은 경우입니다. 

 

동형이 될 필요충분조건은 어떤 순서에 의해서 인접행렬이 동일하다 이러면 동형입니다. 

 

• G1과 G2가 동형이다.
• G1 G2 사이의 매핑하는 G1에서 인접관계가 G2에서 f(v) f(w) 그대로 만족하면 된다.