완전그래프
위 그림과 같이 모든 정점 사이에 모서리를 갖는 그래프를 완전그래프라고 한다.
한마디로 모든 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... 의 그래프도 똑같이 표현할 수 있다.
'수학 > 이산수학' 카테고리의 다른 글
[이산수학] 그래프 이론 (0) | 2020.10.18 |
---|---|
[이산수학] RANK 구하기 (0) | 2020.10.18 |
[이산수학] 가우스 (조던) 소거법, (기약) 행 사다리꼴 (2) | 2020.10.16 |
[이산수학] 역행렬 구하기 - 수반행렬을 이용한 방법 (0) | 2020.10.03 |
[이산수학] 행렬식의 개념 - 그래서 3*3행렬식은? (0) | 2020.09.25 |