Graph[그래프]

1학년 때 배우고 이게 중요한지 알게된건 4학년 뭐하며 산것인지... 에휴

필요한 개념이여서 천천히 정리하자.

주로 영어 용어로 정리하고 익숙하게 해야 할거 같다. 한글에 익숙해있어서 어려울거 같다.

그래프의 개념

Graph

Vertex or Node[꼭지점]로 서로 다른 Vertex와 연결되는 edge[변]로 연결된 것.

인접[adjacent]과 근접[incident]

adjacent는 서로 다른 Vertex를 연결하는 edge가 있는 경우를 말한다.

vertex u와 v가 있고 이를 연결하느 edge e가 존재 할때,

edge e는 vertex u,v에 incident라고 한다.

Loop[루프]

근접하는 점이 같은 점인 변 

walk[길]

그래프에서 꼭지점 Vi와 Vi+1을 연결하는 변을 Ei라고 할 때,

v1에서 시작하여 vk에 도착하는 꼭지점과 변의 나열

Path[경로]

같은 변을 두 번 이상 포함하지 않는 길

Circuit or Cycle

경로의 시작점과 끝점이 같은 길

Length

경로 또는 순환을 구성하는 변의 수

Multi-Grapth

서로 다른 Vertex 중에서 두 개 이상의 edge를 허용하는 그래프

Directed Grapth

변에 방향이 존재하는 그래프

작성 할때 규직은 V = {a,b,c,d}일 때를 생각 해보면

Vertex b에서 시작하여 Vertex d로 끝나면 <b,d>로 작성.

Weighted Graph

각 edge에 Weighted[가중치]가 정의되어 있는 그래프

Degree

d(v) 라고 표시한다 --> Degree(vertex)라는 의미인거 같다

꼭지점 v에 근접하는 변의 수를 Degree[차수]라고 한다.

Out-d(v)

방향 그래프에서 Vertex v로 시작하는 화살표의 수

In-d(v)

방향 그래프에서 Vertex v를 끝으로 하는 화살표의 수

Degree에 대한 정리

모든 꼭지점의 차수의 합은 변 수의 두배이다.

차수가 홀수인 꼭지점의 수는 짝수다.

증명은 위의 차수의 합은 변수의 두 배 짝수이다.

그래프의 종류

Subgraph

그래프 G= (V, E) --> Grapth = (Vertex, Edge)

V` ([포함] V이고 E` ( E인 그래프 G` = (V`,E`)을 부분 그래프라고 한다.

Spanning Graph

그래프 G= (V, E), V` = V 이고 E` ( E인 그래프 G` = (V`,E`)을 스패닝 그래프라고 한다.

간단하게 설명하면 Vertex는 같은데 Edge가 차이나는 그래프이다.

Planer Graph

그래프 G =(V,E)를 평면에 그릴때, 꼭지 점이 아닌 곳에서 어떤 변도 교차하지 않는 그래프

Connected Graph

그래프 G=(V,E) 내에 있는 임의의 꼭지점 u, v 간에 경로[path]가 있는 그래프

Complete Graph

그래프 G =(V,E)내에 있는 모든 꼭짓점 u,v간에 변이 있는 그래프

Regular Graph

그래프 G=(V,E) 내에 있는 모든 꼭짓점의 차수가 같은 그래프

Bipartite Graph

그래프 G = (V,E)에서 꼭지점 집합 V를 두개의 부분집합으로 나눈다. V1, V2라고 

그리고 두 V1과 V2의 관계는 V = V1 or V2이고 V1 and V2는 공집합이다.

Complete Bipartite Graph

Bipartite Graph에서 두 V1과 V2에서 모든 꼭지점 사이에 변이 있는 것

오일러와 해밀턴

오일러는 변과 관련된 정리이다.

Eulerian Path[오일러 경로]

G=(V,E)의 모든 변을 꼭 한 번씩 지나는 경로

Eulerian Cycle

G=(V,E)의 한 Vertex에서 시작해 모든 edge를 지나 v로 돌아오는 회로

Eulerian Grapth

G=(V,E)에서 오일러 회로를 포함하는 그래프

Eulerian Grapth에 대한 정리

1. 모든 꼭짓점의 차수가 짝수 일 때, 오일러 그래프의 필요충분 조건이다.

2. 오일러 경로를 갖기 위한 필요충분조건은 꼭지점 중 차수가 홀수인 꼭짓점의 수가 0또는 2개인 것이다.

Hamiltonian은 vertex[node]와 관련된 정리이다.

Hamiltonian 정의

어떤 edge를 지나든지 상관 없이 모든 vertex를 반드시 지나가도록 하는 방안

Hamiltonian Path

G =(V,E)의 모든 꼭짓점을 꼭 한 번씩 지나는 경로

Hamiltonian Cycle

G = (V,E)에서 한 vertex에시 시작해 모든 vertex를 거치고 다시 한 vertex로 돌아오는 회로

Hamiltonian Graph

Hamiltonian Cycle을 포함하는 그래프

그래프의 표현

그래프를 표현 하는 방법에 어떤 것들이 있는지 알아본다.

1. Adjacency Matrix

인접 행렬로 이용한 표인이 있다. 

이때는 n*n 배열을 이용해서 표현한다.

2. Adjacency List

인접 연결리 스트를 이용해서 사용한다.

각 vertex마다 시작 node를 생성하고 연결 되있는 노드를 연결 시키는 방식이다.

a ->c [a는 c하고만 연결]

b ->c -> d [b는 c와 d와 연결]

c -> a -> b [c는 a와 b와 연결]

d -> b -> d [d는 b와 d와 연결]

그래프의 활용

1. 최단경로 문제 해결[Shortest Path Problem]

가중치 그래프를 이요한 최단 경로 이용

다익스트라 알고리즘

2. 깊이 우선 탐색[DFS : Depth First Search]

시작점 v1에서 인접해 있는 꼭짓점 중 아직 탐색하지 않은 꼭짓점 v2를 방문하고,

꼭짓점 v2에 인접해 있는 꼭짓점 중 아직 탐색하지 않은 꼭짓저 v3을 방분하는 것을 반복

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

3. 너비 우선 탐색[Breath First Search]

시작점 V1로 부터 인접한 꼭짓점 V2, ...., V2n을 모두 탐색하고, 다시 꼭지점 V3..., V3m을 시작으로 인접한 꼭짓점을 탐색 하는 방식

예를 들어 셜명하면

1 .a와 인접하고 탐색되지 않은 node b,c가 있으면, b,c를 탐색한다.

2. b와 인접하고 탐색되지 않은 꼭짓점 d,e가 있다 d부터 탐색하고 e를 탐색한다.

3. 그다음 위에서 찾은 c와 인접하고 탐색되지 않은 node를 찾는다.

이러한 방식으로 찾아 나선다.

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.