[이산수학] 그래프 이론 - 여러가지 그래프 종류

완전그래프

위 그림과 같이 모든 정점 사이에 모서리를 갖는 그래프를 완전그래프라고 한다.
한마디로 모든 Vertex가 서로 연결되어 있다고 보면 된다. 이 경우 n(n-1)/2 가 모서리의 개수가 된다.

 

싸이클 그래프

위 그림처럼 가장자리끼리만 모서리로 연결된 그래프를 Cycle 그래프라고 한다.

n이 모서리의 개수가 된다.

 

휠 그래프

 

위 그림처럼 도형 가운데에 정점이 하나 들어가서 각 정점을 잇는 형태의 그래프다.

이 경우 모서리의 개수는 n*2가 된다.

 

N-CUBE 그래프

다차원적으로 복잡한 관계를 컴퓨터에게 전달해야 할 때 각 정점에 규칙을 부여할 필요가 있다.

 

Q1, Q2, Q3은 각각 1차원~3차원의 그래프를 나타낸 것이다. 얼핏 복잡해보이지만 알고보면 쉽다.

 

[Q1 그래프]

정점이 2개로, 0과 1로 구분하면 된다.

 

[Q2 그래프]

Q2는 Q1에서 한 차원 확장되었다. Q1 그래프가 아래에 있고 그 위로 Q1 모양의 그래프가 새롭게 생겨난 것과 같다.

이제 단순하게 '아래는 0을 추가', '위에는 1을 추가' 한다고 생각해보자.

기존 정점 {'0', '1'} 은 아래에 있으니 0을 추가해 '00', '01' 으로 만든다. 그리고 그 위에 생겨날 정점은 기존 정점 {'0', '1'}에 대해 1을 추가해 '10', '11' 으로 만든다.

 

[Q3 그래프]

 

다시 한 차원 확장되었다. Q2 그래프가 아래(바닥) 에 있고, 그 위로 Q2 모양의 그래프가 새롭게 생겨난 것과 같다.

이제 다시 단순하게 '아래는 0을 추가', '위에는 1을 추가' 한다고 생각해보자.

기존 정점 {'00' , '01', '10', '11'} 은 아래에 있으니 0을 추가해 '000', '001', '110', '111'로 만든다. 그리고 그 위에 생겨나는 정점은 기존 정점 {'00' , '01', '10', '11'} 에 대해 1을 추가해 '100', '101', '110', '111'로 만든다.

 

.

.

.

 

 

이 원리를 생각하면 Q4, Q5, Q6... 의 그래프도 똑같이 표현할 수 있다. 

Q4 그래프를 표현한 모습