Отправляет 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

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

Асмик Гаряка
Статус: Академик
Рейтинг: 8371
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Профессор
Рейтинг: 2599
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2140
∙ повысить рейтинг »

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

Номер выпуска:251
Дата выхода:25.08.2011, 02:30
Администратор рассылки:Асмик Гаряка (Академик)
Подписчиков / экспертов:57 / 67
Вопросов / ответов:1 / 1

Консультация # 183897: Уважаемые эксперты! Пожалуйста, ответьте на вопрос по графам: а) Применив алгоритм Прима построить минимальное остовное дерево для данного графа (построение начинать с вершины I). В ответе указать порядок включения ребер. б) Применив алгоритм Краскала, построить минимальное остовное дерево для данного графа. В ответе необходимо при...

Консультация # 183897:

Уважаемые эксперты! Пожалуйста, ответьте на вопрос по графам:

а) Применив алгоритм Прима построить минимальное остовное дерево для данного графа (построение начинать с вершины I).
В ответе указать порядок включения ребер.

б) Применив алгоритм Краскала, построить минимальное остовное дерево для данного графа. В ответе необходимо привести цвета вершин при каждом добавлении очередного ребра. Начальная раскраска: A-1, B-2,...
Добавляемое ребро перекрашивает цвет с меньшим номером в цвет с большим номером.




Заранее благодарю за помощь!

Дата отправки: 19.08.2011, 02:10
Вопрос задал: barhat (3-й класс)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Профессор):

Здравствуйте, barhat!

а) Алгоритм Прима состоит в следующем: на первом шаге искомое дерево состоит из одной произвольно выбранной вершины; на каждом очередном шаге среди рёбер, соединяющих одну из вершин дерева с любой вершиной, не принадлежащей дереву, выбирается ребро с наименьшим весом и добавляется к дереву (вместе с соответствующей вершиной); процесс заканчивается, когда все вершины графа принадлежат дереву.

В данном случае алгоритм Прима даёт следующее минимальное остовное дерево

IJ(1), JF(11), FC(4), CG(2), FB(10), BE(9), EA(5), GH(13), HD(3), JK(14), KL(18)

с суммарным весом рёбер 90.

б) Алгоритм Краскала в его классическом варианте состоит в следующем: на первом шаге множество рёбер пусто; на очередном шаге среди рёбер, не принадлежащих множеству и не образующих при добавлении к нему цикл, выбирается ребро с наименьшим весом и добавляется к мн ожеству; процесс заканчивается, когда таких рёбер больше нет.

В отличие от алгоритма Прима, где на каждом шаге имеется только одно дерево, в алгоритме Краскала множество рёбер может образовывать несколько деревьев (компонент связности). При добавлении нового ребра происходит либо прирост одного из деревьев на одну вершину, либо соединение двух деревьев в одно, либо образование нового дерева.

В данной задаче дополнительно используется раскраска вершин с последующим перекрашиванием. При этом каждая вершина изначально раскрашена в свой цвет, а каждое дерево - в цвет его вершины с максимальным номером. При добавлении нового ребра оно связывает вершину (дерево) с меньшим номером цвета и вершину (дерево) с большим номером цвета, объединяя их в одно дерево, окрашенное в цвет с большим номером. Процесс заканчивается, когда все вершины оказываются окрашены в один цвет (с максимальным номером).

Построение минимального остовного дерева будет выглядеть следующим обр азом:

HL(4) - A(1), B(2), C(3), D(4), E(5), F(6), G(7), H(12), I(9), J(10), K(11), L(12);
IJ(5) - A(1), B(2), C(3), D(4), E(5), F(6), G(7), H(12), I(10), J(10), K(11), L(12);
CG(8) - A(1), B(2), C(7), D(4), E(5), F(6), G(7), H(12), I(10), J(10), K(11), L(12);
BF(9) - A(1), B(6), C(7), D(4), E(5), F(6), G(7), H(12), I(10), J(10), K(11), L(12);
BC(10) - A(1), B(7), C(7), D(4), E(5), F(7), G(7), H(12), I(10), J(10), K(11), L(12);
GH(10) - A(1), B(12), C(12), D(4), E(5), F(12), G(12), H(12), I(10), J(10), K(11), L(12);
CD(16) - A(1), B(12), C(12), D(12), E(5), F(12), G(12), H(12), I(10), J(10), K(11), L(12);
GK(17) - A(1), B(12), C(12), D(12), E(5), F(12), G(12), H(12), I(10), J(10), K(12), L(12);
JK(23) - A(1), B(12), C(12), D(12), E(5), F(12), G(12), H(12), I(12), J(12), K(12), L(12);
EI(24) - A(1), B(12), C(12), D(12), E(12), F(12), G(12), H(12), I(12), J(12), K(12), L(12);
AB(30) - A(12), B(12), C(12), D(12), E(12), F(12), G(12), H(12), I(12), J(12), K(12), L(12).

Построено минимальное остовное дерево с суммарным весом рёбер 156.

Консультировал: Коцюрбенко Алексей aka Жерар (Профессор)
Дата отправки: 19.08.2011, 23:52

5
нет комментария
-----
Дата оценки: 22.08.2011, 13:50
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

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