그래프(Graph)

• 정의, 용어 정리
• 그래프 표현 방법
  • 인접 리스트(Adjacency Lists)
  • 인접 행렬(Adjacency Matrices)
  • 결합행렬(Incidence Matrices)
• 동형 그래프(Isomorphism of Graphs)
• 참고문헌

정의, 용어 정리

A graph \(G = (V,E)\) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.

• 그래프 \(G = (V, E)\)는 다음으로 구성된다.
  • \(V\): 정점(vertices 또는 nodes)의 집합.
  • \(E\): 모서리(간선)의 집합.
    • 각 모서리들은 두 개의 정점을 잇는다.

The set of vertices V of a graph G may be infinite. A graph with an infinite vertex set or an infinite number of edges is called an infinite graph, and in comparison, a graph with a finite vertex set and a finite edge set is called a finite graph.

• 정점들의 집합 V는 무한할 수 있다.
  • 무한한 정점 집합을 갖는 그래프를 무한 그래프(infinite graph)라 한다.
  • 유한한 정점 집합을 갖는 그래프를 유한 그래프(finite graph)라 한다.

A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices is called a simple graph.

• 두 정점을 연결하는 간선이 한 개만 있는 그래프를 단순 그래프(simple graph)라 한다.

Graphs that may have multiple edges connecting the same vertices are called multigraphs.

• 두 정점을 연결하는 간선이 여러 개 있는 그래프를 다중그래프(multi graph)라 한다.

Sometimes a communications link connects a data center with itself, perhaps a feedback loop for diagnostic purposes. Such a network is illustrated in Figure 3. To model this network we need to include edges that connect a vertex to itself. Such edges are called loops, and sometimes we may even have more than one loop at a vertex. Graphs that may include loops, and possibly multiple edges connecting the same pair of vertices or a vertex to itself, are sometimes called pseudographs.

• 자기 자신과 연결하는 간선을 갖는 정점이 있다.
  • 이런 간선을 루프(loop)라고 한다.
  • 루프와 다중 간선을 갖는 그래프를 의사 그래프(pseudographs)라 부른다.

A directed graph (or digraph) \((V,E)\) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair \((u, v)\) is said to start at u and end at v.

• 방향성 그래프(directed graph, digraph) \((V,E)\)는 다음으로 구성된다.
  • 공집합이 아닌 정점들의 집합 V.
  • 방향이 있는 간선(directed edges 또는 arcs)들의 집합 E.
    • 방향간선은 정점들의 순서쌍이다.
    • 순서쌍 \((u, v)\)는 \(u\)에서 출발해서 \(v\)에서 끝난다.
    • 화살표로 표기하면 알아보기 쉽다.

Two vertices u and v in an undirected graph G are called adjacent(or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.

• 비방향성 그래프에서
  • 하나의 간선 양쪽의 두 정점을 "인접(adjacent)" 또는 "이웃(neighbors)"이라 한다.
  • 이웃하는 두 정점을 연결하는 간선을 해당 정점에 붙어있다(incident)고도 하고, 두 정점을 연결한다(connect)고도 한다.
  • 연결된 두 정점을 끝점(endpoints)이라 부른다.

The set of all neighbors of a vertex v of G = (V,E), denoted by N(v), is called the neighborhood of v. If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A. So, \(N(A) = \bigcup_{ \nu ∈ A } N(\nu)\)

• 한 정점 \(\nu\)의 모든 이웃의 집합을 \(N(\nu)\)로 표기하고, 이를 \(\nu\)의 이웃(neighborhood of \(\nu\))이라 한다.
• \(N(A)\)는 \(A\) 집합의 한 원소에 인접한 모든 정점들의 집합이다.
  • 그러므로 \(N(A) = \bigcup_{ \nu ∈ A } N(\nu)\) 이다.

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by \(deg(v)\).

• 정점 하나에 붙어 있는 간선의 수를 정점의 차수(degree)라 부른다.
  • loop가 있으면 차수에 2를 더한다.
  • 정점 \(\nu\)의 차수는 \(deg(\nu)\)로 표기한다.
• 차수가 0 인 정점은 연결된 간선이 하나도 없으며, "고립되었다(isolated)"고 표현한다.
• 차수가 1 인 정점은 연결된 간선이 하나뿐이며, "늘어졌다(pendant: 목걸이)"고 표현한다.

THE HANDSHAKING THEOREM.
Let \(G = (V , E)\) be an undirected graph with m edges. Then
\(2m = \sum_{\nu ∈ V} deg(\nu)\)
(Note that this applies even if multiple edges and loops are present.)

• 악수 정리(Handshakiing Theorem)
  • 그래프 \(G=(V,E)\)가 m 개의 모서리를 갖는 비방향성 그래프라면,
    • \(2m = \sum_{\nu ∈ V} deg(\nu)\).
    • 이 정리는 다중 간선, 루프가 있을 때에도 성립한다.

악수 정리의 원리는 단순하다. 삼각형을 생각해보자. 삼각형의 모든 정점은 2개의 간선을 갖는다.

그렇다면 각 정점의 차수를 모두 더하면 \(2m = 2 + 2 + 2 = 6\)이 될 것이다.

그러므로 \(m=3\)이다. 당연히 삼각형의 변은 3개.

An undirected graph has an even number of vertices of odd degree.

• 비방향성 그래프에는 홀수 차수를 가진 정점들이 짝수 개 있다.

이는 다음과 같이 증명할 수 있다.

• \(V_1 =\) 짝수 차수를 가진 정점들의 집합
• \(V_2 =\) 홀수 차수를 가진 정점들의 집합

그렇다면 악수 정리를 사용해 식을 다음과 같이 꾸밀 수 있다.

그런데 \(\sum_{ \nu ∈ V_1 } deg(\nu)\)의 \(deg(\nu)\)는 짝수이므로, \(\sum_{ \nu ∈ V_1 } deg(\nu)\)도 짝수이다.

그리고 \(2m\)도 짝수이므로 다음과 같은 모양이 된다.

그러므로 \(\sum_{ \nu ∈ V_2 } deg(\nu)\)도 짝수가 된다.

그런데 \(V_2\)는 홀수 차수를 가진 정점들의 집합이므로 \(deg(\nu)\)는 홀수다.

따라서 \(\sum_{ \nu ∈ V_2 } \text{홀수}\)인 셈이므로, \(V_2\)의 원소의 개수는 짝수여야 한다.

그러므로 홀수 차수의 정점들의 수는 짝수 개이다.

When \((u, v)\) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of \((u, v)\), and v is called the terminal or end vertex of \((u, v)\). The initial vertex and terminal vertex of a loop are the same.

• 방향성 그래프의 간선 \((u, v)\)에 대하여
  • 간선 u 는 \(\nu\)에 인접한다고 한다.
  • 정점 \(\nu\)는 u 로부터 인접된다고 한다.
  • 정점 u 는 시작 정점이라 부른다.
  • 정점 \(\nu\)는 종료 또는 끝 정점이라 부른다.
  • 루프의 경우, 시작 정점과 끝 정점이 같다.

In a graph with directed edges the in-degree of a vertex v, denoted by \(deg^−(v)\), is the number of edges with v as their terminal vertex. The out-degree of v, denoted by \(deg^+(v)\), is the number of edges with v as their initial vertex. (Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.)

• 방향성 그래프에서 정점 \(\nu\)의 입력차수(in-degree)는 \(deg^-(\nu)\)로 표기한다.
• 방향성 그래프에서 정점 \(\nu\)의 출력차수(in-degree)는 \(deg^+(\nu)\)로 표기한다.
• 루프가 있으면 정점의 입력차수와 출력차수에 각각 1씩 추가한다.

Let \(G = (V , E)\) be a graph with directed edges. The
\(\sum_{ \nu ∈ V } deg^{-}(\nu) = \sum_{ \nu ∈ V } deg^{+}(\nu) = \vert E \vert\)

• 방향성 그래프에서 입력차수의 총합과 출력차수의 총합, 그리고 모든 간선의 수는 같다.

A complete graph on n vertices, denoted by \(K_n\), is a simple graph that contains exactly one edge between each pair of distinct vertices.

• 완전 그래프(Complete graph)는 각 정점들이 하나의 간선으로 연결된 단순 그래프이다.
• 모든 정점이 다른 나머지 정점들과 다 연결이 되어 있다.

A cycle \(C_n, n ≥ 3\), consists of n vertices \(\{v_1, v_2\}, \{v_2, v_3\}, ... , \{v_{n−1}, v_n\}\), and \(\{v_n, v_1\}\).

• 사이클(Cycle)은 다음과 같이 \(v_i, v_{i+1}\)이 연결된 형태의 그래프이다.
• 바퀴 모양이다.

We obtain a wheel \(W_n\) when we add an additional vertex to a cycle \(C_n\), for \(n ≥ 3\), and connect this new vertex to each of the n vertices in \(C_n\), by new edges.

• 휠(Wheel)은 한 정점이 다른 모든 정점과 연결되어 있다.
• 가운데에 축이 있는 바퀴 모양이다.

An n-dimensional hypercube, or n-cube, denoted by \(Q_n\), is a graph that has vertices representing the \(2^n\) bit strings of length n. Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position.

• n 큐브(n-Cubes)는 길이 n의 \(2^n\)개의 비트 스트링을 나타내는 정점들을 갖는 그래프.
  • 두 정점이 서로 인접해 있다면 이 두 정점의 비트 스트링은 1개의 비트만 다르다.

Bipartite Graphs.
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets \(V_1\) and \(V_2\) such that every edge in the graph connects a vertex in \(V_1\) and a vertex in \(V_2\) (so that no edge in G connects either two vertices in \(V_1\) or two vertices in \(V_2\)). When this condition holds, we call the pair \((V_1, V_2)\) a bipartition of the vertex set V of G.

• 단순 그래프에서 정점들의 집합 V가 교집합이 없는 집합 \(V_1\), \(V_2\)로 나뉘고, 그래프의 모든 간선이 \(V_1\)의 한 정점과 \(V_2\)의 한 정점을 연결한다면, 이 그래프를 이분되었다(bipartited)고 한다.
  • 단, \(V_1\)의 정점과 \(V_1\)의 정점을 연결하는 간선은 없다.
  • 단, \(V_2\)의 정점과 \(V_2\)의 정점을 연결하는 간선은 없다.

A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.

• 이분 그래프의 필요충분조건
  • 두 인접한 정점들이 같은 색깔을 갖지 않도록 두 가지 색깔로 그래프의 모든 정점을 색칠할 수 있어야 한다.

A complete bipartite graph \(K_{m,n}\) is a graph that has its vertex set partitioned into two subsets of m and n vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset.

• 완전 이분 그래프 \(K_{m,n}\)
  • 정점의 집합이 m개, n개의 정점을 갖는 두 부분집합으로 나뉠 수 있는 그래프.

HALL’S MARRIAGE THEOREM.
The bipartite graph \(G = (V , E)\) with bipartition \((V_1,V_2)\) has a complete matching from \(V_1\) to \(V_2\) if and only if \(|N(A)| ≥ |A|\) for all subsets A of \(V_1\).

• 이분 그래프가 \(V_1\)에서 \(V_2\)로 완전 매칭일 필요충분조건은 다음과 같다.
  • \(V_1\)의 모든 부분집합 A 에 대해 \(\vert N(A) \vert ≥ \vert A \vert\) 이다.
    • 참고: N(A)는 A 집합의 한 원소에 인접한 모든 정점들의 집합이다.
    • 참고: |A|는 집합 A의 원소의 개수.

A matching M in a simple graph \(G = (V,E)\) is a subset of the set E of edges of the graph such that no two edges are incident with the same vertex. In other words, a matching is a subset of edges such that if {s,t} and {u,v} are distinct edges of the matching, then s, t, u, and v are distinct. A vertex that is the endpoint of an edge of a matching M is said to be matched in M; otherwise it is said to be unmatched.

A maximum matching is a matching with the largest number of edges.

We say that a matching M in a bipartite graph \(G = (V,E)\) with bipartition \((V_1,V_2)\) is a complete matching from \(V_1\) to \(V_2\) if every vertex in \(V_1\) is the endpoint of an edge in the matching, or equivalently, if \(\vert M \vert = \vert V1 \vert\).

• Matching M은 그래프에서 연결된 정점을 공유하지 않는 간선들의 집합이다.
  • 매칭 간선 \({s, t}\)와 간선 \({u, v}\)가 있을 때, \(s, t, u, v\) 는 서로 다른 정점이다.
• 최대 매칭(Maximum matching).
  • 간선의 수가 최대인 매칭.
• 완전 매칭(complete matching).
  • \(V_1\)의 모든 정점들이 매칭되었거나, \(\vert M \vert = \vert V_1 \vert\) 인 경우를 \(V_1\)에서 \(V_2\)로의 완전 매칭이라 한다.

A subgraph of a graph \(G = (V,E)\) is a graph \(H = (W,F)\), where \(W ⊆ V\) and \(F ⊆ E\). A subgraph H of G is a proper subgraph of G if \(H \ne G\).

• 그래프 \(G=(V,E)\)의 부 그래프(subgraph)는 \(H = (W,F)\).
  • \(W ⊆ V\).
  • \(F ⊆ E\).
• \(H \ne G\) 이면 진 부그래프(proper subgraph)이다.

Let \(G = (V , E)\) be a simple graph. The subgraph induced by a subset W of the vertex set V is the graph \((W, F)\), where the edge set F contains an edge in E if and only if both endpoints of this edge are in W .

• 유도된 그래프(subgraph induced): 정점의 집합 V 의 부분집합 W 를 통해 유도된 부 그래프.

The union of two simple graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) is the simple graph with vertexset\(V_1 ∪ V_2\) and edge set \(E_1 ∪ E_2\). The union of \(G_1\) and \(G_2\) is denoted by \(G_1 ∪ G_2\).

• 그래프 합집합
  • 두 그래프의 합집합은 두 그래프의 정점들의 집합의 합집합과 두 그래프의 간선들의 합집합을 갖는 단순 그래프이다.

그래프 표현 방법

인접 리스트(Adjacency Lists)

• 각 정점별로 인접한 정점을 나열하는 방법이다.

• 방향성 그래프의 경우, 시작 정점별로 종료 정점들을 나열한다.

인접 행렬(Adjacency Matrices)

만약 다음과 같은 그래프가 있다면…

다음과 같이 표로 나타낼 수 있다.

이 표를 그대로 0, 1을 사용한 행렬로 나타내면 된다.

결합행렬(Incidence Matrices)

정점과 간선의 연결을 표시하는 방법이다.

동형 그래프(Isomorphism of Graphs)

The simple graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) are isomorphic if there exists a one-to-one and onto function \(f\) from \(V_1\) to \(V_2\) with the property that a and b are adjacent in \(G_1\) if and only if \(f(a)\) and \(f(b)\) are adjacent in \(G_2\), for all a and b in \(V_1\). Such a function \(f\) is called an isomorphism\(^*\). Two simple graphs that are not isomorphic are called nonisomorphic.

• 두 단순 그래프 \(G_1 = (V_1, E_1)\)와 \(G_2 = (V_2, E_2)\).
  • \(V_1\) 에서 \(V_2\)로의 함수 f 가 전단사 함수(일대일 대응)이고, \(V_1\)의 모든 a,b에 대해 a,b가 \(G_1\)에서 인접한다면 \(f(a), f(b)\)는 \(G_2\)에서 인접하고 그 역도 성립하면 함수 f 를 동형(isomorphic)이라 부른다.
  • 동형이 아닌 두 산순 그래프를 비동형(nonisomorphic)이라 부른다.
• isomorphism: iso(equal, 같다), morphe(form, 형태).

참고문헌

• Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등 저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일