[Discrete Mathematics] Graph Theory

1. Introduction

그림 8.1.2에는 Vertex가 10개, Edge는 13개가 있다.

 

그래프graph(또는 무방향 그래프undirected graph) G는 정점vertex(또는 노드node)으로 이루어진 집합 V와 간선edge(또는 호arc)으로 이루어진 집합 E로 구성된다. 각 간선 e ∈ E는 순서가 없는 정점 쌍과 연결된다. v와 w라는 정점에 고유한 간선 e가 있다면, 우리는 e = (v, w) 또는 e = (w, v)로 쓴다. 이 맥락에서 (v, w)는 무방향 그래프에서 v와 w 사이의 간선을 나타내며, 순서 쌍이 아니다.

방향 그래프directed graph(또는 다이그래프digraph) G는 정점(또는 노드)으로 이루어진 집합 V와 간선(또는 호)으로 이루어진 집합 E로 구성된다. 이 경우 각 간선 e ∈ E는 정점의 순서 쌍과 연결된다. 만약 (v, w)라는 순서 쌍에 고유한 간선 e가 있다면, 우리는 e = (v, w)로 쓰며, 이는 v에서 w로 향하는 간선을 나타낸다.

그래프(무방향 또는 방향)의 간선 e가 정점 v와 w 쌍과 연결되어 있다면, 이 간선은 v와 w에 대해 인접incident하다고 하며, v와 w는 e에 대해 인접한 정점adjacent vertices이라고 한다.

G가 정점 V와 간선 E로 구성된 그래프(무방향 또는 방향)라면, 우리는 G = (V, E)라고 쓴다. 특별히 명시되지 않는 한, 집합 E와 V는 유한한 것으로 가정하며, V는 비어 있지 않은 것으로 가정한다.

Edges

• e= (v,w)
  • e is said to be incident on v and w.
  • v and w are said to be incident on e
  • v and w are said to be adjacent vertices 
• Isolated vertex = a vertex without incident edges

Special Edges

• Parallel edges
  • Two or more edges joining a pair of vertices
  • in the example, a and b are joined by two 
    parallel edges 
• Loops
  • An edge that starts and ends at the same vertex In the example, vertex d has a loop

Special Graph

• Simple graph 
  • A graph neither loops nor parallel edges. 
• Weighted graph
  • A graph where each edge is assigned a numerical label or “weight”.
  • weight of edge
• Directed graph (Digraph)
  • if each edge has been associated with an ordered pair of vertices, i.e. each edge has a direction

Paths

• path
  • If we start at a vertex v0, travel along an edge to vertex v1, travel along another edge to vertex v2, and so on,  and eventually arrive at vertex vn, we  call the complete tour a path from v0 to vn
  • (예) p = (v5 v2 v4 v1) 

• length of a path 
  • undirected graph G1
    • The number of edges in the path
    • path length of p = 3 (v5-v2-v4-v1)
  • weighted graph G2
    • The sum of the weights of the edges in the path
    • path length of p = 17 (8+4+5)

Bipartite Graph

A graph G = (V, E) is bipartite if there exist subsets V₁ and V₂ (either possibly empty) of V such that
V₁ ∩ V₂ = ∅, V₁ ∪ V₂ = V, and each edge in E is incident on one vertex in V₁ and one vertex in V₂.

This figure is bipartite!

The graph above is bipartite since if we let V₁ = {v1, v2, v3} and V₂ = {v4, v5}, each edge is incident on one vertex in V₁ and one vertex in V₂.

This figure is not bipartite.

The complete bipartite graph on m and n vertices, denoted Km,n, is the simple graph whose vertex set is partitioned into sets V1 with m vertices and V2 with n vertices in which the edge set consists of all edges of the form (v1, v2) with v1 ∈ V1 and v2 ∈ V2.

The complete bipartite graph K₂,₄

---

2. Representations of Graphs

Adjacency matrix (인접 행렬)

• Rows and columns are labeled with ordered vertices
• write a 1 if there is an edge between the row vertex and the column vertex, and 0 if no edge exists between them

If A is the adjacency matrix of a simple graph, the ij-th entry of An is equal to the number of paths of length n from vertex i to vertex j for n = 1, 2,... .

 

위 그림에서 A⁴ [d][e] = 6인데, 이는 이것은 d에서 e로 가는 길이가 4인 path가 6개가 있다는 의미이다.

Incidence matrix (결합 행렬)

• Label rows with vertices
• Label columns with edges
• 1 if an edge is incident to a vertex, 0 otherwise

v2행 e7열을 보면 Self-loop도 1로 표기한다는 것을 확인할 수 있다.

---

3. A Shortest-Path Algorithm

Dijkstra's algorithm finds the length of the shortest path from a single vertex to any other vertex in a connected weighted graph.

dijkstra(w, a,z, L) {
	L(a) = 0
	for all vertices x ̸= a
		L(x) = ∞
		T = set of all vertices
		// T is the set of vertices whose shortest distance from a has not been found
		while (z ∈ T) {
			choose v ∈ T with minimum L(v)
			T = T − {v}
			for each x ∈ T adjacent to v
				L(x) = min{L(x), L(v) + w(v, x)}
			}
	}

L(b)=min {∞, 0+2} = 2 / L(f)=min {∞ , 0+1} = 1

Dijkstra’s shortest-path algorithm correctly finds the length of a shortest path from a to z.