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

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

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Февраль 2013   →
 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


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


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

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

Статистика

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

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


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

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

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

Асмик Гаряка
Статус: Советник
Рейтинг: 11013
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Советник
Рейтинг: 4026
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2108
∙ повысить рейтинг »

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

Номер выпуска:305
Дата выхода:09.02.2013, 15:30
Администратор рассылки:Асмик Гаряка (Советник)
Подписчиков / экспертов:27 / 32
Вопросов / ответов:1 / 2

Консультация # 187152: Здравствуйте! У меня возникли сложности с таким вопросом: 1. Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса; б) кратчайшее расстояние от вершины v5 до остальных вершин графа, используя алгоритм Дейкстры.
...

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

Здравствуйте! У меня возникли сложности с таким вопросом:
1. Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса;
б) кратчайшее расстояние от вершины v5 до остальных вершин графа, используя алгоритм Дейкстры.
∞ ∞ ∞ 2 3 4
∞ ∞ 3 ∞ 1 2
∞ 3 ∞ 5 ∞ 1
2 ∞ 5 ∞ 4 1
3 1 ∞ 4 ∞ ∞
4 2 1 1 ∞ ∞

2. , решать следует по полиномиальной теореме.

Дата отправки: 06.02.2013, 14:49
Вопрос задал: Посетитель - 395932 (Посетитель)
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Асмик Гаряка (Советник):

Здравствуйте, Посетитель - 395932!

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

В графе имеется 2 ребра весом 1 и 2 ребра весом 2. Добавляем их, при этом в подграфе нет циклов. Из двух ребер веса 3 ребро между 1 и 5 не вызывает появления цикла. Добавим его. Добавление любого другого ребра вызывает появления цикла. Алгоритм завершен.

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

3
Коэффициент при a - x в степени 2, y^2 в степени 2, z в степени 2, следовательно, он равен 6!/(2!)^3=90
Учитывая коэффициенты при y и z, 90*42*52=36000
b задан неправильно, степерь при y должна быть четной
c - y^2 в степени 3, z в степени 2, следовательно, он равен
Учитывая коэффициенты при y и z, 15*42*54=150000

Консультировал: Асмик Гаряка (Советник)
Дата отправки: 06.02.2013, 16:07
Прикреплённый файл: посмотреть » [10.8 кб]
Рейтинг ответа:

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

Консультирует Гордиенко Андрей Владимирович (Модератор):

Здравствуйте, Посетитель - 395932!

2. Сразу видно, что коэффициент при b равен нулю, потому что одночленов с y3 в представлении полинома нет. Коэффициенты при a и c удобно искать, положив X = x, Y = 4y2, Z = 5z. Тогда получим следующие результаты:
- число одночленов вида x2y4z2 равно числу одночленов вида X2Y2Z2 и составляет 6!/(2!2!2!) = 90;
- число одночленов вида y4z4 равно числу одночленов вида X0Y2Z4 и составляет 6!/(0!2!4!) = 15.

Следовательно,

(x + 4y2 + 5z)6 = (X + Y + Z)6 = ... + 90X2Y2Z2 + ... + 15X0Y2Z4 + ... =

= ... + 90x2(4y2)2(5z)2 + ... + 15x0(4y2)2( 5z)4 + ... = ... + 36000x2y4z2 + ... + 150000y4z4.


Ответ: коэффициент при a равен 36000, коэффициент при b равен нулю, коэффициент при c равен 150000.

С уважением.

Консультировал: Гордиенко Андрей Владимирович (Модератор)
Дата отправки: 06.02.2013, 16:54
Рейтинг ответа:

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

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

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

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

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