2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Граф - простой цикл (задача)
Сообщение09.11.2006, 10:32 


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

 Профиль  
                  
 
 Re: Граф - простой цикл.
Сообщение10.11.2006, 12:59 


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

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

 Профиль  
                  
 
 
Сообщение10.11.2006, 20:05 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Thor.Myth писал(а):
То ли я не понял условие, то ли полный граф - контрпример. Там вообще нет несмежных вершин и он, безусловно, двусвязен.

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

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

2 lostoman:

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

 Профиль  
                  
 
 
Сообщение10.11.2006, 22:01 


05/07/06
9
незваный гость писал(а):
:evil:
Thor.Myth писал(а):
То ли я не понял условие, то ли полный граф - контрпример. Там вообще нет несмежных вершин и он, безусловно, двусвязен.

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

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

2 lostoman:

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

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

 Профиль  
                  
 
 
Сообщение10.11.2006, 22:12 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Thor.Myth писал(а):
По предложению - а почему кроме двух? Кроме всех, с которыми она была соединена...

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

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

 Профиль  
                  
 
 
Сообщение11.11.2006, 10:28 
Заслуженный участник


09/02/06
4382
Москва
незваный гость писал(а):
Полный граф не становится несвязным при удалении двух вершин.

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

 Профиль  
                  
 
 
Сообщение11.11.2006, 19:45 
Заслуженный участник
Аватара пользователя


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


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

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

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

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

 Профиль  
                  
 
 
Сообщение11.11.2006, 23:05 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
lostoman писал(а):
Дан двусвязный граф G, если из него удалить любые две несмедные вершины он становится несвязным, доказать что такой граф - простой цикл.

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

 Профиль  
                  
 
 
Сообщение11.11.2006, 23:09 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Артамонов Ю.Н. писал(а):
Но на самом деле условию будет удовлетворять и граф, состоящих из простых циклов, соединенных мостом.

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

 Профиль  
                  
 
 
Сообщение11.11.2006, 23:13 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение12.11.2006, 13:19 


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


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

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

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

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

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

 Профиль  
                  
 
 
Сообщение12.11.2006, 20:06 


05/07/06
9
Руст писал(а):
На самом деле даже наличие одной противоречит условию, так как в графе есть циклы, удаляя эту вершину и вершину из цикла мы не теряем связность.

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

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

 Профиль  
                  
 
 
Сообщение12.11.2006, 20:50 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Thor.Myth писал(а):
Во-первых, не знаю, где как, а у нас в определении двусвязности никакой минимальности не было.
Во-вторых, объсните мне, почему полный граф не удовлетворяет условию задачи? ИМХО, удовлетворяет.

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

 Профиль  
                  
 
 
Сообщение12.11.2006, 21:18 
Заслуженный участник


09/02/06
4382
Москва
Thor.Myth писал(а):
Руст писал(а):
На самом деле даже наличие одной противоречит условию, так как в графе есть циклы, удаляя эту вершину и вершину из цикла мы не теряем связность.

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

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

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

 Профиль  
                  
 
 
Сообщение13.11.2006, 11:05 


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


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group