| ← Сентябрь 2005 → | ||||||
|
4
|
||||||
|---|---|---|---|---|---|---|
|
7
|
8
|
10
|
11
|
|||
|
13
|
14
|
15
|
16
|
17
|
18
|
|
|
19
|
20
|
21
|
22
|
23
|
25
|
|
|
26
|
28
|
29
|
30
|
|||
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://rusfaq.ru
Открыта:
14-07-2005
Статистика
0 за неделю
RusFAQ.ru: Математика
| Информационный Канал Subscribe.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 Комментарий оценки: Все как написано сделаю! |
© 2001-2005, RusFAQ.ru, Россия, Москва. Все права защищены.
Идея, дизайн, программирование, авторское право: Калашников О.А.
Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора
Подписан адрес:
Код этой рассылки:
science.exact.mathematicsfaq
Отписаться
Вспомнить пароль
| В избранное | ||
