Русская Википедия:Гипотеза Барнетта

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Unsolved Гипотеза Барнетта — нерешённый вопрос в теории графов о существовании гамильтоновых циклов в графах. Гипотеза названа именем Дэвида В. Барнетта, эмерита калифорнийского университета в Дейвисе. Гипотеза утверждает, что любой двудольный граф многогранника с тремя рёбрами в каждой вершине имеет гамильтонов цикл.

Определения

Планарный граф — это неориентированный граф, который может быть вложен в евклидово пространство без пересечений. Планарный граф называется полиэдральным (или графом многогранника) тогда и только тогда, когда он вершинно 3-связен, то есть, если не существует двух вершин, удаление которых разбивает граф на два (или более) графа. Граф называется двудольным, если его вершины можно раскрасить в два цвета таким образом, что каждое ребро соединяет вершины разных цветов. Граф называется кубическим (или 3-регулярным), если каждая вершина является концом в точности трёх рёбер. Наконец, граф гамильтонов, если существует цикл, проходящий через все вершины в точности один раз. Гипотеза Барнетта утверждает, что любой кубический двудольный граф многогранника гамильтонов.

По теореме Штайница планарный граф представляет рёбра и вершины выпуклого многогранника тогда и только тогда, когда он полиэдрален. Трёхмерный многогранник образует кубический граф тогда и только тогда, когда он является простым. Планарный граф является двудольным тогда и только тогда, когда в его планарном вложении все циклы граней (границы) имеют чётную длину. Таким образом, гипотеза Барнетта может быть сформулирована в эквивалентном виде. Представим, что трёхмерный простой выпуклый многогранник имеет чётное число рёбер в каждой грани. Тогда, согласно гипотезе, граф многогранника имеет гамильтонов цикл.

История

В 1884 году Тэйт высказал предположение, что любой кубический полиэдральный граф является гамильтоновым. Теперь эта гипотеза известна как гипотеза Тэйта. Гипотезу опроверг Татт в 1946Шаблон:Sfn, построив контрпример с 46 вершинами. Другие исследователи позднее нашли меньшие контрпримеры, однако ни один из этих контрпримеров не является двудольным. Сам Татт предположил, что любой кубический 3-связный двудольный граф гамильтонов, но был найден контрпример, граф ХортонаШаблон:SfnШаблон:Sfn. Дэвид В. Барнетт в 1969Шаблон:Sfn предложил ослабленную комбинацию гипотез Тэйта и Татта, утверждающую, что любой двудольный кубический полиэдральный граф гамильтонов, или, эквивалентно, что любой контрпример гипотезы Тэйта не является двудлольным.

Эквивалентые формы

КелмансШаблон:Sfn показал, что гипотеза Барнетта эквивалентна утверждению, что для любых двух рёбер e и f на одной и той же грани двудольного кубического многогранника существует гамильтонов цикл, который содержит e, но не содержит f. Ясно, что если утверждение верно, то любой двудольный кубический полиэдральный содержит гамильтонов цикл — просто выберем e или f. В другом направлении Келман показал, что конртпример этому утверждению можно преобразовать в контрпример оригинальной гипотезы Барнетта.

Гипотеза Барнетта эквивалентна также утверждению, что вершины двойственного графа для любого кубического двудольного полиэдрального графа можно разделить на два подмножества и порождённые графы на этих подмножествах являются деревьями. Сечение, порождённое таким разделением в двойственном графе, соответствует гамильтонову пути в исходном графеШаблон:Sfnp.

Частичные результаты

Хотя неизвестно, верна ли гипотеза Барнетта, вычислительные эксперименты показывают, что конрпримера с числом вершин меньше 86 нетШаблон:SfnШаблон:Sfn.

Если окажется, что гипотеза Барнетта неверна, то можно показать, что проверка, является ли двудольный кубический многогранник гамильтоновым, является NP-полной задачейШаблон:Sfn. Если планарный граф является двудольным и кубическим, но только 2-связным, то он может не быть гамильтоновым, и проверка, является ли граф гамильтоновым, является NP-полной задачейШаблон:Sfn.

Связанные задачи

Гипотеза, связанная с гипотезой Барнетте, утверждает, что любой кубический полиэдральный граф, в котором все грани имеют шесть и менее рёбер, является гамильтоновым. Вычислительные эксперименты показали, что если контрпример существует, он будет иметь более 177 вершинШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Гипотеза_Барнетта&oldid=9555074