задача из теории графов

[Senobit]

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

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

Заранее спасибо
мои идеи: скорее всего нада решать от противного.
Меня еще интересует- почему именно 5?
(еще можно рассмотреть частный случай, когда каждая станция связана с другой)

[VAL]

Senobit писал(а):

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

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

А что тут доказывать? Взрываем 2 станции (что заведомо не более 5). Вот между взорванными станциями и нельзя будет прокачать нефть.

[Senobit]

контр-пример: Берем полный граф из 10 вершин. Какие вершины не выкидывай, между остальными будет сколько хочешь связей.

[Prorab]

Вы что, хотите нас под статью об экстремизме-терроризме подвести? Другой формулировки не нашлось, что ли? Следующий вопрос будет про состав взрывчатки?!

[Senobit]

Prorab писал(а):

Вы что, хотите нас под статью об экстремизме-терроризме подвести? Другой формулировки не нашлось, что ли? Следующий вопрос будет про состав взрывчатки?!

Извините. Но формулировку не я придумал.
Тут нефть и диверсанты- не главное, задача на графы.

[vlad239]

Думаю имеется в виду, что граф планарный.

Влад.

[Senobit]

Может это как- нибудь использовать:

Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K5 или K3,3.

Критерий непланарности:
достаточное условие — если граф содержит двудольный подграф K3,3 или полный подграф K5, то он является не планарным;
необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин степень которых больше 3 или больше 5 вершин степени больше 2.

[ha]

В таком случае нужно найти вершину степени не больше 5 и закрыть все соседние с ней станции. Если это не все вершины графа - то получим искомое.

А вообще даже для планарных графов есть контрпримеры - полные графы из 1,2,3 и 4 станций.

[Senobit]

ha писал(а):

В таком случае нужно найти вершину степени не больше 5 и закрыть все соседние с ней станции. Если это не все вершины графа - то получим искомое.

А вообще даже для планарных графов есть контрпримеры - полные графы из 1,2,3 и 4 станций.

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

[Dementor]

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

P.S. Задача сформулирована некорректно. Если мы взрываем станцию, то докачать до неё нефть не получиться ни при каких условиях.

[PAV]

Dementor в сообщении #203082 писал(а):

Задача сформулирована некорректно. Если мы взрываем станцию, то докачать до неё нефть не получиться ни при каких условиях.

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

[Senobit]

PAV писал(а):

Dementor в сообщении #203082 писал(а):

Задача сформулирована некорректно. Если мы взрываем станцию, то докачать до неё нефть не получиться ни при каких условиях.

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

верно , именно так

Добавлено спустя 4 минуты 5 секунд:

Dementor писал(а):

В случае планарного графа с циклами: максимальный планарный граф 4-вершинно-связен.

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

[Хорхе]

В планарном графе на $n$ вершинах не более $3n-6$ ребер (это легко следует из формулы Эйлера). Тогда найдется вершина, из которой выходит меньше 6 ребер. qed.

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

Dementor писал(а):

максимальный планарный граф 4-вершинно-связен.

Неправда, граф икосаэдра 5-связен.

[Senobit]

Хорхе писал(а):

Dementor писал(а):

максимальный планарный граф 4-вершинно-связен.

Неправда, граф икосаэдра 5-связен.

мы рассматриваем только 2- мерный случай.)

Добавлено спустя 4 минуты 38 секунд:

Хорхе писал(а):

В планарном графе на $n$ вершинах не более $3n-6$ ребер (это легко следует из формулы Эйлера). Тогда найдется вершина, из которой выходит меньше 6 ребер.

вот я нашел подобное : для плоского графа

$E\le3V-6$

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

[Хорхе]

Senobit писал(а):

мы рассматриваем только 2- мерный случай.)

Граф икосаэдра планарный.

Вот он