EXCELSIOR

2. Representation, Sameness and Parts 본문

Graph Theory

2. Representation, Sameness and Parts

Excelsior-JH 2020. 3. 1. 20:34

이번 포스팅은 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 도 마찬가지로 undirecteddirected 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 listpredecessorsuccessor 각각에 대해 나타내야 한다.

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 를 나타낸 것이다.


'Graph Theory' 카테고리의 다른 글

3. Graph Colouring  (1) 2020.03.22
2. Representation, Sameness and Parts  (0) 2020.03.01
1. Introduction  (0) 2020.02.24
0 Comments
댓글쓰기 폼