그래프동형성

그래프 이론의 수학 분야에서 그래프 동형성은 그들의 구조를 존중하는 두 그래프 사이의 매핑이다.구체적으로는 인접 정점을 인접 정점에 매핑하는 두 그래프의 정점 집합 사이의 함수다.

동형체론은 그래프 색상의 다양한 개념을 일반화하고 특정 스케줄링 또는 빈도 할당 문제와 같은 제약조건 만족도 문제의 중요한 부류의 표현을 허용한다.^[1]동형성이 구성될 수 있다는 사실은 풍부한 대수학적 구조로 이어진다: 그래프의 사전 순서, 분배 격자,^[2] 범주(비방향 그래프의 경우 1개, 지시된 그래프의 경우 1개).주어진 그래프 사이에서 동형성을 찾는 계산상의 복잡성은 일반적으로는 엄두도 못 낼 정도로 복잡하지만 다항식 시간에 해결할 수 있는 특수한 경우에 대해서는 많이 알려져 있다.다루기 쉬운 사례와 다루기 힘든 사례 사이의 경계가 연구의 활발한 영역이었다.^[3]

정의들

이 글에서 달리 명시되지 않는 한 그래프는 루프가 허용되는 유한한 비방향 그래프이지만 다중 에지(병행 에지)는 허용되지 않는다.그래프 G = (V(G), E(G)에서 그래프 H = (V(H), E(H)로, 작성되는 그래프 동형성^[4] f

f : G → H

V(G)에서 V(H)까지의 함수로서, G의 각 에지 끝점을 H의 에지 끝점에 매핑한다. 정식으로 {u,v} e E(G)는 V(G)의 모든 꼭지점 쌍에 대해 {f(u),f(v)} e E(H)를 내포한다.G에서 H까지 동형성이 존재한다면, G는 H나 H색에 동형성이 있다고 한다.이것은 흔히 다음과 같이 표현된다.

G → H .

위의 정의는 지시된 그래프까지 확장된다.그렇다면 동형상 f : G → H의 경우 (f(u),f(v)는 (u,v)가 G의 호일 때마다 H의 호(방향 가장자리)이다.

There is an injective homomorphism from G to H (i.e., one that never maps distinct vertices to one vertex) if and only if G is a subgraph of H. If a homomorphism f : G → H is a bijection (a one-to-one correspondence between vertices of G and H) whose inverse function is also a graph homomorphism, then f is a graph isomorphism.^[5]

커버 맵은 위상에서 커버 맵의 정의와 많은 특성을 반영하는 특별한 종류의 동형성이다.^[6]그들은 또한 국소적으로 편향적인, 즉 각 정점의 인접성에 대한 편향인, 허탈적 동형성(즉, 각 정점에 대한 어떤 것을 지도하는 것)으로 정의된다.예를 들어, 각 꼭지점 v를 v와₀₁ v로 나누고 각 가장자리 u를 엣지₀ u,v₁,v₀,u로₁ 교체하여 그래프로 형성된 초당적 이중 커버가 그 예다.표지의 v와₀ v를₁ 원래 그래프의 v에 매핑하는 함수는 동형상 및 표지 맵이다.

그래프 동형성은 다른 개념으로, 동형성과 직접 관련이 없다.대략적으로 말하면, 주입성이 필요하지만, (가장자리뿐만 아니라) 경로에 가장자리를 매핑할 수 있다.그래프의 미성년자들은 여전히 더 느긋한 개념이다.

코어 및 리트랙트

G → H → H → G이면 G, H 2개의 그래프 G는 동형상 등가.^[4] 지도가 반드시 굴절적이거나 주입적인 것은 아니다.예를 들어, 완전한 초당적_2,2 그래프 K와_3,3 K는 동형상 동일하다. 각 맵은 도메인 그래프의 왼쪽(오른쪽) 절반을 가져가고 이미지 그래프의 왼쪽(오른쪽) 절반에 있는 하나의 꼭지점만 매핑하는 것으로 정의할 수 있다.

수축은 그래프 G에서 G의 서브그래프 H까지의 동형상 r로서, H의 각 꼭지점 v에 대해 r(v) = v.이 경우 서브그래프 H를 G의 수축이라고 한다.^[7]

중심은 적절한 하위 그래프에 동형성이 없는 그래프다.마찬가지로, 코어는 적절한 서브그래프로 수축되지 않는 그래프로 정의될 수 있다.^[8]모든 그래프 G는 G의 핵심이라고 불리는 고유한 코어(이소모르프까지)와 동형상 동일하다.^[9] 특히 무한 그래프에 대해서는 일반적으로 사실이 아니다.^[10]단, 지시된 그래프에도 동일한 정의가 적용되며 지시된 그래프도 고유한 코어(core)와 동등하다.모든 그래프와 지시된 모든 그래프는 수축 및 유도 서브그래프로 그것의 핵심을 포함한다.^[7]

예를 들어, 모든 전체 그래프 K와_n 모든 홀수 사이클(홀수 길이의 사이클 그래프)은 코어가 된다.삼각형(즉, 완전한 그래프 K를₃ 서브그래프로 포함)을 포함하는 모든 3색 그래프 G는 동형상 K와₃ 동등하다.한 편으로는 G의 3색상이 아래 설명과 같이 동형성 G → K와₃ 같기 때문이다.한편 G의 모든 서브그래프는 K₃ → G를 암시하는 동형성을 G로 미미하게 인정하고 있다.이것은 또한 K가₃ 그러한 그래프 G의 핵심이라는 것을 의미한다. 마찬가지로, 적어도 하나의 가장자리가 있는 모든 초당적 그래프는 K와₂ 동등하다.^[11]

색상 연결

k-색상은 일부 정수 k의 경우 각 가장자리의 끝점이 서로 다른 색을 갖도록 그래프 G의 각 꼭지점에 k-색 중 하나를 할당하는 것이다.G의 k-색상은 G에서 완전한 그래프 K까지의_k 동형성에 정확히 대응한다.^[12]실제로 K의_k 정점은 k 색상에 해당하며, 두 가지 색상은 K의 정점이 다를 경우에만 K의_k 정점으로 인접해 있다.따라서 함수는 G의 인접 정점을 다른 색상(즉, k-컬러링)에 매핑하는 경우에만 K에_k 동형성을 정의한다.특히 G는 K컬러블일_k 경우에만 k컬러블이 가능하다.^[12]

만약 동형성 G → H → H → K가_k 두 개라면, 그들의 구성 G → K도_k 동형성이다.^[13]즉, 그래프 H를 k 색으로 채색할 수 있고, G에서 H까지의 동형성이 있다면 G도 k 색으로 채색할 수 있다.따라서 G → H는 χ(G) ≤(H)을 내포하고, 여기서 χ은 그래프의 색수(k-colorable의 최소 k)를 나타낸다.^[14]

변형

일반적인 동형체도 색상의 일종으로 생각할 수 있다: 고정 그래프 H의 정점이 사용 가능한 색상이고 H의 가장자리가 어떤 색상이 호환되는지를 설명한다면, G의 H-색상은 인접한 정점이 호환되는 색상을 얻기 위해 G의 정점에 색상을 할당하는 것이다.많은 그래프 컬러링의 개념은 이 패턴에 적합하며 그래프 동형성으로 다른 그래프 계열에 표현될 수 있다.원형 컬러링은 동형성을 사용하여 원형 완전 그래프로 정의하여 일반적인 컬러링 개념을 정제할 수 있다.^[15]분수 및 b-폴드 색상은 Kneser 그래프에 동형식을 사용하여 정의할 수 있다.^[16]T-색상은 동형성에 대응하여 특정한 무한 그래프에 해당한다.^[17]지시된 그래프의 방향 색상은 어떤 방향의 그래프에 대한 동형상이다.^[18]L(2,1)-색상은 국소적으로 주입되는 경로 그래프의 보완에 대한 동형상으로서, 모든 정점의 인접성에 주입되어야 함을 의미한다.^[19]

긴 경로가 없는 방향

또 다른 흥미로운 연결은 그래프의 방향성에 관한 것이다.비방향 그래프 G의 방향은 각 가장자리에 대해 가능한 두 가지 방향 중 하나를 선택하여 얻은 방향 그래프다.전체 그래프 K의_k 오리엔테이션의 예로는 전이 토너먼트가 있다.T→_k i < j. 그래프 G와 H의 방향 사이의 동형동맥은 단순히 방향을 무시하는 것으로 비방향 그래프 G와 H 사이에 동형동맥을 형성한다.한편, 비방향 그래프 사이에 동형성 G → H가 주어지면, 어떤 방향도 주어진다.H→ H의 방향 전환 가능G→ 그렇게 하도록 G의G→ 에 동형성을 가지고 있다.H→ 따라서 G의 어떤 방향이 다음과 같은 동형성을 갖는 경우에만 그래프 G는 k-색상이 가능하다(K에_k 동형성을 가진다).T→_k.^[20]

민속학적 정리는 모든 k에 대해 지시된 그래프 G가 동형성을 가지고 있다고 말한다.T→_k 지시된 경로로부터 동형성을 인정하지 않는 경우에만P→._k+1^[21] 여기P→_n i = 1, 2, …, i에서 i + 1까지의 정점 1, 2, …, n - 1을 나타내는 방향 그래프.따라서 그래프는 동형성을 인정하지 않는 방향을 가진 경우에만 k-컬러블이 가능하다.P→._k+1 이 문장은 일부 방향에 k 길이(no)의 방향 경로가 없는 경우에만 그래프가 k-색상이 가능하다고 약간 강화될 수 있다.P→_k+1 서브그래프로서).이것이 갈라이-하세-로이-비타버 정리다.

제약 조건 만족 문제에 대한 연결

예

일부 스케줄링 문제는 그래프 동형성 발견에 대한 질문으로 모델링될 수 있다.^[22][23]예를 들어, 동일한 학생이 참석하는 두 개의 과정이 시간에 너무 가까이 있지 않도록 달력의 시간 간격에 워크샵 과정을 할당하고 싶을 수 있다.이 과정은 그래프 G를 형성하며, 일부 일반 학생이 참석하는 두 과정 사이의 가장자리를 가지고 있다.시간 간격은 그래프 H를 형성하며, 시간적으로 충분히 먼 두 슬롯 사이에 에지가 있다.예를 들어, 각 학생이 연속되지 않는 날에 워크샵 과정을 이수하는 주기적인 주간 스케줄을 원한다면 H는 C의₇ 보완 그래프가 될 것이다.G에서 H까지의 그래프 동형성은 지정된 시간 간격에 과정을 지정하는 일정이다.^[22]예를 들어, 금요일과 월요일 양쪽에 단일 학생이 수업을 하지 않는다는 요구 사항을 추가하기 위해서는 H에서 해당 가장자리를 제거하면 충분하다.

단순한 주파수 할당 문제는 다음과 같이 지정할 수 있다: 무선 네트워크의 다수의 송신기는 데이터를 전송할 주파수 채널을 선택해야 한다.간섭을 피하기 위해 지리적으로 가까운 송신기는 주파수가 멀리 떨어져 있는 채널을 사용해야 한다.만약 이 조건이 '지리적 근접'과 '멀리 떨어져'를 정의하는 단일 임계값으로 근사치된다면, 유효한 채널 선택은 다시 그래프 동형성에 해당한다.지리적으로 가까운 쌍 사이에 가장자리가 있는 송신기 G의 그래프에서 채널 H의 그래프까지, 채널 간 가장자리가 멀리 떨어져 있어야 한다.이 모델은 다소 단순화되었지만, 일부 융통성은 인정한다: 가깝지는 않지만 지리적 특징 때문에 간섭할 수 있는 송신기 쌍은 G의 가장자리에 추가될 수 있다.동시에 의사소통을 하지 않는 사람들은 그것에서 제거될 수 있다.마찬가지로 멀리 떨어져 있지만 고조파 간섭을 보이는 채널 쌍은 H의 에지 집합에서 제거할 수 있다.^[24]

각각의 경우에, 이러한 단순화된 모델들은 실제로 다루어져야 하는 많은 문제들을 보여준다.^[25]그래프 동형성 문제를 일반화하는 제약조건 만족 문제는 다양한 추가 조건 유형(개별 선호도 또는 일치 과제 수에 대한 한계 등)을 표현할 수 있다.이를 통해 모델을 보다 현실적이고 실용적으로 만들 수 있다.

형식 보기

그래프와 지시된 그래프는 관계 구조라고 불리는 훨씬 더 일반적인 개념의 특별한 사례로 볼 수 있다.지시된 그래프는 도메인(정점 집합)에서 단일 이항 관계(접근)를 갖는 구조물이다.^[26][3]이 견해에 따르면, 그러한 구조의 동형성은 정확히 그래프 동형성이다.일반적으로 한 관계 구조에서 다른 관계 구조로 동형성을 찾는 문제는 제약 만족도 문제(CSP)이다.그래프의 경우는 보다 복잡한 CSP를 이해하는 데 도움이 되는 구체적인 첫 단계를 제시한다.역추적, 제약 조건 전파 및 로컬 검색과 같은 그래프 동형성을 찾기 위한 많은 알고리즘 방법이 모든 CSP에 적용된다.^[3]

그래프 G와 H의 경우, G가 H에 동형성을 가지고 있는지에 대한 문제는 다음과 같이 하나의 제약조건만을 가진 CSP 인스턴스에 해당한다.^[3]변수는 G의 정점이고 각 변수에 대한 도메인은 H의 정점 집합이다. 평가는 각 변수에 도메인의 요소를 할당하는 함수이므로, V(G)에서 V(H)까지의 함수 f가 된다.G의 각 가장자리 또는 호(u,v)는 구속조건(u,v), E(H)에 해당한다.이는 평가에서 호(u,v)를 관계 E(H)에 있는 쌍(f(u),f(v)에 매핑해야 한다고 표현하는 제약조건이다. 즉, CSP에 대한 해결책은 모든 제약조건을 존중하는 평가이므로 G에서 H까지 정확히 동형상이다.

동형성 구조

동형성의 구성은 동형성이다.^[13]특히 그래프 상의 관계 → 는 전이성(그리고 반사성, 사소함)이므로, 그래프의 사전 주문이다.^[27]동형성 등가성에 따른 그래프 G의 등가 등급은 [G]가 되도록 한다.동등성 등급은 [G]의 고유 코어로 나타낼 수도 있다.관계 →는 그러한 동등성 등급에 대한 부분적인 순서로서, poset을 정의한다.^[28]

G < H는 G에서 H까지 동형성은 있지만, H에서 G까지 동형성은 없다는 것을 가리킨다.관계 → 는 밀도 높은 순서로서, G < H와 같은 모든 (비방향) 그래프 G, H에 대해 G < K < H (이것은 사소한 경우 G = K 또는₀ K를₁ 제외하고 잡는다)와 같은 그래프 K가 있다는 것을 의미한다.^[29][30]예를 들어, 어떤 두 개의 완전한 그래프(K₀, K₁, K₂ 제외) 사이에는 무한히 많은 원형 완전 그래프가 있는데, 이는 자연수 사이의 합리적인 숫자에 해당한다.^[31]

[G]의 조인과[H](의 동치)이 연결되지 않은 노조[G∪ H]로 정의한 그래프의 동등 클래스의 homomorphisms 아래의 poset은 개별 격자,[G]의 만나서[H]은 텐서 제품[G×H](그래프 G와 H의 선택이 동등 클래스를 나타내는[G]과[H]문제가 되지 않는다)이라고 정의한다.[32]이 격자의 결합-수정 불가능한 요소는 정확히 연결된 그래프들이다.이것은 동형성이 연결된 그래프를 대상 그래프의 하나의 연결된 구성요소에 매핑한다는 사실을 사용하여 나타낼 수 있다.^[33][34]이 격자의 충족 불가 요소는 정확히 곱셈 그래프다.이것은 G × H 제품이 G 또는 H 중 하나가 K에 동형성을 갖는 것과 같은 그래프 K이다.승수 그래프를 확인하는 것은 헤데니에미 추측의 핵심에 있다.^[35][36]

그래프 동형체도 범주를 형성하는데, 그래프는 객체로, 동형체는 화살표로 한다.^[37]초기 개체는 빈 그래프인 반면, 단자 개체는 그 정점에 하나의 꼭지점과 하나의 루프가 있는 그래프인 것이다.그래프의 텐서 곱은 범주의 이론적 산물이고 지수 그래프는 이 범주의 지수 객체다.^[36][38]이 두 연산은 항상 정의되기 때문에 그래프의 범주는 데카르트 폐쇄 범주다.같은 이유로, 동형화 하에서의 그래프의 동등성 등급의 격자는 사실상 헤이팅 대수학이다.^[36][38]

지시된 그래프의 경우에도 동일한 정의가 적용된다.특히 → 지시된 그래프의 동등성 등급에 대한 부분 순서다.비방향 그래프의 동등성 등급에 대한 순서 →와는 구별되지만 하위 순서로 수록되어 있다.왜냐하면 모든 비방향 그래프는 모든 호(u,v)가 그 역호(v,u)와 함께 나타나는 방향 그래프로 생각할 수 있고, 이것이 동형성의 정의를 바꾸지 않기 때문이다.지시된 그래프에 대한 순서 → 다시 분포 격자 및 헤잉 대수로서, 이전과 같이 정의된 결합 및 충족 연산을 가지고 있다.그러나 밀도가 높지 않다.방향 그래프를 객체로 하고 동형식을 화살표로 하는 범주도 있는데, 이것은 다시 데카르트식 폐쇄 범주다.^[39][38]

비교할 수 없는 그래프

동형성 사전 순서, 즉 동형성을 인정하지 않는 그래프의 쌍과 비교할 수 없는 그래프가 많이 있다.^[40]이들을 구성하는 한 가지 방법은 그래프 G의 홀수 둘레, 즉 가장 짧은 홀수 길이 사이클의 길이를 고려하는 것이다.홀수 둘레는, 동등하게, g 정점의 주기 그래프에서 G까지의 동형성이 존재하는 가장 작은 홀수 g이다.이 때문에 G → H일 경우 G의 홀수 둘레가 H의 홀수 둘레보다 크거나 같다.^[41]

반면 G → H일 경우 G의 색수는 H의 색수보다 작거나 같다.따라서 G가 H보다 홀수 둘레가 엄격히 크고 색수가 H보다 엄격히 크다면 G와 H는 비교할 수 없다.^[40]예를 들어 그뢰츠슈 그래프는 4-색깔과 삼각형이 없기 때문에(그것은 4번째와 5번째 기수가 있다)^[42] 삼각형 그래프 K와는₃ 비교가 안 된다.

홀수 둘레와 색수 값이 임의로 큰 그래프의 예로는 크네저 그래프와^[43] 일반화된 마이켈스키안이 있다.^[44]그러한 그래프의 순서는 두 모수의 값이 동시에 증가하면서 무한히 많은 비교 불가능한 그래프(동형성 사전 순서에서의 반차이)를 제공한다.^[45]동형성 사전 주문의 밀도와 같은 다른 특성들은 그러한 가족을 사용하여 증명될 수 있다.^[46]홀수 둘레뿐만 아니라 색수와 둘레 값이 큰 그래프의 구성도 가능하지만 더 복잡하다(둘레와 그래프 색소 참조).

지시된 그래프 중에서 비교할 수 없는 쌍을 찾는 것이 훨씬 쉽다.예를 들어, 정점 1, 2, …, n과 엣지(i = 1, 2, n - 1) 및 n에서 n까지를 나타내는 C→_n 지시된 주기 그래프를 생각해 보십시오.n이 k의 배수인 경우에만 C→_nC→(_kn, k ≥ 3)까지 동형성이 있다.특히 n prime이 있는 지시 사이클 그래프 C→_n는 모두 비교가 안 된다.^[47]

계산 복잡성

그래프 동형성 문제에서 한 예는 그래프 쌍(G, H)이며 해법은 G에서 H까지의 동형성이다.해결책이 있는지 묻는 일반적인 의사결정 문제는 NP-완전하다.^[48]그러나 허용된 인스턴스를 제한하면 여러 가지 다른 문제가 발생하는데, 그 중 일부는 훨씬 쉽게 해결할 수 있다.왼쪽 G를 억제할 때 적용되는 방법은 오른쪽 H와 매우 다르지만, 각각의 경우 이분법(쉬운 경우와 힘든 경우 사이의 날카로운 경계)이 알려지거나 추측된다.

고정 그래프에 대한 동형성

각 인스턴스의 우측에 고정 그래프 H가 있는 동형성 문제를 H-색상 문제라고도 한다.H가 전체 그래프 K인_k 경우, 이것은 그래프 k-컬러링 문제인데, 이는 k = 0, 1, 2 및 NP에 대한 다항 시간에서 해결 가능하다.^[49]특히 그래프 G의 K-색상성은₂ G가 양분되어 있는 것과 동등한 것으로, 선형적으로 시험할 수 있다.보다 일반적으로 H가 초당적 그래프일 때마다 H-색상은 K-색상성₂(또는₀ H가 비어 있거나 에지가 없을 때 K/K-색상성₁)과 동일하므로 동일하게 쉽게 결정할 수 있다.^[50]파볼 헬과 야로슬라프 네셰틸은 비방향 그래프의 경우 다른 경우를 추적할 수 없다는 것을 증명했다.

헬-네세틸 정리(1990):H-색채 문제는 H가 초당적일 때 P에 있으며 그렇지 않으면 NP-완전이다.^[51][52]

이것은 (비간접) 그래프 동형성에 대한 이분법적 정리라고도 하는데, 이는 H형식 문제를 중간 사례가 없는 NP-완전성 또는 P형 문제로 나누기 때문이다.지시된 그래프의 경우 상황은 더 복잡하고 사실 제약 만족 문제의 복잡성을 특징짓는 훨씬 더 일반적인 문제와 동일하다.^[53]지시된 그래프의 H-색상 문제는 CSP만큼 일반적이고 다른 종류의 제약이 있는 것으로 밝혀졌다.^[54][55]형식적으로 (완료된) 제약 언어(또는 템플릿) Ⅱ는 이 영역에 대한 유한한 영역이자 유한한 관계 집합이다.CSP(CSP)는 인스턴스들이 γ의 제약조건만을 사용하도록 허용된 제약조건 만족도 문제다.

정리(Feder, Vardi 1998):모든 제약 조건 언어 γ에 대해 문제 CSP(CSP)는 일부 방향 그래프 H에 대해 일부 H-색인 문제에 대한 다항 시간 감소 하에서 동등하다.^[55]

직관적으로 이것은 지시된 그래프 H의 H-색상 문제에 적용되는 모든 알고리즘 기술이나 복잡성 결과가 일반 CSP에도 똑같이 적용된다는 것을 의미한다.특히 헬-네슈틸 정리가 지시된 그래프까지 확대될 수 있는지 물어볼 수 있다.위의 정리로는, 이는 CSP 이분법에 관한 Feder-Vardi 추측(일명 CSP 추측, 이분법적 추측)에 해당하는데, 이는 모든 제약조건 언어 Ⅱ에 대해 CSP(CSP)는 NP-완전 또는 P에 있다고 기술하고 있다.^[48]이러한 추측은 드미트리 주크와 안드레이 불라토프에 의해 2017년에 독자적으로 증명되어 다음과 같은 귀결로 이어졌다.

코롤라리(Bulatov 2017; Zhuk 2017):지시된 그래프의 H-색인 문제는 고정 H의 경우 P 또는 NP-완전이다.

고정된 그래프 계열의 동형성

입력 인스턴스 왼쪽에 단일 고정 그래프 G가 있는 동형성 문제는 시간 V(H)의 완력으로 해결할 수 있으므로 입력 그래프 H의 크기에서 다항식이다.^[56]즉, 경계가 있는 그래프 G의 경우 문제는 사소한 P에 있다.흥미로운 질문은 크기 외에도 G의 다른 특성들이 어떤 다항식 알고리즘을 가능하게 하는가에 관한 것이다.

그 중요한 속성은 그래프가 얼마나 나무와 비슷한지 보여주는 척도인 나무 너비로 밝혀졌다.최대 k의 트리 너비 그래프 G와 그래프 H의 경우, 동형상 문제는 표준 동적 프로그래밍 접근법을 사용하여 시간 V(H)로 해결할 수 있다.사실 G의 핵심이 최대 k에 나무 너비를 가지고 있다고 가정해도 충분하다.이것은 핵심을 알 수 없더라도 유지된다.^[57][58]

V(H) - 시간 알고리즘의 지수를 유의하게 낮출 수 없음: 입력이 무한 트리 폭의 그래프 클래스로 제한되더라도 지수 시간 가설(ETH)을 가정할 때 가동 시간이 V(H)인 알고리즘이 존재하지 않는다.^[59]ETH는 P ≠ NP와 유사하지만 입증되지 않은 가정이다.같은 가정 하에서 다항 시간 알고리즘을 얻는 데 사용할 수 있는 다른 속성도 본질적으로 없다.이는 다음과 같이 공식화된다.

정리(그로헤):For a computable class of graphs ${\displaystyle {\mathcal {G}}}$, the homomorphism problem for instances ${\displaystyle (G,H)}$ with ${\displaystyle G\in {\mathcal {G}}}$ is in P if and only if graphs in ${\displaystyle {\mathcal {G}}}$ have cores of bounded treewidth (assuming ETH).^[58]

적어도 G에 대한 의존도는 자의적으로 높지만 H의 크기에 대한 다항식 의존도가 고정된 시간 내에 문제를 해결할 수 있는지 물어볼 수 있다.G를 경계 트리 너비의 코어가 있는 그래프 클래스로 제한하고 다른 모든 클래스에 대해 음수로 제한하면 답은 다시 긍정적이다.^[58]매개변수화된 복잡성의 언어에서 G의 크기(가장자리 수)에 의해 매개변수화된$$ $G{\displaystyle \mathcal{}}$ ${\$의 동형상 문제가 이분법을 나타낸다고 공식적으로 명시한다.$G{\displaystyle \mathcal{}}$ ${\$의 그래프에 경계 트리 너비의 코어가 있으면$$ 고정 파라미터를 추적할 수 있으며, 그렇지 않으면 W[1]-완료된다.

동일한 진술은 제약조건 만족도 문제(또는 관계 구조, 다시 말하면 관계 구조)에 대해 보다 일반적으로 적용된다.제약조건은 한정된 수의 변수만을 포함할 수 있다는 가정만이 필요하다(모든 관계는 어떤 한정된 경성의 관계, 그래프의 경우 2).관련 매개변수는 원시 구속조건 그래프의 트리 너비다.^[59]

참고 항목

• 그래프 이론 용어집
• 동형성, 서로 다른 대수 구조에 대한 동일한 개념에 대한 것
• 그래프 재작성
• 중앙 그래프(하이퍼큐브의 수축으로 정의 가능)
• 시도렌코의 추측

메모들

참조

일반 도서 및 박람회

• Cameron, P. (2006), Graph Homomorphisms, Combinatorics Study Group Notes (PDF)
• Hell, Pavol; Nešetřil, Jaroslav (2004), Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications, vol. 28, Oxford University Press, ISBN 0-19-852817-5
• Hahn, G.; Tardif, C. (1997), "Graph homomorphisms: structure and symmetry", Graph Symmetry: Algebraic Methods and Applications (PDF), Springer, pp. 107–166, doi:10.1007/978-94-015-8937-6_4
• Godsil, C.; Royle, G. (2001), "6. Homomorphisms", Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer–Verlag New York, doi:10.1007/978-1-4613-0163-9, ISBN 978-1-4613-0163-9

제약만족도와 보편대수학에서

• Bodirsky, M. (2007), Graph Homomorphisms and Universal Algebra, Course Notes (PDF)
• Hell, Pavol; Nešetřil, Jaroslav (2008), "Colouring, constraint satisfaction, and complexity" (PDF), Computer Science Review, 2 (3): 143–163, doi:10.1016/j.cosrev.2008.10.003

격자 이론과 범주 이론에서

• Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of morphisms of graphs", Electronic Journal of Combinatorics, 15 (1): A1, doi:10.37236/919
• Gray, C. T. (2014), The Digraph Lattice (PDF) (AMSI 방학 연구 장학금, 브라이언 데이비와 제인 핏켈리 라 트로베 대학 학생 연구 보고서)