Граф - простой цикл (задача)

[juna]

Я Вас не экзаменую, лишь просил уточнить словесную некорректность в доказательстве.
Гамильтонов цикл - это такой простой цикл и т.д. Ясно, что если Вы доказали, что в графе, удовлетворяющем условию задачи есть гамильтонов цикл, это можно использовать. А дальше вы говорите о его единственности - как цикла. Нет там никакой единственности, Вы правильно доказываете, что для удовлетворения условиям в нашем графе нет ребер, не принадлежащих данному гамильтонову циклу, но это не значит, что он единственный. Ну возьмите квадрат с вершинами abcd, есть циклы abcda,bcdab ... - по Вашему это один гамильтонов цикл.
Мои высказывания касались косметических улучшений и никак не противоречат общепринятым определениям.

[Macavity]

Артамонов Ю.Н. писал(а):

Гамильтонов цикл - это такой простой цикл и т.д. Ясно, что если Вы доказали, что в графе, удовлетворяющем условию задачи есть гамильтонов цикл, это можно использовать. А дальше вы говорите о его единственности - как цикла.

Мне просто непонятно, почему в словосочетании "простой цикл" у Вас слово цикл имеет другой смысл чем в словосочетании "Гамильтонов цикл".
Мне всегда казалось и вроде так и у Оре, что смысл слова "цикл" здесь один и тот же.

Артамонов Ю.Н. писал(а):

Нет там никакой единственности, Вы правильно доказываете, что для удовлетворения условиям в нашем графе нет ребер, не принадлежащих данному гамильтонову циклу, но это не значит, что он единственный.

Я считаю, что Гамильтонов цикл единственный. А вот пути или маршруты (замкнутые или незамкнутые там могут быть разные). И рассматриваю единственность цикла, так и стоит в условии задачи.

Артамонов Ю.Н. писал(а):

Ну возьмите квадрат с вершинами abcd, есть циклы abcda,bcdab ... - по Вашему это один гамильтонов цикл.
Мои высказывания касались косметических улучшений и никак не противоречат общепринятым определениям.

А разве по определению Оре это разные циклы? Хотя может есть источники, где это не так, мне это неизвестно. А может в пакете Математика другой смысл, опять не знаю, с ним пока не работал.

[juna]

Macavity писал(а):

Мне просто непонятно, почему в словосочетании "простой цикл" у Вас слово цикл имеет другой смысл чем в словосочетании "Гамильтонов цикл".
Мне всегда казалось и вроде так и у Оре, что смысл слова "цикл" здесь один и тот же.

Определимся:
цепь - машрут из разных ребер;
простая цепь - цепь, все вершины которой различны, кроме возможно первой и последней;
циклический маршрут - маршрут, у которого совпадает начало и конец;
цикл - циклическая цепь;
простой цикл - циклическая простая цепь;
гамильтонов цикл - простой цикл, содержащий каждую вершину графа.
Если граф не содержит кратных ребер, то маршрут можно указать перечислением вершин в порядке их прохождения. В этом смысле указанные циклы (являющиеся гамильтоновыми) abcda,bcdab - разные.
Нигде в этих определениях я сам себе не противоречил (разве что вот здесь неудачно выразился - в простом цикле $2n$ гамильтоновых циклов - имелось в виду в контексте к нашей задаче где простой цикл - гамильтонов). Да бог с ними, не в этом дело. По пункту 3 кроме указанного замечания - все верно. По остальному, внимательно не смотрел пока.
Да и в целом по теме, вроде теорема Менгера на все эти вопросы успешно отвечает, зачем изобретать велосипед.
Добавлено

Macavity писал(а):

Этап 1. Простые цепи в различных компонентах связности.
Возьмем граф с исходными условиями (граф G) и выберем две произвольные несмежные вершины X и Y. Если их удалить граф распадется на две компоненты и . Каждая из вершин X и Y имеет в первоначальном графе ребра как к так и к . Если бы одна из вершин не имела связи с одной из компонент, то достаточно было бы удалить только вторую вершину и получить несвязные между собой компоненты (а это нарушает условие). А так как обе компоненты связные, то это значит, что существует путь в исходном графе из X в Y, состоящий из ребра от X к какой-то вершине компоненты , дальше по вершинам только этой компоненты и в конце от до Y (в силу связности ). Тоже самое для X, и Y.
На самом деле таких путей по каждой компоненте может быть несколько, но один в силу вышесказанного для каждой компоненты существует. Заметим, что хотя найденные пути могут оказаться не простыми, но их всегда можно сделать простыми, отбрасывая ненужные циклы.
Кстати, если бы по каким-либо причинам G раскололся на три и более компонент. То такой путь существовал бы для каждой (в силу двусвязности).

В условии задачи не требуется, чтобы при удалении двух несмежных вершин граф распадался именно на две компоненты связности - требуется, чтобы он стал несвязным.

[Macavity]

Артамонов Ю.Н. писал(а):

Определимся:
цепь - машрут из разных ребер;
...
гамильтонов цикл - простой цикл, содержащий каждую вершину графа.
Если граф не содержит кратных ребер, то маршрут можно указать перечислением вершин в порядке их прохождения. В этом смысле указанные циклы (являющиеся гамильтоновыми) abcda,bcdab - разные.
Нигде в этих определениях я сам себе не противоречил (разве что вот здесь неудачно выразился - в простом цикле $2n$ гамильтоновых циклов - имелось в виду в контексте к нашей задаче где простой цикл - гамильтонов). Да бог с ними, не в этом дело.

Ага. Тем более, что это не имело никакого отношения к доказательству.

Артамонов Ю.Н. писал(а):

По пункту 3 кроме указанного замечания - все верно. По остальному, внимательно не смотрел пока.
Да и в целом по теме, вроде теорема Менгера на все эти вопросы успешно отвечает, зачем изобретать велосипед.

А можно и наоборот сказать, что использовать теорему Менгера в данном случае - это бить из пушки по воробъям.

Артамонов Ю.Н. писал(а):

Macavity писал(а):

Этап 1. Простые цепи в различных компонентах связности.
Возьмем граф с исходными условиями (граф G) и выберем две произвольные несмежные вершины X и Y. Если их удалить граф распадется на две компоненты и . Каждая из вершин X и Y имеет в первоначальном графе ребра как к так и к . Если бы одна из вершин не имела связи с одной из компонент, то достаточно было бы удалить только вторую вершину и получить несвязные между собой компоненты (а это нарушает условие). А так как обе компоненты связные, то это значит, что существует путь в исходном графе из X в Y, состоящий из ребра от X к какой-то вершине компоненты , дальше по вершинам только этой компоненты и в конце от до Y (в силу связности ). Тоже самое для X, и Y.
На самом деле таких путей по каждой компоненте может быть несколько, но один в силу вышесказанного для каждой компоненты существует. Заметим, что хотя найденные пути могут оказаться не простыми, но их всегда можно сделать простыми, отбрасывая ненужные циклы.
Кстати, если бы по каким-либо причинам G раскололся на три и более компонент. То такой путь существовал бы для каждой (в силу двусвязности).

В условии задачи не требуется, чтобы при удалении двух несмежных вершин граф распадался именно на две компоненты связности - требуется, чтобы он стал несвязным.

Можно подумать, что в моем цитированном Вами отрывке написано что-то другое.