Przypuszczenie rekonstrukcji - Reconstruction conjecture

Nieformalnie hipoteza rekonstrukcji w teorii grafów mówi, że grafy są jednoznacznie określone przez ich podgrafy. To zasługa Kelly i Ulama .

Oświadczenia formalne

Wykres i związana z nim talia podgrafów z usuniętymi pojedynczymi wierzchołkami. Zauważ, że niektóre karty przedstawiają wykresy izomorficzne.

Biorąc pod wykresem , zaledwie wierzchołkiem-usunięta subgraph o to subgraph utworzony poprzez usunięcie dokładnie jeden wierzchołek ze zbioru . Z definicji jest to indukowane subgraph od . ${\ Displaystyle G = (V, E)}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle G}$

Na wykresie , na pokładzie G , oznaczony , jest multiset klas Izomorfizm wszystkich subgraphs wierzchołków-delecją . Każdy wykres jest nazywany kartą . Mówi się, że dwa grafy, które mają tę samą talię, są hipomorficzne . ${\ Displaystyle G}$${\ Displaystyle D (G)}$${\ Displaystyle G}$${\ Displaystyle D (G)}$

Dzięki tym definicjom przypuszczenie można sformułować jako:

• Przypuszczenie rekonstrukcji: Dowolne dwa hipomorficzne wykresy na co najmniej trzech wierzchołkach są izomorficzne.

(Wymaganie, aby grafy miały co najmniej trzy wierzchołki, jest konieczne, ponieważ oba wykresy na dwóch wierzchołkach mają te same talie).

Harary zasugerował silniejszą wersję przypuszczenia:

• Hipoteza rekonstrukcji zestawu: dowolne dwa grafy na co najmniej czterech wierzchołkach z tymi samymi zestawami podgrafów z usuniętymi wierzchołkami są izomorficzne.

Biorąc pod uwagę wykres , podgraf z usuniętą krawędzią jest podgrafem utworzonym przez usunięcie dokładnie jednej krawędzi z . ${\ Displaystyle G = (V, E)}$${\ Displaystyle G}$${\ Displaystyle G}$

Na wykresie , na krawędzi pokładu G , oznaczony , jest multiset wszystkich klas Izomorfizm krawędzi subgraphs z delecją . Każdy wykres jest nazywany kartą krawędziową . ${\ Displaystyle G}$${\ Displaystyle ED (G)}$${\ Displaystyle G}$${\ Displaystyle ED (G)}$

• Hipoteza rekonstrukcji krawędzi: (Harary, 1964) Dowolne dwa grafy z co najmniej czterema krawędziami i takimi samymi taliami krawędzi są izomorficzne.

Rozpoznawalne właściwości

W kontekście hipotezy rekonstrukcji właściwość grafu nazywa się rozpoznawalną, jeśli można ją określić z pokładu grafu. Rozpoznawalne są następujące właściwości wykresów:

• Kolejność na wykresie - kolejność wykresie , jest rozpoznawalny z jak multiset zawiera każdy podgrafu z utworzonej przez usunięcie jednego wierzchołka . W związku z tym${\ Displaystyle G}$${\ displaystyle | V (G) |}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle | V (G) | = | D (G) |}$
• Liczba krawędzi grafu – Rozpoznawalna jest liczba krawędzi grafu z wierzchołkami . Najpierw zauważ, że każda krawędź elementu występuje w elementach . Odnosi się to do definicji, która zapewnia, że ​​każda krawędź jest uwzględniana za każdym razem, gdy każdy z wierzchołków, z którymi jest incydentem, jest zawarty w elemencie , więc krawędź wystąpi w każdym elemencie z wyjątkiem dwóch, w których jej punkty końcowe są usunięte. Stąd, gdzie jest liczba krawędzi w i- tym członie .${\ 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) | = \ suma {\ Frac {q_ {i}} {n-2}}}$${\displaystyle q_{i}}$${\ Displaystyle D (G)}$
• Sekwencja stopni - sekwencja stopni na wykresie jest rozpoznawalna, ponieważ stopień każdego wierzchołka jest rozpoznawalny. Aby znaleźć stopień wierzchołka — wierzchołek nieobecny w i- tym elemencie —, zbadamy wykres utworzony przez jego usunięcie, . Ten wykres zawiera wszystkie krawędzie, które nie są przypadkowe , więc jeśli jest to liczba krawędzi , to . Jeśli potrafimy określić stopień każdego wierzchołka na wykresie, możemy określić sekwencję stopni na wykresie.${\ 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} = \ stopni (V_ {i})}$
• Łączność (Vertex-) – Z definicji graf jest połączony z wierzchołkami, gdy usunięcie dowolnego wierzchołka tworzy graf połączony z wierzchołkami; tak więc, jeśli każda karta jest grafem połączonym wierzchołkami, wiemy, że oryginalny graf był połączony wierzchołkami. Możemy również określić, czy oryginalny wykres był połączony, ponieważ jest to równoważne posiadaniu dowolnych dwóch połączonych elementów.${\ Displaystyle n}$${\displaystyle n-1}$${\displaystyle n-1}$${\ Displaystyle n}$${\ Displaystyle G_ {i}}$
• Wielomian Tutte
• Wielomian charakterystyczny
• Płaskość
• Rodzaje drzew opinających na grafie
• Wielomian chromatyczny
• Bycie idealnym grafem lub grafem interwałowym lub pewnymi innymi podklasami doskonałych grafów

Weryfikacja

Zarówno przypuszczenia dotyczące rekonstrukcji, jak i rekonstrukcji zbioru zostały zweryfikowane dla wszystkich grafów z maksymalnie 11 wierzchołkami przez Brendana McKaya .

W sensie probabilistycznym Béla Bollobás wykazał, że prawie wszystkie wykresy można zrekonstruować. Oznacza to, że prawdopodobieństwo, że losowo wybrany graf na wierzchołkach nie jest rekonstruowalny, spada do 0, gdy idzie do nieskończoności. W rzeczywistości wykazano, że nie tylko prawie wszystkie grafy można zrekonstruować, ale w rzeczywistości cała talia nie jest konieczna do ich zrekonstruowania — prawie wszystkie grafy mają tę właściwość, że w ich talii znajdują się trzy karty, które jednoznacznie określają wykres. ${\ Displaystyle n}$${\ Displaystyle n}$

Rekonstruowalne rodziny grafów

Przypuszczenie zostało zweryfikowane dla wielu nieskończonych klas grafów (i, co jest trywialne, ich uzupełnień).

• Wykresy regularne — wykresy regularne można zrekonstruować poprzez bezpośrednie zastosowanie niektórych faktów, które można rozpoznać na podstawie wykresu. Mając graf regularny i jego talię , możemy rozpoznać, że talia jest grafem regularnym, rozpoznając jego ciąg stopni. Przyjrzyjmy się teraz jednemu członkowi talii , . Ten wykres zawiera pewną liczbę wierzchołków o stopniu i wierzchołków o stopniu . Możemy dodać wierzchołek do tego wykresu, a następnie połączyć go z wierzchołkami stopni, aby utworzyć wykres -regularny, który jest izomorficzny z wykresem, od którego zaczęliśmy. Dlatego wszystkie regularne wykresy można zrekonstruować z ich talii. Szczególnym typem regularnego wykresu, który jest interesujący, jest wykres kompletny.${\ 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}$
• Drzewa
• Odłączone wykresy
• Wykresy przedziałów jednostkowych
• Rozdzielne wykresy bez wierzchołków końcowych
• Maksymalne grafy planarne
• Maksymalne grafy zewnętrzne
• Wykresy zewnętrzne
• Bloki krytyczne

Zmniejszenie

Hipoteza rekonstrukcji jest prawdziwa, jeśli wszystkie 2-połączone grafy są rekonstruowalne.

Dwoistość

Hipoteza rekonstrukcji wierzchołków jest zgodna z dwoistością, że jeśli można ją zrekonstruować z talii wierzchołków , to jej dopełnienie można zrekonstruować w następujący sposób: Zacznij od , weź dopełnienie każdej karty, aby uzyskać , użyj tego do rekonstrukcji , a następnie weź dopełnienie ponownie, aby uzyskać . ${\ Displaystyle G}$${\ Displaystyle D (G)}$${\displaystyle G'}$${\ Displaystyle D (G ')}$${\ Displaystyle D (G ')}$${\ Displaystyle D (G)}$${\ Displaystyle G}$${\displaystyle G'}$

Rekonstrukcja krawędzi nie jest zgodna z żadną taką dwoistością: w rzeczywistości dla niektórych klas grafów rekonstruowalnych na krawędziach nie wiadomo, czy ich uzupełnienia są rekonstruowalne na krawędziach.

Inne konstrukcje

Wykazano, że zasadniczo nie da się odtworzyć:

• Digrafy : Znane są nieskończone rodziny nieodtwarzalnych digrafów , w tym turnieje (Stockmeyer) i nie-turniejowe (Stockmeyer). Turniej można odtworzyć, jeśli nie jest silnie powiązany. Słabsza wersja hipotezy rekonstrukcji została przypuszczona dla digrafów, patrz nowa hipoteza rekonstrukcji digrafów .
• Hipergrafy ( Kocay ).
• Nieskończone wykresy . Niech T będzie drzewem na nieskończonej liczby wierzchołków taki, że każdy wierzchołek ma nieskończoną stopnia i niech n T być unia rozłączne od n kopii T. Te wykresy są hypomorphic, a tym samym nie reconstructible. Każdy podgraf z usuniętym wierzchołkiem dowolnego z tych grafów jest izomorficzny: wszystkie są rozłączną sumą nieskończonej liczby kopii T.
• Grafy lokalnie skończone. Kwestia odtwarzalności dla lokalnie skończonych drzew nieskończonych (przypuszczenie Harary-Schwenk-Scott z 1972 r.) była od dawna otwartym problemem aż do 2017 r., kiedy Bowler i in.

Zobacz też

• Nowa hipoteza rekonstrukcji digrafu
• Częściowa symetria

Dalsza lektura

Więcej informacji na ten temat można znaleźć w ankiecie przeprowadzonej przez Nash-Williams .

Bibliografia