2. Representation, Sameness and Parts
Discrete Math의 Lecture Note 자료를 얻게 되어 이를 바탕으로 공부하면서 정리한 것입니다.
Chap02 - Representation, Sameness and Parts
Chap01 - Introduction에서는 전반적인 Graph Theory와 Graph 구조 및 종류에 대해 살펴보았다.
이번 Chap02에서는 Graph를 표현하는 방법, 두 그래프의 동일함을 의미하는 Isomorphism 그리고 Graph의 부분집합인 subgraph에 대해 알아보도록 하자.
먼저 graph를 표현하는 방법에 대해 살펴보자.
graph는 여러 가지 방법으로 나타낼 수 있는데, 여기서는 Edge list, Adjacency matrix, Adjacency list 이렇게 3가지 방법에 대해 알아보도록 하자.
2.1.1 Edge lists
graph를 표현(representation)할 때, edge의 리스트인 로 표현할 수 있다.
예를 들어, graph 다음과 같이 edge list를 이용해 나타낼 수 있다.
이 때, graph 가 undirected graph인지 digraph인지에 따라 아래의 그림과 같이 2개의 그래프로 나타나게 된다.
2.1.2 Adjacency matrix
graph를 표현하는 두 번째 방법으로는 adjacency matrix(인접행렬) 를 이용하는 것이다. adjacency matrix을 만드는 과정은 다음과 같다.
먼저, graph의 vertex 에 대해 번호를 매긴다 :
다음의 규칙에 따라, adjacency matrix 를 만든다:
adjacency matrix 도 마찬가지로 undirected와 directed graph에 따라 아래의 그림과 같이 달라진다.
adjacency matrix 는 다음의 성질을 가진다:
는 unique하지 않다. vertex 에 대해 번호를 어떻게 매기냐에 따라 가 변하기 때문이다.
가 undirected 하면, adjacency matrix 는 대칭(symmetric)이다. 그 이유는 edge간의 관계의 순서가 없으므로, 이기 때문이다.
graph 가 loop(또는 self-loop)가 없다면, 에 대해 이다. 즉, 의 대각성분(diagonal)은 0이다.
vertex 와 사이에 여러개의 edge를 가지는 multigraph인 경우에는 의 원소는 다음의 식과 같이 edge의 개수로 표기한다.
2.1.3 Adjacency lists
세 번째 방법으로는 각 vertex 에 대한 adjacency list로 graph를 표현하는 방법이 있다.
먼저, undirected graph에서의 adjacency list를 살펴보자.
Definition 2.1
In an undirected graph the adjacency list associated with a vertex is te set defined by
위의 정의를 토대로 undirected graph에서의 adjancency list를 다음의 예제와 같이 표현할 수 있다.
이제, digraph 에 대해서 살펴보자. digraph에서의 adjacency list는 predecessor와 successor 각각에 대해 나타내야 한다.
Definition 2.2
In an directed graph the predecessor list of a vetex is the set defined by
while the successor list of is the set defined by
2.2 When are two graphs the same?
이번에는 두 graph가 (거의) 같을 때를 일컫는 용어인 isomorphism에 대해 알아보도록 하자.
isomorphism(동형사상)이란 "equal"을 의미하는 그리스어 iso와 "to form"을 뜻하는 morphosis 로 부터 나온 단어이다.
공식적으로는 isomorphism은 bijective morphism을 뜻한다.
bijective morphism이란 우리가 선형대수학에서 배웠던 전단사(bijection 또는 one-to-one)를 의미한다.
이를 아래의 그림과 같이 나타낼 수 있다(출처: wolfram MathWorld).
"와 가 isomorphic 하다."라는 것을 수식으로 나타내면 다음과 같이 나타낼 수 있다.
이러한 isomorphism개념을 Graph Theory에서 살펴보도록 하자.
Definition 2.3
Two graphs and are said to be isomorphic if there exists a bijection such that the edge if and only if .
위의 정의를 토대로 아래의 3개의 graph는 서로 isomorphic 하다는 것을 확인할 수 있다.
2개의 graph가 서로 isomorphic할 때, 가지는 성질은 다음과 같다.
Proposition 2.4
If and are isomorphic then and .
Proposition 2.5
If and are isomorphic and is the bijection that establishes the isomorphism, then for every and for every .
두 graph가 isomorphic한지 알아볼 수 있는 또 다른 방법은 degree sequence를 이용하여 확인할 수 있다.
Definition 2.6
The degree sequence of an undirected graph is a list of the degree of the vertieces, arranged in ascending(또는 descending) order.
위의 정의를 토대로 아래의 예시와 같이 각 graph에 대해 degree sequence를 다음과 같이 나타낼 수 있다.
Proposition 2.7
If and are isomorphic then they have the same degree sequence.
하지만, 두 graph가 같은 degree sequence를 가진다고 해도, 반드시 isomorphic한 것은 아니다.
아래의 예시와 같이 degree sequence는 으로 같지만 isomorphic하지 않을 수 있다.
2.3 Terms for parts of graphs
마지막으로, 부분 그래프인 subgraph에 대해서 살펴보도록 하자.
subgraph는 다음과 같이 두 가지 방법으로 정의할 수 있다.
Definition 2.8
A subgraph of a graph is a graph where and .
or
Definition 2.9
Given a graph and a subset of its vertices , the subgraph induced by is the subgraph where
아래의 예시는 맨 왼쪽의 graph 에 대하여 subgraph 를 나타낸 것이다.
