Все выпуски  

RusFAQ.ru: Математика


Информационный Канал Subscribe.Ru

РАССЫЛКИ ПОРТАЛА RUSFAQ.RU

/ НАУКА И ОБРАЗОВАНИЕ / Точные науки / Математика

Выпуск № 38
от 01.09.2005, 13:35

Администратор:Tigran K. Kalaidjian
В рассылке:Подписчиков: 60, Экспертов: 14
В номере:Вопросов: 1, Ответов: 2


Вопрос № 25395: Вопрос: Не могли бы вы дать мне рисунок к следующему определению: Определение. Графом K3,3 называется граф с 6 вершинами a1, a2, a3, b1, b2, b3, в котором каждая вершина ai соединена ребром с каждой вершиной bj и нет других ребер. С...

Вопрос № 25.395
Вопрос:

Не могли бы вы дать мне рисунок к следующему определению:
Определение. Графом K3,3 называется граф с 6 вершинами a1, a2, a3, b1, b2, b3, в котором каждая вершина ai соединена ребром с каждой вершиной bj и нет других ребер.
С графом K3,3 связана следующая известная задача о трех домах и трех колодцах. Есть 3 дома и 3 колодца, но хозяева домов в большой вражде. Можно ли так проложить дорожки от каждого дома к каждому колодцу, чтобы они нигде не пересекались?
Отправлен: 27.08.2005, 13:32
Вопрос задал: Терсков Алексей Николаевич (статус: Посетитель)
Всего ответов: 2
Мини-форум вопроса >>> (сообщений: 0)

Отвечает: Бадер Алексей
Здравствуйте, Терсков Алексей Николаевич!

http://www.exponenta.ru/educat/systemat/zolotareva/graf/%D0%BB%D0%B0%D0%B1151.html

см. рис. 3.
Ответ отправил: Бадер Алексей (статус: 1-ый класс)
Отправлен: 27.08.2005, 14:49
Оценка за ответ: 5
Комментарий оценки:
Senk!

Отвечает: mvp
Здравствуйте, Терсков Алексей Николаевич!
Рисунок дать не могу, т. к. вы не оставили e-mail. Но не думаю, что он у Вас вызовет затруднение. Рисуете шесть точек и обозначаете a1, a2, a3, b1, b2, b3. Соединяете вершину a1 со всеми вершинами b1, b2, b3, потом a2 со всеми вершинами b1, b2, b3, и наконец a3 тоже самое. Вот Вам и граф К3,3. Рёбра рисуете как хотите, т.е. хотите дугами, хотите отрезками. Замечу, что в своё время я изрисовал тетрадь в 48 листов, пытаясь нарисовать этот граф, без пересечения рёбер - не получилось. А мог бы и не рисовать, если бы знал следующее:

Планарный граф - если его можно расположить на плоскости так, чтобы рёбра не пересекались. (если речь идёт о трехмерном пространстве, то всегда можно расположить рёбра так, чтобы они не пересекались).
Необходимое условие планарности. Для того, чтобы граф G был планарным, необходимо чтобы выполнялось неравенство: |E|(C - 2) <= C(|V| - Kg - 1) , где С – длина кратного цикла, |E|, |V| - мощности множества рёбер и вершин соответственно, а Kg - число компонент связности, т. е. количество непересекающихся множеств вершин, на которые можно разбить граф так, чтобы не существовало рёбер соединящих любую вершину из одного множества с любой другой вершиной из других множеств, но между любыми двумя вершинами каждого множества существует маршрут, соединяющий эти две вершины (висячая вершина (из которой не в(ы)ходит ни одного ребра) тоже является компонентой связности).

Теперь посмотрим на К3,3. |E| = 9, C = 4, |V| = 6, K = 1 => 9 * (4 - 2) <= 4 * (6 - 1 - 1) - не выполняется, т. к. 18 > 16, т. о. граф К3,3 не планарный и следовательно нельзя разместить дорожки так, чтобы они не пересекались.

Исходя из этого была доказана следующая теорема:

Критерий планарности.
Граф не плоский тогда и только тогда, когда некоторый его подграф гомеоморфен К3,3 или К5,5 .
Опр. Графы G и H наз. гомеоморфными, если существуют такие последовательности G1,..Gn, H1,...Hn, операцией растяжения ребер, что G подобен H (другими словами, например матрицы инцедентности полученных графов одинаковы, при условии точного соответствия между вершинами).

---------
Моя совесть чиста - не бывшая в употреблении
Ответ отправил: mvp (статус: 3-ий класс)
Отправлен: 27.08.2005, 14:56
Оценка за ответ: 5
Комментарий оценки:
Все как написано сделаю!


Отправить вопрос экспертам этой рассылки

Приложение (если необходимо):

* Код программы, выдержки из закона и т.п. дополнение к вопросу.
Эта информация будет отображена в аналогичном окне как есть.

Обратите внимание!
Вопрос будет отправлен всем экспертам данной рассылки!

Для того, чтобы отправить вопрос выбранным экспертам этой рассылки или
экспертам другой рассылки портала RusFAQ.ru, зайдите непосредственно на RusFAQ.ru.


Форма НЕ работает в почтовых программах The BAT! и MS Outlook (кроме версии 2003+)!
Чтобы отправить вопрос, откройте это письмо в браузере или зайдите на сайт RusFAQ.ru.


© 2001-2005, RusFAQ.ru, Россия, Москва. Все права защищены.
Идея, дизайн, программирование, авторское право: Калашников О.А.

Яндекс


Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора
Подписан адрес:
Код этой рассылки: science.exact.mathematicsfaq
Отписаться
Вспомнить пароль

В избранное