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

[lostoman]

Есть задача: Дан двусвязный граф G, если из него удалить любые две несмедные вершины он становится несвязным, доказать что такой граф - простой цикл.
Я пытался доказать от противного, т.е. предполагать что граф не является проствм циклом, и пытался найти способ выбрать 2 вершины шрафа таким оьразом, чтобы граф остался связным. Но для любого графа такого способа никак найти не могу. Была идея что выбрать два простых уиклах в графе G(если он не простой цикл то это можно сделать) и на каждом цикле удалить две веишны лежащие только на этих циклах и эти ыершины не должны лежать на одной цепи вне этих циклах(т.е на цепи которая не проходит через наши циклы), но существуют графы, которые по этому правилу мы все равно получим несвязный граф.
Может у вас есть какие-нибудь идеи?

[Thor.Myth]

lostoman писал(а):

Есть задача: Дан двусвязный граф G, если из него удалить любые две несмедные вершины он становится несвязным, доказать что такой граф - простой цикл.
Я пытался доказать от противного, т.е. предполагать что граф не является проствм циклом, и пытался найти способ выбрать 2 вершины шрафа таким оьразом, чтобы граф остался связным. Но для любого графа такого способа никак найти не могу. Была идея что выбрать два простых уиклах в графе G(если он не простой цикл то это можно сделать) и на каждом цикле удалить две веишны лежащие только на этих циклах и эти ыершины не должны лежать на одной цепи вне этих циклах(т.е на цепи которая не проходит через наши циклы), но существуют графы, которые по этому правилу мы все равно получим несвязный граф.
Может у вас есть какие-нибудь идеи?

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

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

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

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

Полный граф не становится несвязным при удалении двух вершин.

Добавлено спустя 25 минут 51 секунду:

2 lostoman:

Попробуйте удалить одну вершину, и рассмотреть получившийся граф. Мне кажется, что свойство «терять связность при удалении любой вершины, кроме двух» ведет к линейному графу. (Это верно, если не разрешены множественные соединенния между двумя вершинами, и соединение вершины с самой собой. Но в этих условиях и утверждение задачи неверно.)

[Thor.Myth]

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

:evil:

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

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

Полный граф не становится несвязным при удалении двух вершин.

Добавлено спустя 25 минут 51 секунду:

2 lostoman:

Попробуйте удалить одну вершину, и рассмотреть получившийся граф. Мне кажется, что свойство «терять связность при удалении любой вершины, кроме двух» ведет к линейному графу. (Это верно, если не разрешены множественные соединенния между двумя вершинами, и соединение вершины с самой собой. Но в этих условиях и утверждение задачи неверно.)

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

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

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

По предложению - а почему кроме двух? Кроме всех, с которыми она была соединена...

Удалив одну вершину, я рассматриваю оставшийся граф и изучаю его структуру. В этом случае, у меня нет выделенных вершин — «с которыми она была соединена». Просто граф, при удалении некоторых вершин перестающий быть связным.

Я подозреваю, что полный граф при $n > 3$ не является двусвязным. Но это — мои подозрения. Бог с ними…

[Руст]

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

Полный граф не становится несвязным при удалении двух вершин.

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

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

lostoman писал(а):

(самые первые строчки темы): Есть задача: Дан двусвязный граф G, если из него удалить любые две несмежные вершины он становится несвязным, доказать что такой граф - простой цикл. (курсив мой — нг)

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

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

В нашей школе бытовал фольклор (с автором, разумеется): «Прежде чем решать задачу, полезно ознакомиться с ее условием.»

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

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

А вот это — очень верное замечание. Я, почему-то, всегда считаю граф конечным. Позор моим лысинам!

[juna]

lostoman писал(а):

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

Чего-то я не пойму, что понимается под двусвязностью. Вот есть понятие вершинной или реберной $k$ связности - как минимального количества ($k$ штук) вершин (ребер), при удалении которых граф распадается на компоненты связности. Здесь видимо речь о вершинной связности. Для того, чтобы полный граф ($n$ вершин) стал несвязным, необходимо удалить $n-1$ вершин, т.к. в нем любые вершины смежные - поэтому он вообще не удовлетворяет условию: "удалить любые две несмежные вершины он становится несвязным". Ясно, что простой цикл из $n>3$ вершин всегда удовлетворяет условию ( в нем $n$ вершин и $n$ ребер). Нужно показать, что нет другого, отличного от простого цикла. Тогда необходимо показать, что для удовлетворения условию задачи необходимо, чтобы каждой вершине были инцидентны только два ребра. Но на самом деле условию будет удовлетворять и граф, состоящих из простых циклов, соединенных мостом.

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

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

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

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

[juna]

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

[Thor.Myth]

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

:evil:

lostoman писал(а):

(самые первые строчки темы): Есть задача: Дан двусвязный граф G, если из него удалить любые две несмежные вершины он становится несвязным, доказать что такой граф - простой цикл. (курсив мой — нг)

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

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

В нашей школе бытовал фольклор (с автором, разумеется): «Прежде чем решать задачу, полезно ознакомиться с ее условием.»

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

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

А вот это — очень верное замечание. Я, почему-то, всегда считаю граф конечным. Позор моим лысинам!

Во-первых, не знаю, где как, а у нас в определении двусвязности никакой минимальности не было.
Во-вторых, объсните мне, почему полный граф не удовлетворяет условию задачи? ИМХО, удовлетворяет.
Да, полный граф не становится несвязным при удалении двух вершин, но двух несмежных-то у него вообще нет. Поэтому условие, которое должно удовлетворяться пустое.

[Thor.Myth]

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

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

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

Теорема Менгера, ИМХО, факт слишком сложный, чтобы применять его в этой задаче

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

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

Во-первых, не знаю, где как, а у нас в определении двусвязности никакой минимальности не было.
Во-вторых, объсните мне, почему полный граф не удовлетворяет условию задачи? ИМХО, удовлетворяет.

А какое определение двусвязности у Вас было? Напечатайте, пожалуйста, и мы применим его к полному графу.

[Руст]

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

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

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

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

Теорема Менгера, ИМХО, факт слишком сложный, чтобы применять его в этой задаче

Если удалите эту вершину (куда приходит единственное ребро, соответственно не лежащую в цикле) и любую несмедную вершину из цикла связность не теряется, так как при удалении одной вершины из цикла связьность не теряется.
Я так же не понял, что подразумевается под двусвязностью, и поэтому предлагал решение без этого. Подозреваю, что полный граф n-1 связен, соответственно условию удовлетворяет только случай n=3, когда полный граф станет обычным циклом.
Что касается бесконечных графов, они рассматриваются в бесконечномерных представлениях. Контпримеров для бесконечного графа много. При этом все контрпримеры или деревья с бесконечно продолжаемыми листьями. Можно даже приделать один цикл, т.е. деревья начинают расти с одного цикла. Я привёл пример, когда с каждой вершины исходит ровно две вершины.

[Thor.Myth]

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

Цитата:

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

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