Кіріспе
Граф теориясындағы мәселе. Граф теориясында Ловас болжамы (1969) – графтардағы Гамильтондық жолдарға қатысты классикалық мәселе. Ол былай дейді: Кез келген шекті, байланысқан, төбелік транзитивті граф Гамильтондық жолды қамтиды. Бастапқыда Ласло Ловас мәселені кері бағытта қойған, бірақ осы нұсқасы стандартқа айналды. 1996 жылы Ласло Бабаи осы болжамға тікелей қайшы келетін болжам жариялады, бірақ екі болжам да әлі де ашық күйде қалып отыр. Тіпті бір ғана қарсы мысал бірнеше қарсы мысалдарға әкеледі ме, бұл да белгісіз.
In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says:
Every finite connected vertex transitive graph contains a Hamiltonian path. Originally László Lovász stated the problem in the opposite way, but
this version became standard. In 1996, László Babai published a conjecture sharply contradicting this conjecture, but both conjectures remain widely open. It is not even known if a single counterexample would necessarily lead to a series of counterexamples.
Тарихи ескертулер
Жоғары симметриялық графтардағы Гамильтондық жолдарды табу мәселесі өте ертеден келген. Дональд Кнуттың "Компьютерлік бағдарламалау өнері" кітабының 4-томында сипаттағандай, бұл мәселе британдық кампанологияда (қоңырау соғу) пайда болған. Мұндай Гамильтондық жолдар мен циклдар Грей кодтарымен де тығыз байланысты. Әрбір жағдайда құрылымдар нақты түрде берілген.
Бағытталған Кейли графигі
Бағытталған Кейли графиктері (диграфтар) үшін Ловас болжамы дұрыс емес. Роберт Александр Ранкин түрлі контрпримерлер келтірді. Дегенмен, төмендегі нәтижелердің көптегені осы шектеулі жағдайда да қолданылады.
Ерекше жағдайлар
Абельдік топтың әрбір бағытталған Кейли графигінің Гамильтондық жолы бар; алайда, реті біріншілік санның дәрежесі емес әрбір циклдік топтың Гамильтондық циклы жоқ бағытталған Кейли графигі бар. 1986 жылы Д. Витте Ловас болжамының p-топтарының Кейли графиктері үшін орындалатынын дәлелдеді. Бұл диэдрлік топтар үшін де әлі шешілмеген, бірақ генераторлардың белгілі бір жиындары үшін қандай да бір прогресс жасалды. Егер топ симметриялық топ болса, онда көптеген тартымды генерациялық жиынтықтар бар. Мысалы, Ловас болжамы генерациялық жиынтықтардың келесі жағдайларында орындалады: (ұзын цикл және транспозиция). (Коксетер генераторлары). Бұл жағдайда Гамильтондық цикл Штейнхаус–Джонсон–Троттер алгоритмі арқылы құрастырылады. Белгіленген ағашқа сәйкес келетін кез келген транспозициялар жиынтығы. Stong, m жұп немесе үш болған кезде Zm wr Zn гүл шоғырының Кейли графигі үшін болжамның орындалатынын көрсетті, бұл жағдайда табиғи минималды генерациялық жиынтық қолданылады. Атап айтқанда, бұл кубқа жалғасқан циклдар үшін де орындалады, оларды Z2 wr Zn гүл шоғырының Кейли графигі ретінде құруға болады.
(long cycle and a transposition). (Coxeter generators). In this case a Hamiltonian cycle is generated by the Steinhaus–Johnson–Trotter algorithm. any set of transpositions corresponding to a labelled tree on
Stong has shown that the conjecture holds for the Cayley graph of the wreath product Zm wr Zn with the natural minimal generating set when m is either even or three. In particular this holds for the cube connected cycles, which can be generated as the Cayley graph of the wreath product Z2 wr Zn.