차별성함수

두 개의 정점이 두어졌을 때 v = (p1, p2, p3) 를 가지고 있고 w = (q1, q2, q3)를 가지고 있을 때 v정점과 w정점의 특성이 있을 때 차별성 함수는 다음과 같이 계산을 할 수 있습니다. 

 

차별성 함수 값은 v와 w 간의 차이를 나타내는 척도가 됩니다. 

 

N이라는 값을 하나 고정을 시키는데 이 값을 고정시키고 나면 간선을 표기할 때 s(v,w) < N 그러면 정점 사이의 간선을 표기하면 됩니다. 이것이 간선을 주어주는 조건입니다. 

 

두 정점 v와 w 사이의 간선이 있다라는 것은 같은 클래스에 속한다는 것입니다. 이는 두 프로그램은 같은 클래스로 정의될 수 있다는 것입니다. 

 

완전그래프

완전그래프 Kn은 n개의 정점을 가진 심플 그래프라고 볼 수 있습니다. 한가지 특징은 하나의 간선으로 모든 정점이 결합되는 것을 완전그래프라고 합니다. 

즉 모든 정점이 하나의 간선으로 연결되는 것은 완전그래프입니다. 

 

이분그래프

정점이 v1, v2로 분할이 될 때 v1이 m개, v2가 n개라고 할 때 둘의 교집합은 공집합, 같은 subset에 있는 두 정점 사이에는 간선이 존재하지 않으면 이분그래프라고 정의합니다.

 

완전 이분그래프

v1와 v2 사이에 항상 간선이 존재하면 완전 이분그래프라고 볼 수 있습니다. 

 

부분 그래프

 

단순경로, 싸이클, 단순싸이클

단순 경로라는 것은 V에서 W로의 경로에서 중복된 경로를 가지지 않는 경로입니다. 

 

싸이클은 V에서 V로의 길이가 0이 아닌 경로를 말합니다. 중복된 간선을 가지지 않는 경로입니다. 

 

단순 싸이클은 V에서 V로의 싸이클에서 중복되는 정점을 가지지 않는 simple cycle이며 출발과 도착을 제외하고 중복된 정점을 가지지 않아야 합니다. 

 

오일러 사이클

어떤 한 지점에서 출발해서 되돌아오는데 정확하게 한번 건너서 되돌아 올 수 있느냐는 것입니다. 

 

그래프 G가 오일러 사이클을 가진다고 하면 연결된 그래프이면서 모든 정점이 짝수 차수를 가져야 합니다. 그렇다면 오일러 사이클을 가진다고 볼 수 있습니다. 

 

해밀턴 퍼즐 

다음과 같은 12면체가 주어졌을 때 각 도시를 연결하는 도로를 표시한 것이 12면체가 있습니다. 이 해밀턴 퍼즐은 어떤 한 지점에서 출발해서 각 도시를 각 한번 방문하는 싸이클을 찾는 것이 해밀턴 퍼즐입니다. 

 

그래프 G의 모든 정점을 각 한번 방문하는 것이 해밀턴 사이클입니다. 

 

G가 해밀턴 사이클을 가진다고 하면 해밀턴 그래프라고 정의를 합니다. 

 

해밀턴 사이클의 특징

7개의 정점을 가진 그래프에서 해밀턴 사이클을 보면 7개의 간선을 가지는 것을 볼 수 있습니다.

정점이 7개면 즉 7개 이상의 간선이 있습니다. 그럼 해밀턴 사이클을 제외하고 나머지 간선을 제거했을 때 해밀턴 사이클만 남아있는 그래프를 생각해보면 정점의 차수는 2가 됩니다. 

해밀턴의 각 정점의 차수는 2여야하는데 위의 그래프를 확인하기 위해서는 간선을 2가 되도록 해주어야 합니다. V4와 V2가 간선이 3개이므로 간선을 하나씩 제거를 합니다. 

이렇게 간선을 제거하니 간선이 4개가 남습니다. 하지만 정점은  5개이므로 해밀턴 사이클을 만족하려면 5개가 되어야 하므로 해밀턴 사이클이 존재하지 않는다는 것을 유추할 수 있습니다.

 

그레이 부호

n비트의 2^n 개의 모든 string이 수열에 나타납니다. 

 

k번째와 k+1번째는 한 비트가 다릅니다. 

 

그리고 맨 마지막 번째 수와 첫번째 수 역시 한 비트가 달라야 합니다. 

 

이것이 그레이 부호가 되는 조건입니다. 그레이부호는 해밀턴 사이클에 해당이 됩니다. 

 G의 리버스를 적습니다.

 

G의 ' 은 G1의 앞에 0을 더해줍니다.

G의 '' 은 G의 리버스에 1을 더해줍니다. 

 

이후 G2는 그것을 연속해서 G' , G'' 을 입력해주면 됩니다. 

 

최단경로 알고리즘

가장 짧은 길이를 경로를 찾는 것이 Dijkstra 알고리즘이며 이는 n^2의 시간복잡도를 가집니다. 

 

인접행렬

0아니면 1의 값을 표기합니다. 즉 row vertex와 column vertex에서 간선이 존재하면 1 아니면 0을 넣으면 됩니다. 

이렇게 표시를 해주면 됩니다.