2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Гамильтоновость кубического графа
Сообщение18.12.2016, 17:16 
Аватара пользователя
Известны ли какие-либо критерии гамильтоновости для кубического графа?

В частности, является ли следующий граф на 46 вершинах гамильтоновым?
Изображение

 
 
 
 Re: Гамильтоновость кубического графа
Сообщение18.12.2016, 18:10 
Что Вам мешает взять условие существования гамильтонова цикла и проверить?

 
 
 
 Re: Гамильтоновость кубического графа
Сообщение18.12.2016, 19:30 
Аватара пользователя
Alexander Evnin в сообщении #1178096 писал(а):
Известны ли какие-либо критерии гамильтоновости для кубического графа?

В WikipediA не смотрели?

 
 
 
 Re: Гамильтоновость кубического графа
Сообщение18.12.2016, 20:15 
Аватара пользователя
whitefox в сообщении #1178134 писал(а):
В WikipediA не смотрели?
А там как-то на удивление скромно с информацией. Нужно гуглить статьи, работ в этом направлении море (хотя результатов меньше). Из того, что мне недавно попадалось на глаза, известно:
    Если 3-связный плоский кубический граф не имеет более чем 6-сторонних граней, то он гамильтонов.
Это в какой-то статье про фуллерены было. К представленному графу критерий, понятно, не подходит.

-- 18.12.2016, 20:19 --

Вот здесь.

 
 
 
 Re: Гамильтоновость кубического графа
Сообщение18.12.2016, 21:06 
grizzly в сообщении #1178147 писал(а):
whitefox в сообщении #1178134 писал(а):
В WikipediA не смотрели?

А там как-то на удивление скромно с информацией.

Но там есть подсказка:
Цитата:
There has been much research on Hamiltonicity of cubic graphs. In 1880, P.G. Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example to Tait's conjecture, the 46-vertex Tutte graph, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian.

которая приводит к Grinberg's theorem.

 
 
 
 Re: Гамильтоновость кубического графа
Сообщение18.12.2016, 21:50 
Аватара пользователя
Да, оказалось, что всё дело в этой теореме. https://en.wikipedia.org/wiki/Grinberg%27s_theorem

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group