재건 추측

비공식적으로 그래프 이론의 재구성 추측에 따르면 그래프는 하위 그래프에 의해 고유하게 결정된다.켈리와^[1] 울람 덕분이다.^[2][3]

형식명세서

$G{\displaystyle }$${\displaystyle }$=${\displaystyle }$(${\displaystyle V}$, ${\displaystyle E}$ )${\displaystyle G$$}$의$$정점 삭제 하위 그래프는 $G$ ${\displaystyle G}$에서 정확히 하나의 정점을 삭제하여 형성된 하위 그래프로서$,$ 정의상 $G{\displaystyle }$ ${\displaystyle G$의 유도 하위 그래프인 것이다.

그래프 $G{\displaystyle }$ ${\displaystyle G}$의 경우$,$ $D{\displaystyle }$( ${\displaystyle G}$)$${\$displaystyle D(G$로 표시된 G의 데크는 $G{\displaystyle }$ ${\displaystyle G}$의 모든 정점 삭제 하위 그래프의 이형성 등급의 다중 집합이다$.$ D (${\displaystyle }G{\displaystyle }$) ${\displaystystyle D(G)$의 각 그래프를 카드라고 부른다.같은 데크를 가진 두 개의 그래프는 저형체라고 한다.

이러한 정의로 추측할 수 있는 것은 다음과 같다.

• 재구성 추측:적어도 세 개의 꼭지점에 있는 두 개의 저형 그래프는 이형이다.

(두 꼭지점의 두 그래프 모두 동일한 데크를 가지기 때문에 그래프에 최소한 세 개의 꼭지점이 있어야 한다.)

하라리는^[4] 더 강력한 버전의 추측을 제시했다.

• 재구성 추측 설정:정점-삭제된 하위 그래프의 집합이 같은 적어도 네 개의 정점에 있는 두 개의 그래프는 이형성이다.

그래프 $G{\displaystyle }$=${\displaystyle }$( ${\displaystyle V}$, ${\displaystyle E}$) ${\displaystyle$ G$=(V,E)}$이(가) 주어진 경우$,$ $G{\displaystyle }$ ${\displaystyle$ G$}$의 가장자리 삭제 하위 그래프는 $G{\displaystyle }$ ${\displaystyle G}$에서 정확히 하나의 가장자리를 삭제하여 형성된 하위 그래프다$.$

For a graph ${\displaystyle G}$, the edge-deck of G, denoted ${\displaystyle ED(G)}$, is the multiset of all isomorphism classes of edge-deleted subgraphs of ${\displaystyle G}$. Each graph in ${\displaystyle ED(G)}$ is called an edge-card.

• 모서리 재구성 추측: (Harary, 1964)^[4] 최소 4개의 모서리 및 동일한 모서리 데크를 가진 두 개의 그래프는 모두 이형성이다.

인식 가능한 속성

재구성 추측의 맥락에서, 그래프의 갑판에서 속성을 결정할 수 있는 경우 그래프 속성을 인식할 수 있다고 한다.다음과 같은 그래프의 속성을 인식할 수 있다.

• Order of the graph – The order of a graph ${\displaystyle G}$, ${\displaystyle V(G) }$ is recognizable from ${\displaystyle D(G)}$ as the multiset ${\displaystyle D(G)}$ contains each subgraph of ${\displaystyle G}$ created by deleting one vertex of ${\displaystyle G}$. Hen${\displaystyle CE}$ V${\displaystyle }$(${\displaystyle G}$ )${\displaystyle }$= D${\displaystyle }$( ${\displaystyle G}$) $디스플레이$ 스타일 $V(G)$= D$(G) }$
• 그래프의 가장자리 수 – $그래프{\displaystyle }$ $G{\displaystyle }$ ${\displaystyle n}$ 정점$$, ${\displaystyle E(G)}$ $displaystyle E(G)}$을(를) 가진 그래프 G ${\displaystyle G}$의 가장자리 수를 인식할 수 있다$$.$먼저{\displaystyle }$ G ${\displaystyle G}$의 각 에지는 $D{\displaystyle (}$${\displaystyle G}$${\displaystyle }$) ${\displaystyle D($$G)}$의 $n{\displaystyle }$- 2 ${\$$displaystyle$ $n-2}$ 멤버에서 발생한다는$$ 점에 유의하십시오$.$ 이것은 $D{\displaystyle (}$G)의 정의에 따르면 각 에지가 해당 멤버에 포함될 때마다 각 에지가 포함되도록 하는 것이다$$.${\displaystyle D}$( ${\displaystyle G}$) ${\displaystyle D(G$ 따라서 끝점이 삭제된 두 개를 제외한$$ $D{\displaystyle (G}$) ${\displaystyle D(G)}$의 모든 멤버에서 에지가 발생한다.따라서 ${\displaystyle E}$( ${\displaystyle G}$)${\displaystyle }$= ${\displaystyle \sum }$ ${\displaystyle \frac{q_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ -${\displaystyle \frac{2}{}}$ ${\$${i$$}}{n-2}}:$ 여기서$$ $}$는 ${\displaystyle D}$( G${\displaystyle }$) ${\displaystyle d(G)}$의 ith 멤버에 있는 가장자리 수입니다$$$.$^[5]
• Degree sequence – $그래프{\displaystyle }$ G {\$displaystyle G}$의 각도 시퀀스는 모든 꼭지점의 정도를 인식할 수 있기 때문에 인식할 수 있다$$$.$$($) ${\$ D($G)}$의 ith 멤버에 없는 꼭지점$$$v{\displaystyle {}_{}}$ i {\$displaystyle D(G)}$의 정도를 찾기 위해 Gi ${\$을(를) 삭제하여 생성한 그래프를 조사한다$.$This graph contains all of the edges not incident with ${\displaystyle v_{i}}$, so if ${\displaystyle q_{i}}$ is the number of edges in ${\displaystyle G_{i}}$, then ${\displaystyle E(G) -q_{i}=\deg(v_{i})}$. If we can tell the degree of every vertex i그래프에서, 우리는 그래프의 정도 순서를 알 수 있다.^[5]
• (Vertex-)Connectivity – By definition, a graph is ${\displaystyle n}$-vertex-connected when deleting any vertex creates a ${\displaystyle n-1}$-vertex-connected graph; thus, if every card is a ${\displaystyle n-1}$-vertex-connected graph, we know the original graph was ${\displaystyle n}$-vertex-connected.또한 ${\$ 중 두 개라도 연결된$$ 것과 같으므로 원본 그래프가 연결되었는지도 확인할 수 있다.^[5]
• 투테 다항식
• 특성 다항식
• 평면성
• 그래프의 스패닝 트리 유형
• 색다항식
• 완벽한 그래프, 간격 그래프 또는 다른 완벽한 그래프의^[6] 하위 클래스인 경우

검증

재구성 및 세트 재구성 추측 모두 브렌던 맥케이에 의해 최대 11 정점을 가진 모든 그래프에 대해 검증되었다.^[7]

확률론적 의미에서, Béla Bollobas는 거의 모든 그래프가 재구성 가능하다는 것을 보여주었다.^[8]즉, $n{\displaystyle }$ ${\displaystyle n}$ 정점에서$$ 임의로 선택한 그래프가 재구성할 수 없는 확률은 $n{\displaystyle }$ ${\displaystyle n}$이(가) 무한대로 이동하기$$ 때문에 0이 된다.사실, 거의 모든 그래프를 재구성할 수 있을 뿐만 아니라, 실제로 전체 그래프를 재구성할 필요가 없다는 것이 밝혀졌다. 거의 모든 그래프는 그래프를 고유하게 결정하는 세 장의 카드가 갑판에 존재한다는 속성을 가지고 있다.

재구성 가능한 그래프 패밀리

그 추측은 수많은 무한 등급의 그래프(그리고, 사소한 것으로, 그들의 보완물)에 대해 검증되었다.

• 일반 그래프^[9] - 일반 그래프는 그래프의 데크에서 인식할 수 있는 일부 사실을 직접 적용하여 재구성할 수 있다.$n{\displaystyle }$ ${\displaystyle n}$ - 정규$$ $그래프{\displaystyle }$ G ${\displaystyle G}$ 및 그$$ $데크{\displaystyle }$ D${\displaystyle (G)}$ ${\displaystyle D(G)}$을(를) 볼 때$,$ 우리는 데크의 도열을 인식함으로써 데크가 정규 그래프임을 인식할 수 있다.이제 갑판 $D{\displaystyle }$( ${\displaystyle G}$) ${\displaystyle D(G)},$G ${\displaystyle i_{}}$ ${\$의 한 멤버를 살펴보도록 합시다$.$이 그래프에는 $n{\displaystyle }${\$displaystyle$ $n$$}$의 정도인 $정점$과${\displaystyle }$$n{\displaystyle }$ $-$ ${\displaystyle 1}$의 정도인$$정점이$$ 몇 개 포함되어 있다$.$ 이 그래프에 정점을 추가한 다음 $n{\displaystyle }$ -${\displaystyle 1}$의 $정도{\displaystyle }$ n ${\displaystyle$ $n-1$$}$의 정점에$$ 연결하여$$ $n{\displaystyle }$ ${\\$displaystyle n-1}을 생성할 수 있다.$displaystyle n}$ - 우리가 시작한 그래프와 이형화된 정규$$ 그래프.따라서 모든 일반 그래프는 갑판에서 재구성할 수 있다.흥미로운 일반 그래프의 특정 유형은 전체 그래프다.^[5]
• 나무들^[9]
• 연결이 끊긴 그래프^[9]
• 단위 구간 그래프 ^[6]
• 끝 정점이^[10] 없는 분리 가능한 그래프
• 최대 평면 그래프
• 최대 외부 평면 그래프
• 외부 평면 그래프
• 임계블록

축소

2개의 연결 그래프를 모두 재구성할 수 있다면 재구성 추측이 맞다.^[11]

이중성

정점 재구성 추측에 $따르면{\displaystyle }$, G ${\displaystyle G}$을(를) 정점 $데크{\displaystyle }$ D${\displaystyle }$( G${\displaystyle }$) ${\displaystyle$ $D$$(G$$)\}$에서 재구성할$$ 수 있는 경우, 다음과 같이$$ 보완 $\$ {\$displaystyle$ G$'}$을(를$)$ D ( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$)에서 재구성할 수 있다$$.$D{\displaystyle }$${\displaystyle (G}$ ${\displaystyle {\prime }^{}}$) ${\displaystyle$ $D$$(G')}$로 시작하고$,$ $D{\displaystyle }$(G ) {\$displaystyle$ $D$$(G)}$을(를$)$ 얻기 위해 그 안에 있는 모든 카드의 보완을 취하고$,$ 이를 사용하여 $G{\displaystyle }$ ${\displaystyle$ G$}$을(를) 재구성하고$,$ $다시{\displaystyle {}^{}}$ 보완하여 G${\displaystyle {}^{}}$get ${\$ G'}을 얻으십시오$.$

에지 재구성은 다음과 같은 이중성을 준수하지 않는다.실제로, 일부 에지 재구성 가능한 그래프의 경우 이들의 보완이 에지 재구성 가능한지 여부는 알려지지 않았다.

기타 구조물

다음은 일반적으로 재구성할 수 없는 것으로 나타났다.

• 디그라프:대회(스톡마이어^[12])와 비관광(스톡마이어^[13]) 등 무한의 비재건성 디그그래프 가족이 알려져 있다.토너먼트는 강하게 연결되지 않으면 재구성할 수 있다.^[14]더 약한 버전의 재건 추측이 디그라프에 대해 추측되었다. 새로운 디그라프 재건 추측을 보라.
• 하이퍼그래프(코케이^[15])
• 무한 그래프.모든 꼭지점이 무한정 많은 정점에 T를 나무가 되게 하고, NT를 T의 n개 사본의 분리 결합이 되게 한다.이 그래프들은 고형질이므로 재구성할 수 없다.이러한 그래프의 모든 정점 삭제 하위 그래프는 이형적이다: 그것들은 모두 T의 무한한 수의 복사본의 분리된 결합이다.
• 국소적으로 유한한 그래프.지역적으로 유한한 무한 나무의 재구성성 문제(1972년부터의 하라리-슈웬크-스코트 추측)는 보울러 외 연구원이 최대 3도의 비재구성 나무를 발견한 2017년까지 오랫동안 열려 있던 문제였다.^[16]

참고 항목

• 새로운 디그라프 재건 추측
• 부분대칭

추가 읽기

이 주제에 대한 자세한 내용은 내시윌리엄스의 설문조사를 참조하십시오.^[17]

참조