Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Январь 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по дискретной математике


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

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

Лучшие эксперты данной рассылки

Гордиенко Андрей Владимирович
Статус: Мастер-Эксперт
Рейтинг: 10218
∙ повысить рейтинг » 		Гаряка Асмик
Статус: Профессор
Рейтинг: 6736
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2275
∙ повысить рейтинг »

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

Номер выпуска:229
Дата выхода:15.01.2011, 20:30
Администратор рассылки:Гаряка Асмик (Профессор)
Подписчиков / экспертов:64 / 60
Вопросов / ответов:1 / 1

Вопрос № 181799: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Дан граф G={V,E},m(v)=8,m(E)=15. Требуется записать матрицу смежности графа, установить, является ли данный планарным, изобразить изоморфный ему плоский граф и записать для ...

Вопрос № 181799:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Дан граф G={V,E},m(v)=8,m(E)=15. Требуется записать матрицу смежности графа, установить, является ли данный планарным, изобразить изоморфный ему плоский граф и записать для него формулу Эйлера.
Матрицу смежности я записал, а вот изобразить ему плоский граф и записать для него формулу Эйлера не могу. Помогите пожалуйста!

Отправлен: 09.01.2011, 20:04
Вопрос задал: Посетитель - 356777 (Посетитель)
Всего ответов: 1
Страница вопроса »

Отвечает Гаряка Асмик (Профессор) :
Здравствуйте, Посетитель - 356777!



Граф планарен тогда и только тогда, когда он не содержит в качестве частей графы К5 и К3,3 (быть может с добавочными вершинами степени 2).

Как сделать граф плоским?
Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться гамма-алгоритмом.

На вход подаются графы, обладающие следующими свойствами:

1. граф связный;
2. граф имеет хотя бы один цикл;
3. граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две компонеты связности.

Если нарушено свойство (1), то граф нужно укладывать отдельно по компонентам связности.

Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально.

Случай нарушения свойства (3) рассмотрим более подробно. Если в графе есть мостики, то их нужно разрезать, провести отдельно плоскую укладку каждой компоненты связности, а затем соединить их мостиками. Здесь может в озникнуть трудность: в процессе укладки концевые вершины мостика могут спрятаться внутри плоского графа. Нарисуем одну компоненту связности и будем присоединять к ней другие последовательно. Каждую новую компоненту связности будем рисовать в той грани, в которой лежит концевая вершина соответствующего мостика. Так как граф связности мостиками компонент связности является деревом, мы сумеем получить плоскую укладку.

Гамма-алгоритм

1. (Инициализация). Выберем любой простой цикл C исходного графа G; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G′; сформируем сегменты Si; если множество сегментов пусто, то перейти к п. 3.
2. (Общий шаг). Пока множество сегментов непусто:
1. Для каждого сегмента S найти множество Γ(S). Если существует сегмент S, для которого |Γ(S)| = 0, то граф не планарный, конец.
2. Выбираем один из сегментов с минимальным числом, вмещающих его граней.
3. Выбираем одну из подходящих граней для выбранного сегмента.
4. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).
3. (Завершение). Построена плоская укладка G′ исходного графа G, конец.

Инициализация алгоритма производится так: выбираем любой простой цикл; в нашем примере { 2, 3, 5, 6, 7, 4} и получаем две грани: Γ1 — внешнюю и Γ2 — внутреннюю



Формула Эйлера: В связном планарном графе справедливо следующее:
p+q-r=2
p - вершины
r - ребра
q - грани
P=8
q=9
r=15

Ответ отправил: Гаряка Асмик (Профессор)
Ответ отправлен: 09.01.2011, 21:45
Номер ответа: 265308
Армения, Ереван
Тел.: 37493385079
Адрес сайта: http://rus-kniga.biz/tv11073127-3155712.html
ICQ # 166073765
Mail.ru-агент: hasmikgaryaka@bk.ru
Абонент Skype: hasmik7

Оценка ответа: 5

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 265308 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

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

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2011, Портал RFPRO.RU, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Калашников О.А. | Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2011.6.26 от 05.01.2011
    В избранное