logo

이산 수학의 그래프 동형성

동형사상 그래프는 단일 그래프가 두 가지 이상의 형태를 가질 수 있는 그래프로 설명할 수 있습니다. 이는 두 개의 서로 다른 그래프가 동일한 수의 간선, 정점 및 동일한 간선 연결을 가질 수 있음을 의미합니다. 이러한 유형의 그래프를 동형 그래프라고 합니다. 동형 그래프의 예는 다음과 같이 설명됩니다.

이산 수학의 그래프 동형성

위 그래프에는 다음과 같은 내용이 포함되어 있습니다.

  • 동일한 그래프가 두 가지 이상의 형태로 표시됩니다.
  • 따라서 이 그래프는 동형 그래프라고 말할 수 있습니다.

그래프 동형성의 조건

두 그래프가 다음 네 가지 조건을 만족하면 동형(isomorphism)이라고 합니다.

  1. 주어진 그래프에는 동일한 수의 정점이 있습니다.
  2. 주어진 그래프에는 동일한 수의 간선이 있습니다.
  3. 주어진 그래프에는 동일한 양의 차수 시퀀스가 ​​있습니다.
  4. 첫 번째 그래프가 정점 {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는 동형이 아닙니다.