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

[Руст]

Thor.Myth писал(а):

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

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

[Macavity]

Thor.Myth писал(а):

"Двусвязный граф - граф при удалении любой вершины остающийся связным."
Полный удовлетворяет этому свойству. Возможно, есть и другие определения двусвязности.

Другое определение -
Каждая вершина графа принадлежит какому-либо простому циклу.

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

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

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

[незваный гость]

Thor.Myth писал(а):

"Двусвязный граф - граф при удалении любой вершины остающийся связным."

Мне как-то больше по душе точка зрения Руста:

Руст писал(а):

Подозреваю, что полный граф n-1 связен

Хотя бы потому, что как-то нелогично — односвязный строго один, а двучсвязный — больше либо равно два.

[Someone]

Ф.Харари. Теория графов. "Мир", Москва, 1973.

Связностью $\varkappa=\varkappa(G)$ графа $G$ называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.

Тривиальный граф - это граф, содержащий только одну вершину (и не содержащий ни одного ребра).

[незваный гость]

Спасибо, Someone.

[lostoman]

Под двусвязностью графа здесь понимакется:
Граф G называется двусвязным если в нем существуют две вершинв при удалении которых он становиться несвязным. При удалении любой одной вершины он остается связным.
Очевидны следующие свойства:
1) Минимальная степень вершины графа > 1.
2)Через любые две вершины графа проходит простой цикл.
To Macavity
Я тоже сначала так решалю Но если мы возьмем в качетве графа квадрат с одной диагональю, и соеденим вершины , неинцидентные диагоналям простой цепью, то по такому методу у нас получиться несвязный граф. Здесь надо выбрать как-то еще два простых цикла, не произвольно, мне кажется.

[Macavity]

lostoman писал(а):

Под двусвязностью графа здесь понимакется:
Граф G называется двусвязным если в нем существуют две вершинв при удалении которых он становиться несвязным. При удалении любой одной вершины он остается связным.

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

Очевидны следующие свойства:
1) Минимальная степень вершины графа > 1.
2)Через любые две вершины графа проходит простой цикл.

Это понятно,
если бы можно было доказвать, что существует Гамильтонов цикл, то доказывать уже было бы нечего...

lostoman писал(а):

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

Не знаю, надо ещё подумать.

[lostoman]

Цитата:

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

Да правильно. Может немного неточно выразился. Лучше сказать, что существует хотя бы 2 вершины, при удалении которых граф становится несвязным. Такими вершинами могут быть и все несмежные вершины.

[незваный гость]

Macavity писал(а):

lostoman писал(а):

Под двусвязностью графа здесь понимакется:
Граф G называется двусвязным если в нем существуют две вершинв при удалении которых он становиться несвязным. При удалении любой одной вершины он остается связным.

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

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

[Macavity]

незваный гость писал(а):

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

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

[Macavity]

Вот моё доказательство.
Если кто найдет ошибку или какие-то неясности, то пожалуйста прокомментируйте. Тем более, что доказательство получилось немаленькое, так что там может быть всяко-разно.

Доказательство проведем в три этапа.

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

Этап 2. Существование Гамильтонова цикла.
Утверждается, что в графе G обязательно существует Гамильтонов цикл (простой цикл, проходящий через все вершины). Докажем это. Доказательство проведем конструктивно, то есть построим алгоритм находящий Гамильтонову цепь (простая цепь через все вершины), а потом преобразуем её в цикл.

Обозначим за A_k=(a_1,a_2,…, a_k) цепь, которая образуется на некотором цикле алгоритма и состоящая из k вершин (в порядке, как они представлены в записи). G^k – это множество вершин, которые еще не принадлежат цепи на том же цикле. На каждом цикле последняя вершина a_k будет считаться текущей вершиной для присоединения новых вершин или простых цепей.


Алгоритм
1. Выбираем произвольную вершину и помещаем её в A_1 и соответственно получаем множество G^1 (уже без этой вершины). a_1 – текущая вершина. K=1
2. Выбираем из G^k произвольную вершину X. Рассматриваем две вершины a_1 и X.
Если они смежные, то добавляем вершину X в цепь и делаем её текущей (соответственно меняем k и удаляем из G^{k+1} вершину X). Если же вершины несмежные, то удалив их из исходного графа получим несколько компонент связности, причем в одной из компонент связности будут находится все вершины цепи A_k, за исключением вершины a_k, которая удаляется из графа. Исходя из этапа 1 существует простая цепь, находящаяся полностью в другой компоненте связности и соединяющая a_k и X. Раз эта цепь находится в другой компоненте связности, то она не имеет пересечений с цепью A_k, и может продлить цепь A_k до вершины X (Здесь надо добавить цепь в конец A_k и удалить вершины цепи из G^k, увеличить k на длину пристыкованной цепи). То есть после шага 2 длина простой цепи увеличиться.
3. Если в множестве G_k, остались вершины, то переходим к шагу 2, иначе получена простая (Гамильтонова) цепь из всех вершин графа G.

Алгоритм всегда завершается построением Гамильтоновой цепи, так как на каждом цикле цепь увеличивается. Ну и поскольку любая оставшаяся вершина графа может быть или смежной с a_k или несмежной, то все они рано или поздно за конечное количество циклов (не более количества вершин n в исходном графе) будут подключены к цепи.

Примечание. Ради интереса можно посмотреть, что произойдет, когда в графе останется только одна неподключенная к цепи вершина. На самом деле, эта вершина может быть только смежной к вершине a_{n-1} поскольку вся остальная цепь оказывается в одной компоненте связности (второй компоненты нет, и граф остается связным) после удаления a_{n-1} и этой последней вершины из графа. То есть, эта вершина подключается как смежная к a_{n-1}.

Последний вопрос на этом этапе это превращения Гамильтоновой цепи в Гамильтонов цикл. Из тех же соображений, что указаны в примечании, оказывается, что вершины a_1 и a_n смежные и могут быть соединены ребром. Таким образом, Гамильтонов цикл построен.

Этап 3. Единственность цикла.
То, что существует Гамильтонов цикл ещё не значит, что это единственный цикл в исходном графе G. Предположим, что Гамильтонов цикл построен. По определению он простой и проходит через все вершины. Если в графе G нет других ребер, кроме принадлежащих Гамильтонову циклу, то единственность автоматически доказана. Предположим, что есть еще какие то ребра не входящие в Гамильтонов цикл. Любое из таких ребер соединяет две вершины Гамильтонова цикла (причем эти вершины не являются смежными в Гамильтоновом цикле, иначе это бы означало, что две вершины может соединять несколько ребер). Возьмем такое ребро z, этим ребром цикл разделится на две части B_1 и B_2. В каждой из частей обязательно есть вершина(X_1 в B_1 и X_2 в B_2), не принадлежащая добавленному ребру z. Если удалить эти две вершины (X_1 и X_2) из графа, то граф останется связным в силу существования дополнительного ребра z между вершинами Гамильтонова цикла. Это не соответствует исходным условиям, наложенным на граф G и это означает, что в графе G не существует никаких других рёбер, кроме принадлежащих Гамильтонову циклу.
Что и доказывает единственность данного цикла (Гамильтонова) в графе.

[juna]

В доказательство не вчитывался, но отмечу следующие моменты:
1) в простом цикле $2n$ гамильтоновых циклов, где $n$ - количество вершин, в общем графе если из вершины есть гамильтонов цикл, то их два - туда и обратно
2) найдите здесь больше 12 гамильтоновых циклов

[Macavity]

Возможно там есть темные места... Но я проверил, мое мнение - доказательство верное.

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

В доказательство не вчитывался, но отмечу следующие моменты:
1) в простом цикле $2n$ гамильтоновых циклов, где $n$ - количество вершин, в общем графе если из вершины есть гамильтонов цикл, то их два - туда и обратно

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

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

2) найдите здесь больше 12 гамильтоновых циклов

Честно говоря, вообще не понял к чему это.

[juna]

Macavity писал(а):

Этап 3. Единственность цикла.
То, что существует Гамильтонов цикл ещё не значит, что это единственный цикл в исходном графе . Предположим, что Гамильтонов цикл построен. По определению он простой и проходит через все вершины. Если в графе нет других ребер, кроме принадлежащих Гамильтонову циклу, то единственность автоматически доказана. Предположим, что есть еще какие то ребра не входящие в Гамильтонов цикл. Любое из таких ребер соединяет две вершины Гамильтонова цикла (причем эти вершины не являются смежными в Гамильтоновом цикле, иначе это бы означало, что две вершины может соединять несколько ребер). Возьмем такое ребро , этим ребром цикл разделится на две части и . В каждой из частей обязательно есть вершина( в и в ), не принадлежащая добавленному ребру . Если удалить эти две вершины ( и ) из графа, то граф останется связным в силу существования дополнительного ребра между вершинами Гамильтонова цикла. Это не соответствует исходным условиям, наложенным на граф и это означает, что в графе не существует никаких других рёбер, кроме принадлежащих Гамильтонову циклу.
Что и доказывает единственность данного цикла (Гамильтонова) в графе.

А что Вы понимаете под единственностью цикла - если есть хоть один, то есть два.

[Macavity]

Какие-то странные сообщения Вы пишете. Складывается впечатления, что Вы изрядно подзабыли теорию графов, причем начиная с терминологии:

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

1) в простом цикле $2n$ гамильтоновых циклов, где $n$ - количество вершин, в общем графе если из вершины есть гамильтонов цикл, то их два - туда и обратно

Нет никаких общих графов. То, что Вы называете общим графом, на самом деле называется неориентированным графом. А так ни общих, ни необщих графов не существует.

По поводу количества Гамильтоновых циклов - это тоже ерунда. Простой цикл может быть либо Гамильтоновым, либо негамильтоновым, а не 2*n Гамильтоновых. Заглянем в матчасть?
О.Оре. Теория графов:

Цитата:

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

Все очень просто и конкретно. Простой цикл (один простой) называется Гамильтоновым (одним Гамильтоновым) и т.д.

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

А что Вы понимаете под единственностью цикла - если есть хоть один, то есть два.

Еще лучше.
Поскольку в задаче рассматривается неориентированный граф, то и циклы в нем рассматриваются неориентированные. Смотрите Оре, Харари и т.д. и т.п.

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