@Возбуждающая

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

Добавлено через 5 часов 14 минут
((((((

0

Day

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

0

magirus

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

0

@Возбуждающая

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

вроде теорема о несвязности графа подходит...

Добавлено через 29 секунд
не могу до конца разобраться

0

Day

Планарный граф - это граф, который можно нарисовать на плоскости без пересечения ребер (без мостов и тонелей). У него есть свои любопытные свойства.

Напомните, плз, что такое "теорема о несвязности графа"

И еще вопрос - каждые 2 города соединяет не больше 1-й дороги ? Или их может быть несколько?

Мой контрпример, который я придумал, покуривая на балконе, оказался неверным.

0

@Возбуждающая

граф G(V,E) являются не связным , тогда и только тогда , когда множество его вершин V , можно разбить на два не пустых подмножества V1 и V2, так что бы любое ребро графа соединяла вершины из одного подмножества.

Добавлено через 4 минуты
из каждого города выходит 100 дорог...

0

@теркин

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

0

Day

Очень странно. Я такого условия достаточности не знал. Да и вряд ли оно верно. Легко построить контрпример. Простейший - 2 треугольника.

0

@теркин

На счет треугольника, поправка не достигнуть только в орт графе. По условию задачи 100 ребер из узла. Начертите 3 точки постройте 100 кратных ребер и попробуйте закрыть дорогу, движение встанет или нет как вы думаете?

Добавлено через 44 минуты
Это шутка. А если немного посерьезней достаточное условие достижимости -удаляемое ребро не должно являться единственной хордой. Если удаляется хорда граф G(V,E) разобьется на 2 не пересекающихся не пустых множества V1 и V2 а это означает что дороги из одного графа в другой нет. Если удаленное ребро хордой не является тогда одно из множеств V1 или V2 будет пустым а это значит вершины связаны.

0

Day

теркин, в решении должно использоваться число 100 (или м.б. любое четное). Возьмем 2 графа K101. Какие-то 2 вершины их соединим. Разрыв этого ребра приводит к несвязности графа. Правда, тут две вершины имеют степень 101, поэтому контрпримером это не является. Но и в твоих рассуждениях доказательства не видно.

Добавлено через 2 часа 49 минут
Все оказалось очень просто.
Очевидно, сумма индексов вершин в графе (неориентированном) четна.
Если после выбрасывания одного ребра граф распадается на два, то для них обоих четность нарушается
(индексы всех вершин =100, кроме одной с индексом 99)

2

@теркин

Поправка кроме двух вершин, ребро все таки инцидентно 2-м вершинам, удаляем ребро степень поменяется у двух вершин.(петли пока не рассматриваю).
А на счет доказательства - два изолированных графа соединены ребром. Степени этих вершин, до соединения, 99. Соединили ребром степень обеих вершин 100. Условие соблюдается. Теперь про хорды. По определению хорды -при удалении всех хорд в графе граф распадается на какое то количество подграфов. Для простоты доказательства по условиям задачи и применению вышеуказанной теоремы достаточно выполнения одного условия- при удалении ребра множество G(V,E) разбивается на 2 не пересекающихся подмножества. Для того чтобы это условие выполнилось -ребро должно быть хордой
подмножество G1(V,E)-соединено ребром с подмножеством G2(V,E) объединение множеств G1(V,E)UG2(V,E)=G(V,E). Операция объединения это добавление ребра. Степень вершин до объединения G2(V,E) 99 у G1(V,E) 99 объединили ребром степень вершин 100 все по условиям задачи. Так что решение если удаляемое ребро не хорда вершины достижимы. Остаются только цепи Эйлера, у которых начальные и конечные вершины совпадают(треугольник). Но тут есть маленькое но. При удаление любого ребра цепи G(V,E) на два подграфа разобьется так что G1(V,E) или G2(V,E) (как Вам больше нравится) окажется пустым. А это изначально противоречит условию о не пустоте множеств. Если хорд много. Тогда при удалении любой хорды граф распадаться не будет G1(V,E) или G2(V,E) окажутся пустыми. Вот и все доказательство. Надеюсь теперь все.

0

Байт

Краткость - сестра таланта! Даже если двоюродная.

1

@теркин

Четность говорите. Простой пример неориентированный граф 3 вершины треугольник 100 ребер из каждой вершины. Удалите ребро. Четная окажется степень или нечетная до любой вершины все равно дойдете.

0