Xreferat.com » Рефераты по математике » Решение практических заданий по дискретной математике

Решение практических заданий по дискретной математике

/>


Выбираем произвольно путь из вершины v1 в вершину v6 . Пусть это будет путь Решение практических заданий по дискретной математике. Минимальную пропускную способность на этом пути, равную 10, имеет дуга Решение практических заданий по дискретной математике, т.е. Решение практических заданий по дискретной математике Увеличим на этом пути поток до 10 единиц. Дуга Решение практических заданий по дискретной математике становится насыщенной. Дуга Решение практических заданий по дискретной математике имеет на данный момент пропускную способность, равную 10.

Путь Решение практических заданий по дискретной математике Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги Решение практических заданий по дискретной математике становятся насыщенными.

Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v1 по насыщенным дугам

Решение практических заданий по дискретной математикеРешение практических заданий по дискретной математике


и получаем его величину Решение практических заданий по дискретной математике единиц.

8. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа Решение практических заданий по дискретной математике, у которого Решение практических заданий по дискретной математике, если заданы веса (длины) ребер:

Решение практических заданий по дискретной математике

□ Построим граф G :


Решение практических заданий по дискретной математике


1. Упорядочим ребра в порядке неубывания веса (длины):

Решение практических заданий по дискретной математике


Решение практических заданий по дискретной математике


2. Возьмем ребро u1 и поместим его в строящийся остов.

Возьмем ребро u2 и поместим его в строящийся остов (т.к. оно не образует с предыдущим ребром цикла).

Берем ребро u3 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u4 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u5 и помещаем его в строящийся остов (т.к. оно не образует цикла с предыдущими ребрами).

Ребра Решение практических заданий по дискретной математике не рассматриваем, т.к. они образуют циклы с предыдущими ребрами.

Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и Решение практических заданий по дискретной математике. Таким образом, остов содержит все вершины заданного графа G .

Вес (длина) построенного остова


Решение практических заданий по дискретной математике


равен Решение практических заданий по дискретной математикеРешение практических заданий по дискретной математике.


Литература


1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго атомиздат, 1987. – 496 с.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.

4. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. - 400 с.

5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.

6. Хаханов В.И., Чумаченко С.В. Дискретная математика ( конспект теоретического материала). – Харьков: ХНУРЭ, 2003. – 246 с.

7. Богданов А.Е. Курс лекций по дискретной математике.–Северодонецк: СТИ, 2006. – 190 с.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: