동형사상 그래프는 단일 그래프가 두 가지 이상의 형태를 가질 수 있는 그래프로 설명할 수 있습니다. 이는 두 개의 서로 다른 그래프가 동일한 수의 간선, 정점 및 동일한 간선 연결을 가질 수 있음을 의미합니다. 이러한 유형의 그래프를 동형 그래프라고 합니다. 동형 그래프의 예는 다음과 같이 설명됩니다.
위 그래프에는 다음과 같은 내용이 포함되어 있습니다.
- 동일한 그래프가 두 가지 이상의 형태로 표시됩니다.
- 따라서 이 그래프는 동형 그래프라고 말할 수 있습니다.
그래프 동형성의 조건
두 그래프가 다음 네 가지 조건을 만족하면 동형(isomorphism)이라고 합니다.
- 주어진 그래프에는 동일한 수의 정점이 있습니다.
- 주어진 그래프에는 동일한 수의 간선이 있습니다.
- 주어진 그래프에는 동일한 양의 차수 시퀀스가 있습니다.
- 첫 번째 그래프가 정점 {v1, v2, v3, …의 도움으로 길이가 k인 순환을 형성하는 경우. vk}이면 다른 그래프도 정점 {v1, v2, v3, …의 도움으로 동일한 길이 k의 동일한 사이클을 형성해야 합니다. vk}.
참고: 그래프의 차수 시퀀스는 모든 정점의 차수를 오름차순으로 나열한 것으로 설명할 수 있습니다.
중요사항
- 임의의 두 그래프가 동형이 되기 위해서는 위에서 정의한 4가지 조건이 필요합니다.
- 위에서 정의한 조건이 주어진 그래프가 동형임을 보여주기에 충분할 필요는 없습니다.
- 두 그래프가 위에서 정의한 네 가지 조건을 만족하더라도 그래프가 반드시 동형일 필요는 없습니다.
- 그래프가 어떤 조건도 만족하지 못하면 그래프는 확실히 동형이 아니라고 말할 수 있습니다.
그래프 동형성을 위한 충분 조건
임의의 두 그래프가 동형임을 증명하려는 경우 두 그래프가 확실히 동형임을 보장하는 몇 가지 충분 조건이 있습니다. 두 그래프가 위의 네 가지 조건을 모두 성공적으로 클리어한 경우에만 해당 그래프가 다음과 같이 충분한 조건인지 확인합니다.
- 두 그래프의 보수 그래프가 동형이라면, 이들 그래프는 확실히 동형이 될 것입니다.
- 두 그래프의 인접한 행렬이 동일하면 이 그래프는 동형이 됩니다.
- 한 그래프의 일부 정점을 삭제하여 두 그래프의 해당 그래프를 얻었고 다른 이미지의 해당 이미지가 동형인 경우에만 이러한 그래프는 동형이 아닙니다.
두 그래프가 위의 조건 중 하나를 만족하면 해당 그래프가 확실히 동형이라고 말할 수 있습니다.
그래프 동형성의 예
그래프 동형성의 예는 다음과 같이 많이 있습니다.
예시 1:
이 예에서는 다음 그래프가 동형인지 여부를 보여주었습니다.
해결책: 이를 위해 다음과 같이 그래프 동형성의 4가지 조건을 모두 확인하겠습니다.
조건 1:
- 그래프 1에는 총 4개의 정점이 있습니다. 즉, G1 = 4입니다.
- 그래프 2에는 총 4개의 정점이 있습니다. 즉, G2 = 4입니다.
여기,
두 그래프 G1과 G2에는 동일한 수의 정점이 있습니다. 따라서 이 그래프는 조건 1을 만족합니다. 이제 두 번째 조건을 확인하겠습니다.
조건 2:
- 그래프 1에는 총 5개의 간선이 있습니다. 즉, G1 = 5입니다.
- 그래프 2에는 총 6개의 간선이 있습니다. 즉, G2 = 6입니다.
여기,
끈으로 길게
그래프 G1과 G2 모두에 동일한 수의 간선이 없습니다. 따라서 이 그래프는 조건 2를 만족하지 않습니다. 이제 나머지 조건을 모두 확인할 수 없습니다.
왜냐하면 이 그래프는 조건 2를 위반하기 때문입니다. 따라서 이 그래프는 동형이 아닙니다.
∴ 그래프 G1과 그래프 G2는 동형 그래프가 아닙니다.
예 2:
이 예에서는 다음 그래프가 동형인지 여부를 보여주었습니다.
해결책: 이를 위해 다음과 같이 그래프 동형성의 4가지 조건을 모두 확인하겠습니다.
조건 1:
- 그래프 1에는 총 4개의 정점이 있습니다. 즉, G1 = 4입니다.
- 그래프 2에는 총 4개의 정점이 있습니다. 즉, G2 = 4입니다.
- 그래프 3에는 총 4개의 정점이 있습니다. 즉, G3 = 4입니다.
여기,
모든 그래프 G1, G2, G3에는 동일한 수의 정점이 있습니다. 따라서 이 그래프는 조건 1을 만족합니다. 이제 두 번째 조건을 확인하겠습니다.
조건 2:
javac가 인식되지 않습니다
- 그래프 1에는 총 5개의 간선이 있습니다. 즉, G1 = 5입니다.
- 그래프 2에는 총 5개의 간선이 있습니다. 즉, G2 = 5입니다.
- 그래프 3에는 총 4개의 간선이 있습니다. 즉, G2 = 4입니다.
여기,
- 두 그래프 G1과 G2에는 동일한 수의 간선이 있습니다. 따라서 이 그래프는 조건 2를 만족합니다.
- 그러나 그래프(G1, G2)와 G3에는 동일한 수의 간선이 없습니다. 따라서 그래프(G1, G2)와 G3는 조건 2를 만족하지 않습니다.
그래프(G1, G2)와 G3은 조건 2를 위반하므로 이 그래프는 동형이 아니라고 말할 수 있습니다.
∴ 그래프 G3은 그래프 G1이나 그래프 G2와 동형이 아닙니다.
그래프이므로 G1과 G2는 조건 2를 만족합니다. 따라서 이 그래프는 동형이라고 말할 수 있습니다.
∴ 그래프 G1과 G2는 동형일 수 있습니다.
이제 그래프 G1과 G2의 세 번째 조건을 확인하겠습니다.
조건 3:
- 그래프 1에서 시퀀스 s의 차수는 {2, 2, 3, 3}입니다. 즉, G1 = {2, 2, 3, 3}입니다.
- 그래프 2에서 수열 s의 차수는 {2, 2, 3, 3}, 즉 G2 = {2, 2, 3, 3}입니다.
여기
두 그래프 G1과 G2에는 동일한 수의 차수 시퀀스가 있습니다. 따라서 이 그래프는 조건 3을 만족합니다. 이제 네 번째 조건을 확인하겠습니다.
조건 4:
그래프 G1은 정점 {2, 3, 3}의 도움으로 길이가 3인 순환을 형성합니다.
그래프 G2는 또한 정점 {2, 3, 3}의 도움으로 길이가 3인 순환을 형성합니다.
여기,
이는 두 그래프 G1과 G2 모두 꼭지점 {2, 3, 3}의 도움으로 길이 3의 주기를 형성하기 때문에 두 그래프에 동일한 주기가 포함되어 있음을 보여줍니다. 따라서 이 그래프는 조건 4를 만족합니다.
따라서,
- 그래프 G1과 G2는 위의 네 가지 필수 조건을 모두 만족합니다.
- 따라서 G1과 G2는 동형일 수 있습니다.
이제 그래프 G1과 G2가 동형임을 보여주기 위한 충분한 조건을 확인하겠습니다.
HTML 태그
충분 조건 확인
우리가 배웠듯이 두 그래프의 보수 그래프가 동형이라면 두 그래프는 확실히 동형이 될 것입니다.
따라서 G1과 G2의 보수 그래프를 그려보면 다음과 같다.
위의 G1과 G2의 보수 그래프에서 두 그래프 모두 동형임을 알 수 있습니다.
∴ 그래프 G1과 G2는 동형입니다.
예시 3:
이 예에서는 다음 그래프가 동형인지 여부를 보여주었습니다.
해결책: 이를 위해 다음과 같이 그래프 동형성의 4가지 조건을 모두 확인하겠습니다.
조건 1:
자바스크립트 if 문
- 그래프 1에는 총 8개의 정점이 있습니다. 즉, G1 = 8입니다.
- 그래프 2에는 총 8개의 정점이 있습니다. 즉, G2 = 8입니다.
여기,
두 그래프 G1과 G2에는 동일한 수의 정점이 있습니다. 따라서 이 그래프는 조건 1을 만족합니다. 이제 두 번째 조건을 확인하겠습니다.
조건 2:
- 그래프 1에서는 총 간선 수가 10개입니다. 즉, G1 = 10입니다.
- 그래프 2에서는 총 간선 수가 10개입니다. 즉, G2 = 10입니다.
여기,
두 그래프 G1과 G2에는 동일한 수의 간선이 있습니다. 따라서 이 그래프는 조건 2를 만족합니다. 이제 세 번째 조건을 확인하겠습니다.
조건 3:
- 그래프 1에서 수열 s의 차수는 {2, 2, 2, 2, 3, 3, 3, 3}입니다. 즉, G1 = {2, 2, 2, 2, 3, 3, 3, 3}입니다. .
- 그래프 2에서 수열 s의 차수는 {2, 2, 2, 2, 3, 3, 3, 3}입니다. 즉, G2 = {2, 2, 2, 2, 3, 3, 3, 3}입니다. .
여기
두 그래프 G1과 G2에는 동일한 수의 차수 시퀀스가 있습니다. 따라서 이 그래프는 조건 3을 만족합니다. 이제 네 번째 조건을 확인하겠습니다.
조건 4:
- 그래프 G1은 3차 정점의 도움으로 길이 4의 순환을 형성합니다.
- 그래프 G2는 정점이 인접하지 않기 때문에 정점의 도움으로 길이가 4인 순환을 형성하지 않습니다.
여기,
그래프 G1과 G2는 모두 동일한 길이의 동일한 사이클을 형성하지 않습니다. 따라서 이 그래프는 조건 4를 위반합니다.
그래프 G1과 G2는 조건 4를 위반하므로 조건 4를 위반하므로 이 그래프는 동형이 아닙니다.
∴ 그래프 G1과 G2는 동형이 아닙니다.