그래프 이론과 그 활용(1)

[임꺽정]

Regular and Bipartite Graph

 

 앞에서 학습한 그래프의 개념과 정의에 이어서 필요한 여러 개념을 계속하여 학습하기로 한다.

  다음의 강의 내용은 앞에서와 같이 그래프이론에 대한 표준적인 교재들을 참고하여 학습하기 바랍니다.

 

먼저 다음의 정의를 생각해 봅시다.

 

 

정의 1.  V는 n개의 정점을 갖는 집합이라 가정할 때, V 를 정점으로 하는 완전그래프 (complete graph)란  임의의 a≠b인 a,b∈V 에 대하여 모서리 (a,b)가 반드시 존재하는 루프가 없는 그래프를 의미하며,  K_n이라고 나타낸다.

 

 

 

 

예제 1.  n개의 정점을 갖는 완전 그래프는 K_n으로 표시하며,  Kn은 n(n-1)/2개의 모서리를 갖는다. 실제로 조합의 수를 이용하여 구할 수 있다.아래의 그림은  n=2,3,5,8인 경우의  완전그래프 K_n을 나타낸다.

 

   그래프 G는 n개의 정점을 갖는 루프가 없는 그래프라고 하자.  그래프 G의  complement인 그래프는 그래프 G에 속하지 않는 모든 모서리들과 정점들로 구성된 완전그래프 K_n의  부분그래프를 의미한다.

 The degree (차수) of a vertex in a graph is the number of edges that touch it. The number on each vertex of this graph is the degree of that vertex.

다음 그래프에서 정점에 표시된 수는 각 정점의 degree(차수)를 나타낸다.

                      

 

다음은 graph이론의 여러 그래프 중에서 가장 이상적인 그래프를 나타 낸다.

 

 

정의 2.  그래프G = (V, E)의 모든 정점의  차수(degree)가 같다면 , 그 그래프를 정규 그래프 (regular graph)라고 한다.

 

 

 

   

 

정의 3.  그래프 G = (V, E)가  V=V₁∪ V₂ 과 V₁∩V₂= Ф인 두 개의 집합 V₁과 V₂로 분할된 그래프라고 하고,  분할된  집합 V₁와 V₂ 의 각 정점을 갖는 모서리가 존재한다면, 이 그래프 G를 이분그래프(bipartite graph)라고 한다. 또, V₁과 V₂에 존재하는 각 모든 정점들 사이에 모서리들이 모두 존재할 경우, 그래프 G를 완전이분그래프 (complete bipartite graph)라고 한다.

 

 

 

   

 

예제 2. V₁의 정점의 개수를 m, V₂의 정점의 개수를 n이라 가정할 경우, 완전 이분그래프를 K_m,n으로 나타낸다.

 

 

 

 

예제 3.  다음 그림 5의 그래프들처럼 모든 정점의  차수가 모두 k인 그래프를 k-정규그래프라고 한다. n개의 정점을 갖는 완전그래프 K_n은  분명히 (n-1) -정규그래프이다.

 

  

 

In a graph, the neighbors of a vertex are all the vertices which are connected to that vertex by a single edge. A dominating set for a graph is a set of vertices whose neighbors, along with themselves, constitute all the vertices in the graph.

(The Ice Cream Stands Problem is an example of a dominating set problem.