그래프

그래프

• 공집합이 아닌 꼭짓점(node)의 집합 V와 서로 다른 꼭짓점의 쌍(vᵢ, vⱼ)을 연결하는 모서리(edge)의 집합 E로 구성된 구조
  • G = (V, E)
  • V = {v₁, v₂, ... , vₙ}
  • E = {e₁, e₂, ... , eₙ} = {(vᵢ, vⱼ), ... }
• G = (V, E) : 그래프 G는 꼭짓점 집합 V와 모서리 집합 E로 구성
• 그래프 G = (V, E)에서 꼭짓점 u와 v를 연결한 모서리 e가 있을 때, 꼭짓점 u와 v는 서로 인접(adjacent)하고, 모서리 e는 꼭짓점 u와 v에 근접(incident)함
• 루프: 인접하는 꼭짓점이 하나인 모서리 e
• 다중 그래프: 그래프 G = (V, E)에서 두 꼭짓점 사이에 두 개 이상의 모서리가 있는 그래프
• 방향 그래프: 화살표로 모서리를 표현해 인접하는 꼭짓점 간의 순서를 알 수 있는 그래프
  • G = <V, E>
  • V = {v₁, v₂, ... , vₙ}
  • E = {e₁, e₂, ... , eₙ} = {<vᵢ, vⱼ>, ... }
  • 시작하는 꼭짓점에서 끝나는 꼭짓점으로 화살표를 이용해 그림
  • 인접하는 꼭짓점 사이에 순서가 존재
• 가중치 그래프: 그래프 G = (V, E)에서 각 모서리에 가중치가 부여된 그래프
  • 가중치 그래프의 W[u, v]는 두 꼭짓점에 근접하는 모서리에 부여된 가중치를 의미

그래프의 차수

• d(v)
• 꼭짓점 v에 근접하는 모서리의 수
  • 홀수점(Odd Degree): 차수가 홀수인 꼭짓점
  • 짝수점(Even Degree): 차수가 짝수인 꼭짓점
• 방향 그래프의 경우
  • 외차수(Out-degree, out-d(v)): 꼭짓점 v를 시작으로 하는 화살표의 수
  • 내차수(In-degree, in-d(v)): 꼭짓점 v를 끝으로 하는 화살표의 수
• 차수에 대한 정리
  • 그래프 G = (V, E)에서 모든 꼭짓점의 차수의 합은 모서리 수의 2배
  • 그래프 G = (V, E)에서 차수가 홀수인 꼭짓점의 수는 짝수

그래프의 종류

부분 그래프

• Subgraph
• 그래프 G = (V, E)가 있을 때, V'⊆V이고 E'⊆E인 그래프  G' = (V', E')
• 어떤 그래프 G에 포함되는 일부 꼭짓점과 모서리로만 그린 그래프

부분신장 그래프

• 어떤 그래프 G의 모든 꼭짓점을 포함하지만 모서리는 부분 포함한 그래프

평면 그래프

• Planar Graph
• 그래프 G = (V, E)를 평면에 그릴 때, 꼭짓점이 아닌 곳에서는 어떤 모서리도 교차하지 않는 그래프
• 오일러 공식
  • 연결된 평면 그래프 G에서 꼭짓점의 수를 v, 모서리의 수를 e, 영역의 수를 s라고 할 때 오일러 공식(v - e + s = 2)이 성립함
  • 영역: 모서리로 닫힌 부분과 바깥의 부분
  • 위의 공식을 증명하기 위해서는 모서리가 하나인 그래프와 둘 이상인 그래프를 나누어 고려해야 함

연결 그래프

• Connected Graph
• 그래프 G = (V, E) 내에 있는 임의의 꼭짓점 u, v 간에 경로가 있는 그래프
• 길(walk): 그래프 G = (V, E)에서 꼭짓점 vᵢ와 vᵢ₊₁에 근접하는 모서리를 eᵢ라고 했을 때, v₁에서 시작해서 vₖ에 도착하는 꼭짓점과 모서리의 나열
  • v₁, e₁, v₂, e₂, ... , eₖ₋₁, vₖ
  • v₁ → v₂ → ... → vₖ
• 경로(path): 그래프 G = (V, E)에 존재하는 임의의 꼭짓점 u, v 간의 길 중에서 같은 모서리를 두 번 이상 포함하지 않는 길

완전 그래프

• Complete Graph
• 그래프 G = (V, E) 내에 있는 모든 n개의 꼭짓점 사이에 모서리가 있는 그래프
• n개의 꼭짓점 모두에 대해 근접하는 모서리의 수가 n-1개, 즉 모든 꼭짓점의 차수가 d(vᵢ) = n-1인 그래프 kₙ

---

그래프의 표현

인접행렬

• Adjacency Matrix
• 그래프 G = (V, E)에서 |V| = n일 때 n×n의 행렬 [aᵢⱼ]로 나타내는 방법
• 인접행렬은 하나의 꼭짓점 집합에 대한 행렬이므로 항상 정사각행렬

인접리스트

• Adjacency List
• 그래프 G = (V, E)를 구성하는 각 꼭짓점에 인접하는 꼭짓점들을 연결리스트로 표현한 것
• 연결리스트는 노드의 연결로 표현되는데, 각 노드는 두 개의 필드로 첫 번째 필드는 데이터 필드, 두 번째 필드는 포인터 필드로 다음에 따라오는 노드의 주소를 가리킴
• 연결리스트의 마지막 노드의 포인터 필드에는 더 이상 연결될 노드가 없음을 의미하는 null 값으로 채워서 연결리스트를 마무리
• 노드 중에는 헤드라고 불리는 시작 노드가 있어서 리스트의 시작을 알림

---

오일러 & 해밀턴

• 순환(Cycle) or 회로(Circuit): 시작하는 꼭짓점과 끝나는 꼭짓점이 같은 경로
• 길이: 경로 또는 순환을 구성하는 변의 수

오일러 그래프

• 오일러 경로(Eulerian Path): 그래프 G = (V, E)의 모든 모서리를 꼭 한 번씩만 지나는 경로
• 오일러 순환/회로: 그래프 G = (V, E)의 꼭짓점 v에서 시작해 모든 모서리를 꼭 한 번씩만 지나 v로 되돌아오는 경로
• 오일러 그래프: 오일러 순환을 가지는 그래프 G = (V, E)
• 오일러 경로, 오일러 순환에서 꼭 기억해야 할 것은 꼭짓점에 상관없이 모든 변을 반드시 한 번씩 지나야 한다는 것
• 연결 그래프 G = (V, E)의 모든 꼭짓점의 차수가 짝수이면, 오일러 그래프의 필요충분조건이 됨
• 꼭짓점 중 차수가 홀인 꼭짓점의 수가 0 또는 2개이면, 오일러 경로를 갖기 위한 필요충분조건

해밀턴 그래프

• 해밀턴 경로(Hamiltonian Path): 그래프 G = (V, E)의 모든 꼭짓점을 꼭 한 번씩만 지나는 경로
• 해밀턴 순환/회로: 그래프 G = (V, E)의 꼭짓점 v에서 시작해 모든 꼭짓점을 꼭 한 번씩만 지나 v로 되돌아오는 경로
• 해밀턴 그래프: 해밀턴 순환을 가지는 그래프 G = (V, E)
• 오일러 경로, 오일러 순환과는 다르게 해밀턴 경로, 해밀턴 순환은 같은 모서리를 몇 번을 지나든 상관없이 꼭짓점들만 한 번씩 지나면 됨