Rekonstruktionsvermutung - Reconstruction conjecture

Informell besagt die Rekonstruktionsvermutung in der Graphentheorie , dass Graphen eindeutig durch ihre Teilgraphen bestimmt werden. Es ist Kelly und Ulam zu verdanken .

Formale Erklärungen

Ein Graph und das zugehörige Deck von Einzelknoten-gelöschten Untergraphen. Beachten Sie, dass einige der Karten isomorphe Graphen zeigen.

Bei einem gegebenen Graphen ist ein knotengelöschter Untergraph von ein Untergraph , der durch Löschen genau eines Knotens von gebildet wird . Per Definition ist es ein induzierter Teilgraph von . ${\displaystyle G=(V,E)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

Für einen Graphen ist das Deck von G , bezeichnet mit , die Mehrfachmenge von Isomorphismusklassen aller knotengelöschten Teilgraphen von . Jeder Graph in wird als Karte bezeichnet . Zwei Graphen mit dem gleichen Deck werden als hypomorph bezeichnet . ${\displaystyle G}$${\displaystyle D(G)}$${\displaystyle G}$${\displaystyle D(G)}$

Mit diesen Definitionen kann die Vermutung wie folgt ausgedrückt werden:

• Rekonstruktionsvermutung: Zwei beliebige hypomorphe Graphen auf mindestens drei Ecken sind isomorph.

(Die Anforderung, dass die Graphen mindestens drei Scheitelpunkte haben, ist notwendig, da beide Graphen auf zwei Scheitelpunkten dieselben Decks haben.)

Harary schlug eine stärkere Version der Vermutung vor:

• Satzrekonstruktionsvermutung: Zwei beliebige Graphen auf mindestens vier Knoten mit den gleichen Sätzen von knotengelöschten Untergraphen sind isomorph.

Bei einem gegebenen Graphen ist ein kantengelöschter Teilgraph von ein Teilgraph , der durch das Löschen genau einer Kante aus gebildet wird . ${\displaystyle G=(V,E)}$${\displaystyle G}$${\displaystyle G}$

Für eine grafische Darstellung , die kanten Deck G , bezeichnet , ist die multiset aller Isomorphieklassen kanten gelöscht Subgraphen von . Jeder Graph in wird als Edge-Card bezeichnet . ${\displaystyle G}$${\displaystyle ED(G)}$${\displaystyle G}$${\displaystyle ED(G)}$

• Kantenrekonstruktionsvermutung: (Harary, 1964) Zwei beliebige Graphen mit mindestens vier Kanten und mit den gleichen Kantendecks sind isomorph.

Erkennbare Eigenschaften

Im Kontext der Rekonstruktionsvermutung wird eine Diagrammeigenschaft als erkennbar bezeichnet, wenn man die Eigenschaft aus dem Deck eines Diagramms bestimmen kann. Folgende Eigenschaften von Graphen sind erkennbar:

• Ordnung des Graphen - der Reihenfolge eines Graphen , ist erkennbar , wie die multiset enthält jedes Teilgraph von durch das Löschen eines Scheitelpunkt erstellt . Daher${\displaystyle G}$${\displaystyle |V(G)|}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle |V(G)|=|D(G)|}$
• Anzahl der Kanten des Graphen – Die Anzahl der Kanten in einem Graphen mit Scheitelpunkten ist erkennbar. Beachten Sie zunächst, dass jede Kante von in Mitgliedern von auftritt . Dies trifft zu, indem sichergestellt wird, dass jede Kante jedes Mal eingeschlossen wird, wenn jeder der Scheitelpunkte, mit denen sie inzident ist, in einem Mitglied von enthalten ist , sodass eine Kante in jedem Mitglied von auftritt, außer in den beiden, in denen ihre Endpunkte liegen gelöscht. Daher , wo die Anzahl von Kanten in dem i - ten Element der .${\displaystyle G}$${\displaystyle n}$${\displaystyle |E(G)|}$${\displaystyle G}$${\displaystyle n-2}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle |E(G)|=\sum {\frac {q_{i}}{n-2}}}$${\displaystyle q_{i}}$${\displaystyle D(G)}$
• Gradfolge – Die Gradfolge eines Graphen ist erkennbar, weil der Grad jedes Scheitelpunkts erkennbar ist. Um den Grad eines Scheitelpunkts zu ermitteln – dem Scheitelpunkt, der im i- ten Glied von fehlt – untersuchen wir den durch Löschen erzeugten Graphen, . Dieser Graph enthält alle Kanten, die nicht mit einfallen. Wenn also die Anzahl der Kanten in ist , dann . Wenn wir den Grad jedes Knotens im Graphen bestimmen können, können wir die Gradfolge des Graphen bestimmen.${\displaystyle G}$${\displaystyle v_{i}}$${\displaystyle D(G)}$${\displaystyle G_{i}}$${\displaystyle v_{i}}$${\displaystyle q_{i}}$${\displaystyle G_{i}}$${\displaystyle |E(G)|-q_{i}=\deg(v_{i})}$
• (Scheitel-)Konnektivität – Per Definition ist ein Graph -Scheitelpunkt-verbunden, wenn das Löschen eines Scheitelpunkts einen -Scheitelpunkt-verbundenen Graphen erzeugt; Wenn also jede Karte ein mit einem Knoten verbundener Graph ist, wissen wir, dass der ursprüngliche Graph mit einem Knoten verbunden war. Wir können auch feststellen, ob der ursprüngliche Graph verbunden war, da dies gleichbedeutend ist mit zwei beliebigen verbundenen.${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle G_{i}}$
• Tutte-Polynom
• Charakteristisches Polynom
• Planarität
• Die Arten von Spannbäumen in einem Graphen
• Chromatisches Polynom
• Ein perfekter Graph oder ein Intervallgraph oder bestimmte andere Unterklassen von perfekten Graphen sein

Überprüfung

Sowohl die Rekonstruktions- als auch die Mengenrekonstruktionsvermutung wurden von Brendan McKay für alle Graphen mit höchstens 11 Knoten verifiziert .

Im probabilistischen Sinne hat Béla Bollobás gezeigt, dass fast alle Graphen rekonstruierbar sind. Dies bedeutet, dass die Wahrscheinlichkeit, dass ein zufällig ausgewählter Graph auf Knoten nicht rekonstruierbar ist, gegen 0 geht wie gegen unendlich. Tatsächlich wurde gezeigt, dass nicht nur fast alle Graphen rekonstruierbar sind, sondern dass nicht das gesamte Deck notwendig ist, um sie zu rekonstruieren – fast alle Graphen haben die Eigenschaft, dass es in ihrem Deck drei Karten gibt, die den Graphen eindeutig bestimmen. ${\displaystyle n}$${\displaystyle n}$

Rekonstruierbare Graphfamilien

Die Vermutung wurde für eine Reihe von unendlichen Klassen von Graphen (und trivialerweise für ihre Komplemente) verifiziert.

• Reguläre Graphen - Reguläre Graphen sind rekonstruierbar durch direkte Anwendung einiger der Fakten, die aus dem Deck eines Graphen erkannt werden können. Bei einem gegebenen -regulären Graphen und seinem Deck können wir erkennen, dass es sich bei dem Deck um einen regulären Graphen handelt, indem wir seine Gradfolge erkennen. Lassen Sie uns nun ein Mitglied des Decks untersuchen , . Dieser Graph enthält eine Anzahl von Scheitelpunkten mit einem Grad von und Scheitelpunkten mit einem Grad von . Wir können diesem Graphen einen Knoten hinzufügen und ihn dann mit den Gradknoten verbinden , um einen -regulären Graphen zu erstellen, der isomorph zu dem Graphen ist, mit dem wir begonnen haben. Daher sind alle regulären Graphen aus ihren Decks rekonstruierbar. Eine bestimmte Art von regulärem Diagramm, die interessant ist, ist das vollständige Diagramm.${\displaystyle n}$${\displaystyle G}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle G_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n}$
• Bäume
• Getrennte Diagramme
• Einheitenintervalldiagramme
• Trennbare Graphen ohne Endknoten
• Maximal planare Graphen
• Maximale äußereplanare Graphen
• Äußereplanare Graphen
• Kritische Blöcke

Die Ermäßigung

Die Rekonstruktionsvermutung ist wahr, wenn alle 2-zusammenhängenden Graphen rekonstruierbar sind.

Dualität

Die Vertex-Rekonstruktions-Vermutung gehorcht der Dualität, dass, wenn sie aus ihrem Vertex-Deck rekonstruiert werden kann , ihr Komplement wie folgt rekonstruiert werden kann: Beginnen Sie mit , nehmen Sie das Komplement jeder Karte darin, um zu erhalten , verwenden Sie dies, um zu rekonstruieren , und nehmen Sie dann das Komplement wieder zu bekommen . ${\displaystyle G}$${\displaystyle D(G)}$${\displaystyle G'}$${\displaystyle D(G')}$${\displaystyle D(G')}$${\displaystyle D(G)}$${\displaystyle G}$${\displaystyle G'}$

Die Kantenrekonstruktion gehorcht keiner solchen Dualität: Tatsächlich ist für einige Klassen von kantenrekonstruierbaren Graphen nicht bekannt, ob ihre Komplemente kantenrekonstruierbar sind.

Andere Strukturen

Es hat sich gezeigt , dass die folgenden sind nicht im allgemeinen rekonstruierbar:

• Digraphen : Unendliche Familien von nicht rekonstruierbaren Digraphen sind bekannt, darunter Turniere (Stockmeyer) und Nicht-Turniere (Stockmeyer). Ein Turnier ist rekonstruierbar, wenn es nicht stark verbunden ist. Für Digraphen wurde eine schwächere Version der Rekonstruktionsvermutung vermutet, siehe neue Digraph-Rekonstruktionsvermutung .
• Hypergraphen ( Kocay ).
• Unendliche Graphen . Sei T ein Baum auf unendlich vielen Knoten, so dass jeder Knoten unendlichen Grad hat, und sei n T die disjunkte Vereinigung von n Kopien von T. Diese Graphen sind hypomorph und somit nicht rekonstruierbar. Jeder knotengelöschte Teilgraph eines dieser Graphen ist isomorph: Sie alle sind die disjunkte Vereinigung einer unendlichen Anzahl von Kopien von T.
• Lokal endliche Graphen. Die Frage der Rekonstruierbarkeit für lokal endliche unendliche Bäume (Harary-Schwenk-Scott-Vermutung aus dem Jahr 1972) war bis 2017 ein seit langem offenes Problem, als Bowler et al.

Siehe auch

• Neue Vermutung zur Rekonstruktion des Digraphen
• Partielle Symmetrie

Weiterlesen

Weitere Informationen zu diesem Thema finden Sie in der Umfrage von Nash-Williams .

Verweise