Spanning Tree

Definition

Subgraph that contains all vertices of the original graph and is a tree.

• 즉, 기존 그래프의 모든 노드들을 최소한의 엣지로 연결한 그래프. 사이클 X.
• ST는 여러 그래프를 가질 수 있다.

---

Minimum Spanning Tree

• ST중에서 각 edge weight들의 합을 구했을 때, 가장 작게 나오도록 하는 그래프.
• Useful in constructing networks.
• Not unique.
• Prim's algorithm, Kruskal's algorithm.

---

Prim's Algorithm

Basic Idea

• MST를 만들기 위해 vertex를 하나씩 추가하는 방식.
• Keep track of
  • U : the set of vertices included in the MST so far.
  • V - U : the set of vertices not in the MST yet.

Procedure

• Begin with U = {v_0}.
• At each step
  • Loot at all the vertices in V - U.
  • Choose v_j in U with the cheapest edge <v_i, v_j>, where v_j in V - U.
  • Add v_j to U unless v_j creates a cycle.
• 위 과정을 노드 갯수만큼 한 뒤엔 MST 완성.

Key Procedure

1. V - U에 있는 vertex중에서 U의 임의의 vertex와 연결된 가장 싼 edge와 연결된 것을 찾는다.
2. V - U에 있는 vertices를 priority queue로 유지한다. 그래야 가장 적은 cost로 연결할 수 있는 vertex를 효율적으로 뽑아낼 수 있다.
3. priority queue 안의 vertex v의 우선 순위는 'v와 some vertex in U를 연결하는 데에 가장 싼 edge'이다.
4. 만약 그런 edge가 없다면, v의 우선 순위는 inf.
5. vertex의 priority edge도 저장한다. 그래야 vertex가 PQ에서 삭제됐을 때, 그 저장된 edge가 ST edge가 된다.

Goal

• A cheapest edge : the lowest cost is the highest priority
• Use a min heap

---

Kruskal's Algorithm

Main idea

• Prim's algorithm과 달리, 매 스텝 edge를 하나씩 추가하는 방법을 취한다.

Procedure

1. 그래프가 주어졌을 때, 모든 edge들을 전부 지우고 vertices만 고려한다. 이 때, vertices는 각각 tree라고 볼 수 있다. 그리고 이 vertices의 집합은 forest F이다.
2. 원래 그래프에 있던 모든 edge들의 집합을 S로 한다. S는 nonempty, F는 아직 spanning되지 않음.
   • Remove an edge with minimum weight from S.
   • If that edge connects two different trees, then add it to the forest, combining two trees into a single tree.
   • Otherwise discard that edge.
3. At the termination of the algorithm, the forest forms a minimum spanning forest of the graph.

---

Analysis of MST Algorithms

Greedy Algorithm

• 각 단계마다 locally optimal choice를 한다.
• No backtracking
• 하지만, 어쨌든 해는 최적해.

Time complexity

Prim's alg : O(|E| log |V|) or O(|V|^2)

• O(|V|^2) with adjacency matrix
• O(|E| log |V|) with binary heap and adjacency list.
• O(|E| + |V|log|V|) with Fibonacci heap(pass) and adjacency list.

Kruskal's alg : O(|E| log|V|)

---

Hamiltonian Cycle

• 모든 vertex를 정확히 한 번만 방문해서 cycle을 만들게 하는 방법.

Traveling Salesperson Problem (TSP)

Definition

• The problem of finding the minimum cost Hamiltonian cycle in a weighted graph.

Properties

• Intractable problem
  • NP : There's no polynomial time algorithm.
  • Many other problems are in this class.
• Time complexity of TSP >> O(n^k), where n is the number of vertices.
• Time complexity of naive algorithm : O(n!)
• T.c of the best known algorithm : O(2^n)

Greedy algorithm

• T.c : O(n^2)
• Not neccesarily optimal, but typically close to optimal in practice.