Informell sagt die Rekonstruktionsvermutung in der Graph-Theorie, dass Graphen einzigartig durch ihre Subgraphen bestimmt werden. Es ist wegen Kellys und Ulams.

Formelle Behauptungen

In Anbetracht eines Graphen ist ein Scheitelpunkt-gelöschter Subgraph dessen ein gebildeter Subgraph durch das Löschen genau eines Scheitelpunkts davon. Klar ist es ein veranlasster Subgraph dessen.

Für einen Graphen ist das Deck von G, angezeigt, der Mehrsatz aller Scheitelpunkt-gelöschten Subgraphen dessen. Jeder Graph darin wird eine Karte genannt. Wie man sagt, sind zwei Graphen, die dasselbe Deck haben, hypomorphic.

Mit diesen Definitionen kann die Vermutung als festgesetzt werden:

Rekonstruktionsvermutung: Irgendwelche zwei hypomorphic Graphen auf mindestens drei Scheitelpunkten sind isomorph.

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

Harary hat eine stärkere Version der Vermutung vorgeschlagen:

Satz-Rekonstruktionsvermutung: Irgendwelche zwei Graphen auf mindestens vier Scheitelpunkten mit denselben Sätzen von Scheitelpunkt-gelöschten Subgraphen sind isomorph.

In Anbetracht eines Graphen ist ein Rand-gelöschter Subgraph dessen ein gebildeter Subgraph durch das Löschen genau eines Randes davon.

Für einen Graphen ist das Rand-Deck von G, angezeigt, der Mehrsatz aller Rand-gelöschten Subgraphen dessen. Jeder Graph darin wird eine Rand-Karte genannt.

Rand-Rekonstruktionsvermutung: (Harary, 1964) Irgendwelche zwei Graphen mit mindestens vier Rändern und dieselben Rand-Decks zu haben, sind isomorph.

Überprüfung

Beide die Rekonstruktion und Satz-Rekonstruktionsvermutungen sind für alle Graphen mit höchstens 11 Scheitelpunkten (McKay) nachgeprüft worden.

In einem probabilistic Sinn ist ihm (Bollobás) gezeigt worden, dass fast alle Graphen reconstructible sind. Das bedeutet, dass die Wahrscheinlichkeit, dass ein zufällig gewählter Graph auf Scheitelpunkten nicht reconstructible ist, zu 0 geht, wie zur Unendlichkeit geht. Tatsächlich wurde es gezeigt, dass nicht nur fast alle Graphen reconstructible, aber tatsächlich sind, dass das komplette Deck nicht notwendig ist, sie wieder aufzubauen - haben fast alle Graphen das Eigentum, dass dort drei Karten in ihrem Deck bestehen, die einzigartig den Graphen bestimmen.

Graph-Familien von Reconstructible

Die Vermutung ist für mehrere unendliche Klassen von Graphen nachgeprüft worden.

• Regelmäßige Graphen
• Bäume
• Getrennte Graphen
• Einheitszwischenraum-Graphen
• Trennbare Graphen ohne Endscheitelpunkte
• Maximale planare Graphen
• Maximale Outerplanar Graphen
• Planare Außengraphen
• Kritische Blöcke

Erkennbare Eigenschaften

Im Zusammenhang der Rekonstruktionsvermutung wird ein Graph-Eigentum erkennbar genannt, wenn man das Eigentum vom Deck eines Graphen bestimmen kann. Die folgenden Eigenschaften von Graphen sind erkennbar:

• Grad-Folge
• Polynom von Tutte
• Planarity
• Die Typen, Bäume in einem Graphen abzumessen
• Chromatisches Polynom
• Ein vollkommener Graph oder ein Zwischenraum-Graph oder einige andere Unterklassen von vollkommenen Graphen seiend

Die Verminderung

Die Rekonstruktionsvermutung ist wahr, wenn alle 2-verbundenen Graphen reconstructible sind

Andere Strukturen

Es ist gezeigt worden, dass der folgende nicht in allgemeinem reconstructible ist:

• Digraphe: Unendliche Familien von non-reconstructible Digraphen, sind einschließlich Turniere (Stockmeyer) und Nichtturniere (Stockmeyer) bekannt. Ein Turnier ist reconstructible, wenn es nicht stark verbunden wird.
• Hypergraphen (Kocay).
• Unendliche Graphen. Lassen Sie T ein Baum auf einer unendlichen Zahl von solchen Scheitelpunkten sein, dass jeder Scheitelpunkt unendlichen Grad hat. Das Gegenbeispiel ist T und 2T. Die Frage von reconstructibility für lokal begrenzte unendliche Graphen ist noch offen.

Siehe auch

• Neue Digraph-Rekonstruktion vermutet

Weiterführende Literatur

Für die weitere Information über dieses Thema, sieh den Überblick von Nash-Williams.