Conjectura lui Barnett este o problemă nerezolvată în teoria grafurilor despre existența ciclurilor hamiltoniene în grafuri. Ipoteza este numită după David W. Barnett, emerit al Universității din California, Davis . Conjectura afirmă că orice graf politop bipartit cu trei muchii la fiecare vârf are un ciclu hamiltonian.
Un graf plan este un graf nedirecționat care poate fi încorporat într-un spațiu euclidian fără intersecții . Un graf plan se spune că este poliedric (sau un graf politop) dacă și numai dacă este conectat la vârf 3 , adică dacă nu există două vârfuri a căror eliminare împarte graficul în două (sau mai multe) grafice. Un grafic se numește bipartit dacă vârfurile sale pot fi colorate în două culori, astfel încât fiecare muchie să conecteze vârfuri de culori diferite. Un grafic se numește cubic (sau 3-regular ) dacă fiecare vârf este capătul exact a trei muchii. În cele din urmă, un grafic hamiltonian , dacă există un ciclu care trece prin toate vârfurile exact o dată. Conjectura lui Barnett afirmă că orice graf bipartit cubic este un politop hamiltonian.
După teorema lui Steinitz , un graf plan reprezintă muchiile și vârfurile unui poliedru convex dacă și numai dacă este poliedric. Un 3-politop formează un grafic cubic dacă și numai dacă este simplu . Un graf plan este bipartit dacă și numai dacă în înglobarea sa plană toate ciclurile de fețe (limite) sunt de lungime uniformă. Astfel, conjectura lui Barnett poate fi formulată într-o formă echivalentă. Imaginează-ți că un poliedru convex simplu tridimensional are un număr par de muchii în fiecare față. Apoi, conform conjecturii, graficul poliedrului are un ciclu hamiltonian.
În 1884, Tate a presupus că orice graf poliedric cubic este hamiltonian. Această presupunere este acum cunoscută sub numele de conjectura Tate . Conjectura a fost respinsă de Tatt în 1946 [1] prin construirea unui contraexemplu cu 46 de vârfuri. Alți cercetători au găsit mai târziu contraexemple mai mici, dar niciunul dintre aceste contraexemple nu este bipartit. Tutt însuși a presupus că orice graf bipartit cubic cu 3 conexiuni este hamiltonian, dar a fost găsit un contraexemplu, graful Horton [2] [3] . David W. Barnett în 1969 [4] a propus o combinație slăbită a conjecturilor Tate și Tutt, afirmând că orice graf poliedric cubic bipartit este hamiltonian, sau echivalent, că orice contraexemplu al conjecturii Tate nu este bipartit.
Kelmans [5] a arătat că conjectura lui Barnett este echivalentă cu a spune că pentru oricare două muchii e și f de pe aceeași față a unui politop cubic bipartit, există un ciclu hamiltonian care conține e dar nu conține f . Este clar că, dacă afirmația este adevărată, atunci orice poliedric cubic bipartit conține un ciclu hamiltonian - alegeți doar e sau f . Într-o altă direcție, Kelman a arătat că un contraexemplu la această afirmație poate fi convertit într-un contraexemplu al conjecturii originale a lui Barnett.
Conjectura lui Barnett este, de asemenea, echivalentă cu afirmația că vârfurile grafului dual pentru orice graf poliedric bipartit cubic pot fi împărțite în două submulțimi, iar graficele generate pe aceste submulțimi sunt arbori. Secțiunea generată de o astfel de diviziune în graficul dual corespunde drumului hamiltonian din graficul original [6] .
Deși nu se știe dacă conjectura lui Barnett este corectă, experimentele de calcul arată că nu există un contraexemplu cu mai puțin de 86 de vârfuri [7] [8] .
Dacă se dovedește că conjectura lui Barnett este greșită, atunci se poate demonstra că verificarea dacă un politop cubic bipartit este hamiltonian este o problemă NP-completă [9] . Dacă un graf plan este bipartit și cubic, dar numai 2-conectat, atunci s-ar putea să nu fie hamiltonian, iar verificarea dacă un graf este hamiltonian este o problemă NP-completă [10] .
O presupunere legată de conjectura lui Barnette afirmă că orice graf poliedric cubic în care toate fețele au șase sau mai puține muchii este hamiltonian. Experimentele de calcul au arătat că, dacă există un contraexemplu, acesta va avea mai mult de 177 de vârfuri [11] .