2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 задача из теории графов
Сообщение07.04.2009, 21:27 
Здравствуйте. Прошу помочь с идей решения задачи. Задача на графы.

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

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

 
 
 
 Re: задача из теории графов
Сообщение07.04.2009, 21:38 
Senobit писал(а):
Здравствуйте. Прошу помочь с идей решения задачи. Задача на графы.

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

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

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

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

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

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

 
 
 
 
Сообщение07.04.2009, 22:43 
Думаю имеется в виду, что граф планарный.

Влад.

 
 
 
 
Сообщение07.04.2009, 23:11 
Может это как- нибудь использовать:

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

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

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

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

 
 
 
 
Сообщение08.04.2009, 10:34 
ha писал(а):
В таком случае нужно найти вершину степени не больше 5 и закрыть все соседние с ней станции. Если это не все вершины графа - то получим искомое.

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

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

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

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

 
 
 
 
Сообщение08.04.2009, 14:11 
Аватара пользователя
Dementor в сообщении #203082 писал(а):
Задача сформулирована некорректно. Если мы взрываем станцию, то докачать до неё нефть не получиться ни при каких условиях.

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

 
 
 
 
Сообщение08.04.2009, 18:58 
PAV писал(а):
Dementor в сообщении #203082 писал(а):
Задача сформулирована некорректно. Если мы взрываем станцию, то докачать до неё нефть не получиться ни при каких условиях.

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

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

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

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


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

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

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

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

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

 
 
 
 
Сообщение08.04.2009, 20:31 
Хорхе писал(а):

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

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


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

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

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


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

$E\le3V-6$

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

 
 
 
 
Сообщение08.04.2009, 20:39 
Аватара пользователя
Senobit писал(а):
мы рассматриваем только 2- мерный случай.)

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

Вот он

Изображение

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group