Rekonstruktion gissningar - Reconstruction conjecture

Olöst problem i matematik :

Är grafer unikt bestämda av deras underbilder?

Informellt säger rekonstruktionsgissningarna i grafteorin att grafer bestäms unikt av deras underbilder. Det beror på Kelly och Ulam .

Formella uttalanden

En graf och tillhörande däck med en-vertex-raderade underbilder. Observera att några av korten visar isomorfa grafer.

Med ett diagram är en topp-raderad delgraf av en subgraf som bildas genom att ta bort exakt ett toppunkt från . Per definition är det en inducerad subgraf av . ${\ displaystyle G = (V, E)}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle G}$

För ett diagram är däck av G , betecknat , multiset av isomorfismklasser för alla vertex-raderade underbilder av . Varje graf i kallas ett kort . Två grafer som har samma däck sägs vara hypomorfa . ${\ displaystyle G}$ ${\ displaystyle D (G)}$ ${\ displaystyle G}$ ${\ displaystyle D (G)}$

Med dessa definitioner kan antagandet anges som:

Rekonstruktionskonjektion: Alla två hypomorfa grafer på minst tre hörn är isomorfa.

(Kravet att graferna ska ha minst tre hörn är nödvändigt eftersom båda graferna på två hörn har samma däck.)

Harary föreslog en starkare version av antagandet:

Ange rekonstruktionsförmodningar: Alla två grafer på minst fyra hörn med samma uppsättningar av vertex-raderade underbilder är isomorfa.

Med ett diagram är en kantraderad undergraf av en subgraf som bildas genom att ta bort exakt en kant från . ${\ displaystyle G = (V, E)}$ ${\ displaystyle G}$ ${\ displaystyle G}$

För ett diagram är kantdäcket av G , betecknat , multiset av alla isomorfismklasser av kantraderade underbilder av . Varje graf i kallas ett kantkort . ${\ displaystyle G}$ ${\ displaystyle ED (G)}$ ${\ displaystyle G}$ ${\ displaystyle ED (G)}$

Edge Reconstruction Conjecture: (Harary, 1964) Två grafer med minst fyra kanter och med samma kantdäck är isomorfa.

Kännbara egenskaper

I samband med rekonstruktionen gissningar, en graf egenskap kallas igenkännbar om man kan bestämma egendom från däcket på en graf. Följande egenskaper för grafer är igenkännliga:

Ordning av grafen - Ordningen på en graf , kan kännas igen från som Multiset innehåller varje subgraf av skapat genom deletion en vertex . Därav ${\ displaystyle G}$ ${\ displaystyle | V (G) |}$ ${\ displaystyle D (G)}$ ${\ displaystyle D (G)}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle | V (G) | = | D (G) |}$
Antalet kanter i diagrammet - Antalet kanter i ett diagram med hörn är igenkännligt. Observera först att varje kant av förekommer hos medlemmar i . Detta är sant genom att definitionen säkerställer att varje kant inkluderas varje gång var och en av de hörn som det händer med ingår i en del av , så en kant kommer att inträffa i varje medlem utom för de två där dess slutpunkter är raderade. Därför där är antalet kanter i I e medlem . ${\ 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)}$
Gradsekvens - Gradsekvensen för ett diagram är igenkännlig eftersom graden för varje toppunkt är igenkännlig. För att hitta graden av ett hörn -Den vertex frånvarande från i : e medlem - vi kommer att undersöka grafen skapas genom att ta bort den, . Den här grafen innehåller alla kanter som inte inträffar , så om är antalet kanter i , då . Om vi kan säga graden för varje toppunkt i diagrammet, kan vi berätta om gradssekvensen för diagrammet. ${\ 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})}$
(Vertex-) Anslutbarhet - Per definition är en graf -vertex-ansluten när du tar bort ett toppunkt skapar en -vertex-ansluten graf; alltså, om varje kort är en -vertex-ansluten graf, vet vi att den ursprungliga grafen var -vertex-ansluten. Vi kan också avgöra om den ursprungliga grafen var ansluten, eftersom det motsvarar att ha två av de som är anslutna. ${\ displaystyle n}$ ${\ displaystyle n-1}$ ${\ displaystyle n-1}$ ${\ displaystyle n}$ ${\ displaystyle G_ {i}}$
Tutte polynom
Karakteristisk polynom
Planhet
Typerna av spännande träd i en graf
Kromatisk polynom
Att vara en perfekt graf eller ett intervallgraf eller vissa andra underklasser av perfekta grafer

Verifiering

Både rekonstruktions- och uppsatta rekonstruktionsförmodningar har verifierats för alla grafer med högst elva hörn av Brendan McKay .

I sannolikhet har Béla Bollobás visat att nästan alla grafer är rekonstruerbara. Detta innebär att sannolikheten för att ett slumpmässigt valt diagram på hörn inte är rekonstruerbart går till 0 som går till oändligheten. I själva verket visades det att inte bara nästan alla grafer är rekonstruerbara, utan faktiskt att hela kortlek inte är nödvändigt för att rekonstruera dem - nästan alla grafer har den egenskapen att det finns tre kort i deras kortlek som unikt bestämmer grafen. ${\ displaystyle n}$ ${\ displaystyle n}$

Rekonstruerbara diagramfamiljer

Antagandet har verifierats för ett antal oändliga klasser av grafer (och, triviellt, deras komplement).

Regelbundna grafer - Regelbundna grafer kan rekonstrueras genom direkt tillämpning av några av de fakta som kan kännas igen från grafens kortlek. Med tanke på ett regelbundet diagram och dess däck kan vi känna igen att däcket har en vanlig graf genom att känna igen dess gradssekvens. Låt oss nu undersöka en medlem av däcket , . Denna graf innehåller ett antal antal hörn med en grad av och hörn med en grad av . Vi kan lägga till ett toppunkt i den här grafen och sedan ansluta den till graderna för att skapa en -regelbunden graf som är isomorf till den graf som vi började med. Därför är alla vanliga diagram rekonstruerbara från deras däck. En speciell typ av vanligt diagram som är intressant är hela grafen. ${\ 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}$
Träd
Frånkopplade diagram
Enhetsintervalldiagram
Separabla diagram utan ändhörnor
Maximala plana grafer
Maximala yttre plana grafer
Ytterplanära grafer
Kritiska block

Minskning

Rekonstruktionens gissningar är sanna om alla 2-anslutna grafer är rekonstruerbara.

Dualitet

Gissning av vertexrekonstruktionen följer dualiteten att om det kan rekonstrueras från dess toppdäck , kan dess komplement rekonstrueras från följande: Börja med , ta komplementet till varje kort i det för att få , använd detta för att rekonstruera , ta sedan komplementet igen för att få . ${\ displaystyle G}$ ${\ displaystyle D (G)}$ ${\ displaystyle G '}$ ${\ displaystyle D (G ')}$ ${\ displaystyle D (G ')}$ ${\ displaystyle D (G)}$ ${\ displaystyle G}$ ${\ displaystyle G '}$

Kantrekonstruktion följer inte någon sådan dualitet: För vissa klasser av kantrekonstruerbara grafer är det inte känt om deras komplement är kantrekonstruerbara.

Andra strukturer

Det har visat sig att följande inte är generellt rekonstruerbara:

Digraphs : Oändliga familjer av icke-rekonstruerbara digraphs är kända, inklusive turneringar (Stockmeyer) och icke-turneringar (Stockmeyer). En turnering kan rekonstrueras om den inte är starkt kopplad. En svagare version av rekonstruktionsgissningen har antagits för digrafier, se ny gissningsrekonstruktion .
Hypergraphs ( Kocay ).
Oändliga diagram . Låt T vara ett träd på ett oändligt antal hörn så att varje toppunkt har oändlig grad, och låt n T vara den ojämna sammansättningen av n kopior av T. Dessa grafer är hypomorfa och därmed inte rekonstruerbara. Varje vertex-raderad underbild av någon av dessa grafer är isomorf: de är alla den ojämna sammansättningen av ett oändligt antal kopior av T.
Lokalt begränsade grafer. Frågan om rekonstruerbarhet för oändliga lokalt oändliga träd (antagandet Harary-Schwenk-Scott från 1972) var ett långvarigt öppet problem fram till 2017, då ett icke-rekonstruerbart träd av maximal grad 3 hittades av Bowler et al.

Se även

Vidare läsning

För mer information om detta ämne, se undersökningen av Nash-Williams .

Languages

In other projects