Задача на графы

romero111

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

Lokomotiv59

Вопрос номер один: граф ориентированный ?

Lokomotiv59

Вопрос номер два: циклы имеются ввиду простые ?

romero111

Граф обычный, циклы без самопересечений

Lokomotiv59

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

romero111

Пусть компонента одна.
Почему при разных наборах удаляемых ребер не могут получиться существенно различные деревья разной длины?

Lokomotiv59

Могут конечно =)
Только есть такое свойство --- дерево из n вершин имеет n-1 ребро

romero111

Хм... А вот это уже хорошее свойство!

seregaohota

Для графов есть инвариант - можно сказать обобщение теоремы Эйлера для обычных многогранников в R^3.
V-E+C-K=0
V число вершин, E - рёбер, C - независимых циклов, K - компонент связности. Доказать можно по индукции строя граф с пустого.
Для многогранника в R^3 будет C=Г-1, K=1, Г - число граней, откуда
V-E+Г=2
Кстати ещё следствие: для дерева при отсутствии циклов и компонента связности одна
V-E=1

iri3955

Как-то заумно... Сказали ведь уже в дереве n-1 вершина.
Поскольку при разрезании граф не т еряет свзяности, то отстанется связный граф без циклов - n-1 вершина

topboy84

это только для плоских графов такое свойство

seregaohota


Как-то заумно...
Ну если мы умеем ходить пешком не значит, что умение передвигаться ещё десятком способов как более общий факт не имеет никакой ценности. Ведь я же не для деревьев доказывал, это только пример был, как частный случай. А то это анекдот напоминает.
1. Дано. Электрочайник. Вода. Задача вскипятить чайник.
Физик: Наливаем воду в чайник, включаем. Ждём.
Математик:Так же.
2. Дано. Вода во включённом электрочайнике. Задача вскипятить чайник.
Физик: Ждём.
Математик: Выключаем чайник, выливаем воду и задача сводится к предыдущей.

это только для плоских графов такое свойство
Почему? Тогда в этой ветке неверен был бы ответ на вопрос, которым началась тема.
Для примера 2 непланарных графа - любой непланарный граф содержит как подмножество либо G_5 - звезду, вписанную в пятиугольник, либо G_{3,3} - три вершины "вверху", три "внизу", и каждая верхняя соединена с каждой нижней.
Так для
G_5: V=5, E=10, C=6, K=1
G_{3,3}: V=6, E=9, C=4, K=1
V-E+C-K=0 для обоих.
Дело в том, что для пустого графа это выполнено. Добавляя к произвольному графу новую (изолированную естественно)вершину v - мы получаем и ещё одну компоненту связности.
А добавляя ребро e, мы либо соединяем 2 компоненты, и тогда цикл не появляется, т.к. из одной компоненты в другую нельзя было пройти до того, минуя только-что добавленное ребро e. Либо это новое ребро e соединяет вершины из одной старой компоненты, и тогда минуя это новое ребро e можно было пройти из одного его конца в другой, а добавив это ребро e замкнём цикл, который независим от предыдущих, т.к. ребро e в предыдущих циклах не встречалось. Инвариант вобщем.
Только петлю на себя из вершины в саму себя надо считать циклом из одного ребра. В обычных графах таких рёбер правда не бывает.
На эту фишку я наткнулся пытаясь доказать, что уравнения Кирхгофа разрешимы для любой сети. Вроде эта штука мне потом у Оре в книжке теории графов попалась.

Lokomotiv59

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

topboy84

дерево - планарный граф, и для него т. Эйлера верна.
возьми для примера граф, состоящий из 2 вершин и 5 ребер.
у него 1 компонента связности, 2 вершины 5 ребер и 10 циклов.
10 + 2 != 5 + 1

seregaohota

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

seregaohota

дерево - планарный граф, и для него т. Эйлера верна.
возьми для примера граф, состоящий из 2 вершин и 5 ребер.
у него 1 компонента связности, 2 вершины 5 ребер и 10 циклов.
10 + 2 != 5 + 1
Дело в том, что 10 это зависмые циклы. Независимых или как они там называются, через которые можно выразить остальные линейной комбинацией - 4.
а 4+2=5+1
Берёшь цикл - выкидываешь из него ребро. Дальше ищешь циклы в оставшемся подграфе. 4 получится, техника как в топикстарте написано. Так что ошибки нет, ты непрравильно циклы считаешь.

Lokomotiv59

По содержанию претензии высказал
А я к тому, что это собственно пушкой в любом случае назвать нельзя. Просто была конкретная задачка --- было дано конкретное решение. Когда будет другая задача --- будем дальше думать. А это свойство про инварианты выглядит немного "надуманным"

Lokomotiv59

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

topboy84

понял, был неправ

seregaohota

круто, тогда надо доказать независимость от выбора ребра, что эквивалентно задаче топикстартера
Естественно. Вы именно это и доказываете в случае обычных графов (не мультиграфов, без параллельных рёбер и петель на себя) и вроде по контексту для одной компоненты связности. Переход на общий случай не сильно усложняет жизнь.
У меня просто более красивая и более чёткая IMHO переформулировка результата с кивками в сторону теоремы Эйлера и свойств деревьев как частные случаи, но принципиально ничего нового.
А вообще по идеологии возражения "нафига решать задачу, пока её реально нет" - подход IMHO неверный. Математика как раз затачивается на решение классов задач, и чем более мы широкий класс без лишнего напряга охватили - тем лучше. Если только не пытаемся объять необъятное. "Математика - искусство разным вещам давать одинаковое название,"- Пуанкаре.
Впрочем, такой же подход и в физике, ...., и в технике, и в жизни вообще. Упрощает жизнь, если не сильно разбрасываешься.

Lokomotiv59

Тогда бы уж лучше на сети обобщали или ориентированные графы (хотя там ничо хорошего сказать скорее всего нельзя) В данном случае действительно смысла не имело, так как формулировка определений раза в 2 больше самого решения.
Оставить комментарий
Имя или ник:
Комментарий: