Przypuszczenie Barnette'a

Nierozwiązany problem z matematyki :

Czy każdy dwudzielny prosty wielościan jest hamiltonianem?

(więcej nierozwiązanych problemów z matematyki)

Hipoteza Barnette'a jest nierozwiązanym problemem w teorii grafów , gałęzi matematyki , dotyczącym cykli Hamiltona w grafach. Jej nazwa pochodzi od Davida W. Barnette'a, emerytowanego profesora na Uniwersytecie Kalifornijskim w Davis ; stwierdza, że ​​​​każdy dwudzielny graf wielościenny z trzema krawędziami na wierzchołek ma cykl Hamiltona.

Definicje

Graf planarny to graf nieskierowany , który można umieścić na płaszczyźnie euklidesowej bez żadnych przecięć . Graf planarny nazywamy wielościennym wtedy i tylko wtedy, gdy jest spójny w 3 wierzchołkach , to znaczy, gdy nie istnieją dwa wierzchołki, których usunięcie spowodowałoby rozłączenie reszty grafu. Graf jest dwudzielny , jeśli jego wierzchołki można pokolorować dwoma różnymi kolorami, tak że każda krawędź ma jeden punkt końcowy każdego koloru. Graf jest sześcienny (lub 3-regularny ), jeśli każdy wierzchołek jest punktem końcowym dokładnie trzech krawędzi. Wreszcie, graf jest hamiltonowski , jeśli istnieje cykl, który przechodzi przez każdy z jego wierzchołków dokładnie raz. Hipoteza Barnette'a stwierdza, że ​​​​każdy dwudzielny graf wielościenny sześcienny jest hamiltonowski.

Zgodnie z twierdzeniem Steinitza graf planarny przedstawia krawędzie i wierzchołki wypukłego wielościanu wtedy i tylko wtedy, gdy jest wielościenny. Trójwymiarowy wielościan ma graf sześcienny wtedy i tylko wtedy, gdy jest prostym wielościanem . I graf planarny jest dwudzielny wtedy i tylko wtedy, gdy w planarnym osadzeniu grafu wszystkie cykle twarzy mają parzystą długość. Dlatego hipotezę Barnette'a można sformułować w równoważnej postaci: załóżmy, że trójwymiarowy prosty wypukły wielościan ma parzystą liczbę krawędzi na każdej ze swoich ścian. Wtedy, zgodnie z przypuszczeniem, wykres wielościanu ma cykl Hamiltona.

Historia

PG Tait ( 1884 ) przypuszczał, że każdy sześcienny graf wielościenny jest hamiltonowski; stało się to znane jako przypuszczenie Taita . Zostało to obalone przez WT Tutte ( 1946 ), który skonstruował kontrprzykład z 46 wierzchołkami; inni badacze znaleźli później jeszcze mniejsze kontrprzykłady. Jednak żaden z tych znanych kontrprzykładów nie jest dwudzielny. Sam Tutte przypuszczał, że każdy sześcienny 3-połączony graf dwudzielny jest hamiltonowski, ale odkrycie kontrprzykładu, wykresu Hortona , wykazało, że jest to fałszywe . David W. Barnette ( 1969 ) zaproponował osłabioną kombinację hipotez Taita i Tutte'a, stwierdzając, że każdy dwudzielny wielościan sześcienny jest hamiltonowski, lub równoważnie, że każdy kontrprzykład do hipotezy Taita nie jest dwudzielny.

Równoważne formy

Kelmans (1994) wykazał, że hipoteza Barnette'a jest równoważna z powierzchownie silniejszym stwierdzeniem, że dla każdych dwóch krawędzi e i f na tej samej ścianie dwudzielnego wielościanu sześciennego istnieje cykl Hamiltona, który zawiera e , ale nie zawiera f . Oczywiście, jeśli to stwierdzenie jest prawdziwe, to każdy dwudzielny wielościan sześcienny zawiera cykl Hamiltona: po prostu wybierz e i f arbitralnie. W innych kierunkach Kelmans wykazał, że kontrprzykład można przekształcić w kontrprzykład dla pierwotnej hipotezy Barnette'a.

Hipoteza Barnette'a jest również równoważna stwierdzeniu, że wierzchołki dwójki każdego sześciennego dwudzielnego grafu wielościennego można podzielić na dwa podzbiory, których indukowanymi podgrafami są drzewa. Cięcie wywołane przez taki podział na grafie dualnym odpowiada cyklowi Hamiltona na grafie pierwotnym.

Wyniki częściowe

Chociaż prawdziwość hipotezy Barnette'a pozostaje nieznana, eksperymenty obliczeniowe wykazały, że nie ma kontrprzykładu z mniej niż 86 wierzchołkami.

Jeśli przypuszczenie Barnette'a okaże się fałszywe, to można wykazać, że jest NP-zupełne , aby sprawdzić, czy dwudzielny sześcienny wielościan jest hamiltonowski. Jeśli graf planarny jest dwudzielny i sześcienny, ale tylko o łączności 2, to może być niehamiltonowski, a testowanie hamiltoniczności dla tych grafów jest NP-zupełne. Inny wynik uzyskali Alt i in. (2016) : jeśli graf dualny może być pokolorowany kolorami wierzchołków kolorami niebieskim, czerwonym i zielonym, tak że każdy czerwono-zielony cykl zawiera wierzchołek stopnia 4, to graf pierwotny jest hamiltonowski.

Powiązane problemy

Pokrewne przypuszczenie Barnette'a stwierdza, że ​​​​każdy sześcienny graf wielościenny, w którym wszystkie ściany mają sześć lub mniej krawędzi, jest hamiltonowski. Eksperymenty obliczeniowe wykazały, że gdyby istniał kontrprzykład, musiałby mieć więcej niż 177 wierzchołków. Przypuszczenie zostało udowodnione przez Kardoša (2020) .

Przecięcie tych dwóch przypuszczeń byłoby takie, że każdy dwudzielny sześcienny graf wielościenny, w którym wszystkie ściany mają cztery lub sześć krawędzi, jest hamiltonowski. Udowodnił to Goodey (1975) .

Notatki

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Barnette%27s_conjecture&oldid=1117475410 ”