[ 이산 수학 ] 17. 그래프

그래프

: 인접 Adjacent

 

G = ( V , E ) 에서 꼭짓점 u,v를 연결한 모서리 e가 있을 때 

       u와 v는 서로 인접하다고 말한다.

 

---

Multi 그래프

 

: 두 vertex ( node)  사이에 두 개 이상의 Edge가 있는 그래프

 

참고 : pseudograph = Multi 그래프 + loop

 

 

---

 

Direct 그래프

 

화살표로 모서리를 표현 , Vertex간의 순서나 관계를 알 수 있다.

 

 

 

Direct Multi 그래프

 

Direct에다가 Multi. 즉 화살표로 표시된 edge가 두 vertex 사이에 두 개 이상 있는 것. 

 

---

 

그래프들의 특징 분석

 

 

1) 두 개의 vertex가 edge하나로 연결되어 있을 때,

두 vertex는 'adjacent' or 'neighbors'라고 한다.

 

2) Vertex v의 이웃 집합을 N(v)라고 하고

  A가 N(v)의 부분 집합일 때 N(A)는 A에 속한 최소한 하나의 정점과 연결된 모든 정점의 집합

 

3)  degree of a vertex: 그냥 알아야 할 건, loop는 deg 계산할 때 2번 카운트

 

 

예제)

 

 

 

모든 간선의 합은 짝수다. 

 

증명

 

악수는 두 사람이서 할 수 있다.

악수한 사람의 총 합을 구하면 짝수다.

 

A,B 가 이어진 걸 보면 A에서도 한 번, B에서도 한 번 카운트되어서 그런가보다.

 

문제)

 

 

이해하자마자 밑에 바로 설명나옴

 

10개의 vertex의 degree가 6이라고 한다.

그럼 10 * 6으로 60개의 edge가 있다고 할텐데, a~b edge는 a에서도 , b에서도 카운트 되기 때문에

반으로 나누어야 실제 edge 개수로 볼 수 있다.

 

 

 

 

 

Direct에서는 들어오는 방향의 edge와 나가는 방향의 edge 모두 고려해야한다.

아래 예시를 보자

 

 

 

---

들어오는 것만큼 나가는 애들도 있으니 

나가는 deg와 들어오는 deg 개수는 같다.

 

---

완전 그래프

: 모든 vertex간에 edge가 존재하는 것

 

 

n개의 노드가 있을 때 완전 그래프라면

● edge의 개수는 nC2

● 하나의 vertex의 deg는 n-1

 

 

추가로 보면 될 것들 (중요하진 않을 듯)

 

1) cycle

 

 

2) wheel : Cycle 그래프에서 가장 중심에 하나의 vertex를 더하고

                그 vertex와 모든 edge를 더하면 나오는 모양

 

 

 

 

3) Bipartite Graphs (이분 그래프)

 

 

 

---

 

그래프의 합 연산 도 가능함

 

 

 

(참고)

https://m.blog.naver.com/ndb796/221027866623

오늘 한 내용 다 있음

 

 

(출처)

한동대학교 최희열교수님 - 이산수학