그래프 동형

그래프 이론에서, 그래프 G와 H의 동형성은 G와 H의 정점 집합 사이의 분사이다.

${\displaystyle f(G)\colon V(H)\to V(H)}$

f${\displaystyle (u}$) {$displaystyle f($u$$)} $및{\displaystyle }$ ${\displaystyle f(}$v$)$ {$displaystyle f(v$)}가$$ H에 인접한 $경우$에만 G의 두 꼭지점 u와 v가 G에 인접하도록 한다.이러한 종류의 분사는 구조 보존 분사가라는 동형사상의 일반적인 개념에 따라 일반적으로 "가장자리를 보존하는 분사"로 묘사된다.두 그래프 사이에 동형이 존재하는 경우, 그래프를 동형이라고 하고, G${\displaystyle \mathrm{if}}$H(\$style$ G$\simeq$ H$)$라고 한다.이 경우, G와 H가 하나이고, 같은 그래프일 때, G가 유한한 그래프일 경우, 이 동형을 G의 자기동형이라고 할 수 있다.둘 다 보여줄 필요 없이 일대일/온토임을 보여줌으로써 경향화한다.그래프 동형성은 그래프 상의 동등성 관계이며, 따라서 모든 그래프의 클래스를 동등성 클래스로 분할합니다.서로 동형인 그래프 세트를 그래프의 동형성 클래스라고 합니다.

아래 두 그래프는 서로 다른 모양의 도면에도 불구하고 동형입니다.

그래프 G	그래프 H	동형사상 G와 H 사이에
		f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7

바리에이션

위의 정의에서 그래프는 무방향 비가중치 그래프로 이해된다.단, 다음과 같은 예외를 제외하고 구조의 해당 추가 요소(호 방향, 모서리 무게 등)를 보존하기 위한 요건을 추가하여 그래프 개념의 다른 모든 변형에 동형 개념을 적용할 수 있다.

레이블이 지정된 그래프의 동형성

레이블이 지정된 그래프의 경우 두 가지 동형 정의가 사용됩니다.

하나의 정의에 따르면, 동형성은 모서리 보존과 라벨 ^[1][2]보존 둘 다인 정점 사출이다.

또 다른 정의에 따르면, 동형성은 라벨의 동등성 클래스를 보존하는 가장자리 보존 정점 분사이다. 즉, 등가(같은) 라벨이 있는 정점은 등가 라벨이 있는 정점에 매핑되며, 그 반대도 에지 ^[3]라벨과 동일하다.

예를 들어 1과 2로 표시된 두 정점이 있는 ${\displaystyle {K\mathrm{}}_{}}$ 2$(\$ K_${2$$}})$ $그래프$는 첫 번째 정의에서는 단일 자기동형이 존재하지만 두 번째 정의에서는 두 개의 자기동형이 있습니다.

두 번째 정의는 특정 상황에서 그래프에 정수 범위 1,...,n에서 일반적으로 취해지는 고유한 라벨이 부여되는 것으로 가정한다. 여기서 n은 정점을 고유하게 식별하는 데만 사용되는 그래프의 정점 수이다.이러한 경우, 라벨이 부착되지 않은 해당 기본 그래프가 동형일 경우 레이블이 부착된 두 그래프가 동형이라고 말할 수 있다(그렇지 않으면 동형의 정의는 간단할 것이다).

동기

예를 들어 "그래프 동형"의 공식적 개념은 문제의 물체의 "원자" 구성요소의 개별적 구분을 무시한다면 일부 물체는 "동일한 구조"를 가지고 있다는 비공식적 개념을 포착한다.그래프에 의해 모델링된 것을 정확하게 표현하기 위해 "원자" 구성요소(그래프의 경우 수직과 가장자리)의 개성이 중요할 때마다, 구조에 추가적인 제한을 가함으로써 모델이 개선되고, 다른 수학적 객체(이글래프, 레이블이 지정된 그래프, 색상 그래프, 루트 트리 등)가 사용된다.동형관계는 그래프의 모든 일반화에 대해서도 정의될 수 있습니다.동형분사법은 문제의 객체 유형을 정의하는 구조의 요소(호, 라벨, 정점/엣지 색상, 루트 트리의 루트 등)를 보존해야 합니다.

"그래프 동형" 개념은 그래프 자체의 구조에 고유한 그래프 특성과 그래프 표현과 관련된 속성(그래프 도면, 그래프 데이터 구조, 그래프 레이블 등)을 구별할 수 있도록 한다.예를 들어, 그래프에 정확히 하나의 주기가 있는 경우, 동형 클래스의 모든 그래프에도 정확히 하나의 주기가 있습니다.한편, 그래프의 정점이 정수 1, 2, ...로 표시되는 일반적인 경우입니다.N, 그러면 식

$\displaystyle \sum _{v\in V(G)}v\cdot {text{deg}}v}$

두 개의 동형 그래프에 대해 다를 수 있습니다.

휘트니 정리

Hasler Whitney에 의해 제시된 Whitney 그래프 동형 ^[4]정리는 연결된 두 그래프가 동형일 경우에만 동형이라고 기술한다. 단 하나의 예외: K는₃ 3개의 정점에 있는 완전한 그래프이고_1,3 K는 동형은 아니지만 둘 다 K를₃ 선 그래프로 가지고 있다.휘트니 그래프 정리는 하이퍼그래프로 ^[5]확장될 수 있다.

그래프 동형 인식

그래프 동형사상은 휘트니 정리에 의해 예시된 것처럼 고전적인 수학적 방법으로 연구될 수 있지만, 알고리즘적 접근으로 다루어져야 할 문제라고 인식된다.두 개의 유한 그래프가 동형인지 아닌지를 결정하는 계산 문제를 그래프 동형 문제라고 한다.

이 방법의 실용적 적용에는 주로 화학, 수리 화학(화학성분 식별), 전자 설계 자동화(전자 회로 설계의 다양한 표현에 대한 동등성 검증)가 포함된다.

그래프 동형 문제는 계산 복잡도 이론에서 NP에 속하는 몇 안 되는 표준 문제 중 하나이지만, 잘 알려진 부분 집합인 P와 NP-완전 중 하나에 속하는 것으로 알려져 있지 않다.이는 Garey & Johnson(1979)에 열거된 문제 중 복잡성이 해결되지 않은 유일한 두 가지 문제 중 하나이며, 다른 하나는 정수 인수분해이다.그러나 문제가 NP-완전이면 다항식 계층이 유한 ^[6]수준으로 붕괴되는 것으로 알려져 있습니다.

2015년 11월, 시카고 대학의 수학자이자 컴퓨터 과학자인 라즐로 바바이는 그래프 동형성 문제가 준다항 시간에 ^[7][8]해결 가능하다는 것을 증명했다고 주장했다.그는 2016년 컴퓨터 ^[9]이론 심포지엄과 2018년 국제 수학자 ^[10]콩그레스에서 이 결과의 예비 버전을 발표했다.2017년 1월, Babai는 준다항성 주장을 잠시 철회하고 대신 하위 지수 시간 복잡도를 언급했다.그는 5일 ^[11]후에 원래의 주장을 회복했다.2020년 현재^[update], Babai의 논문의 풀 저널 버전은 아직 출판되지 않았다.

그 일반화, 즉 서브그래프 동형성 문제는 NP-완전인 것으로 알려져 있다.

이 문제에 대한 주요 연구 분야는 빠른 알고리즘의 설계와 계산 복잡성에 대한 이론적 조사이며, 일반적인 문제와 그래프의 특수 클래스에 대한 것이다.

「 」를 참조해 주세요.

• 그래프 동형사상
• 그래프 자기동형성 문제
• 그래프 동형 문제
• 그래프 캐논라이제이션

메모들

레퍼런스

• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5