2. Representation, Sameness and Parts

이번 포스팅은 Graph Theory에 관하여 참고할만한 자료를 검색하던 중 맨체스터 대학교의 Discrete Math의 Lecture Note 자료를 얻게 되어 이를 바탕으로 공부하면서 정리한 것입니다.

Chap02 - Representation, Sameness and Parts

• Chap01 - Introduction에서는 전반적인 Graph Theory와 Graph 구조 및 종류에 대해 살펴보았다.

• 이번 Chap02에서는 Graph를 표현하는 방법, 두 그래프의 동일함을 의미하는 Isomorphism 그리고 Graph의 부분집합인 subgraph에 대해 알아보도록 하자.

2.1 Ways to represent a graph

• 먼저 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을 만드는 과정은 다음과 같다.

  1. 먼저, graph의 vertex ​에 대해 번호를 매긴다 : ​

  2. 다음의 규칙에 따라, ​ 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 ​를 나타낸 것이다.