Дискретная математика
Нахождение пути минимального веса между вершинами в нагруженном графе с помощью алгоритма Дейкстры. Максимальный поток в транспортной сети с использованием алгоритма Форда-Фалкерсона. Проверка по теореме Форда-Фалкерсона. Пропускные способности дуг.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 03.10.2017 |
| Размер файла | 328,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Курсовая работа
Дискретная математика
Решенина И.И.
1. С помощью алгоритма Дейкстры найти путь минимального веса между вершинами s и t в нагруженном графе.
Размещено на http://www.allbest.ru/
Решение
Прямого пути из вершины в вершину нет. Поэтому применим алгоритм Дейкстры. граф алгоритм дуга
Вершине присваиваем метку 0. Все остальные вершины имеют метки . Из вершины можно напрямую попасть в вершины и . Это кратчайшие расстояния, поэтому метки этих вершин заменяем соответствующими весами графа (зелёный цвет). Вершина считается посещённой, поэтому вычёркиваем её. Получим:
Ближайшая из непосещённых вершин - вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен ( - путь из вершины в вершину , - путь из вершины в вершину ). , поэтому вес вершины будет равен . Путь в вершину будет равен , поэтому вес вершины будет равен . Путь в вершину будет равен ). , поэтому вес вершины станет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:
Ближайшая из непосещённых вершин - вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен . , поэтому вес вершины останется равным . Путь в вершину будет равен , поэтому вес вершины будет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:
Ближайшая из непосещённых вершин - вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен , поэтому вес вершины останется равным . Путь в вершину будет равен ). , поэтому вес вершины станет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:
Ближайшая из непосещённых вершин - вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен . , поэтому вес вершины станет равен . Путь в вершину будет равен , поэтому вес вершины будет равен . Путь в вершину будет равен ). поэтому вес вершины останется равным . Вершина становится посещённой, поэтому вычёркиваем её. Получим:
Ближайшая из непосещённых вершин - вершина . Из неё можно попасть в вершины и . Путь в вершину будет равен , поэтому вес вершины останется равным . Путь в вершину будет равен ). , поэтому вес вершины станет равен . Вершина становится посещённой, поэтому вычёркиваем её. Получим:
Ближайшая из непосещённых вершин - вершина . Из неё можно попасть в вершину . Путь в вершину будет равен . , поэтому вес вершины останется равным . Вершина становится посещённой, поэтому вычёркиваем её. Из вершины больше никуда попасть нельзя, поэтому её также вычёркиваем Получим:
Все вершины графа получились вычеркнутыми. Поэтому найдены минимальные пути из вершины во все остальные. Вес вершины равен , поэтому кратчайший путь из вершины в вершину равен .
Пути следующие:
2. Найти максимальный поток в заданной транспортной сети, используя алгоритм Форда-Фалкерсона. Проверить ответ по теореме Форда-Фалкерсона (найти минимальный разрез графа сети).
Решение
С помощью алгоритма Форда-Фалкерсона найдем наибольший поток из в .
Шаг 1. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть . Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.
Шаг 2. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть .
Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.
Шаг 3. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть .
Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.
Шаг 4. Выбираем произвольный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть .
Уменьшаем пропускные способности дуг этого потока на , насыщенную дугу вычеркиваем.
Шаг 5. Остался один возможный поток, например, . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть . Уменьшаем пропускные способности дуг этого потока на , насыщенные дуги вычеркиваем.
Больше путей нет. Суммарный поток равен: .
Начинаем расстановку пометок. Начальная вершина (источник) имеет пометку 0. Из этой вершины нет ненасыщенных дуг, поэтому большепометки расставить нельзя.
Значит, максимальный поток найден, причем (непомеченные вершины) образуют разрез. Источником теперь является вершина . Величина разреза .
3. По матрице инцидентности построить остовное дерево графа. Составить список ветвей и хорд графа. Построить граф.
Решение
Построим сам граф. Столбцы - вершины графа, строки - его рёбра. Если ребро инцидентно вершине, то клетка будет закрашена. Получим:
Составим остовное дерево для данного графа. Остовное дерево графа - это подграф графа, состоящий из всех вершин графа и минимального числа рёбер так, чтобы из любой вершины можно добраться в любую. Сначал включаем в оствное дерево ребро Ребро добавляет к остовному дереву вершину , его также включаем. Ребро добавляет к остовному дереву вершину , его также включаем. Ребро добавляет к остовному дереву вершину , его также включаем. Ребро добавляет к остовному дереву вершину , его также оставляем. Ребро добавляет к остовному дереву вершину , его также оставляем. Ребро не добавляет к остовному дереву новых вершин, поэтому его в остовное дерево не включаем. Ребро добавляет к остовному дереву вершину , поэтому его также включаем. В остовное дерево включены все вершины графа, поэтому остовное дерево построено.
4. а) Написать таблицу состояний данного автомата.
б) Считая автомат неинициальным, построить эквивалентный автомат Мура. Проверить работу данного и построенного автоматов над одним и тем же словом.
Решение.
Изобразим таблицу данного автомата
|
A\Q |
1 |
2 |
3 |
4 |
|
|
a |
1,0 |
4,1 |
1,0 |
2,1 |
|
|
b |
3,1 |
3,1 |
4,0 |
4,0 |
По данному неинициальному автомату Мили строим эквивалентный ему автомат Мура следующим образом:
Автомат содержит состояний, каждое из которых мы будем помечать двумя символами. Состояния автомата обозначим так: , , , , , , , , , , , .
|
м |
- |
- |
- |
- |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
A\Q |
*1 |
*2 |
*3 |
*4 |
a1 |
b1 |
a2 |
b2 |
a3 |
b3 |
a4 |
b4 |
|
|
a |
a1 |
a2 |
a3 |
a4 |
a1 |
a3 |
a4 |
a3 |
a1 |
a4 |
a2 |
a4 |
|
|
b |
b1 |
b2 |
b3 |
b4 |
b1 |
b3 |
b4 |
b3 |
b1 |
b4 |
b2 |
b4 |
Проверим работу исходного автомата над словом , запустив его из 2 состояния:
Построенный автомат Мура запускаем из состояния
Как видим, результаты обоих автоматов совпали.
Размещено на Allbest.ru
Подобные документы
Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
контрольная работа [740,3 K], добавлен 09.03.2015Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.
курсовая работа [311,3 K], добавлен 15.06.2015Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
курсовая работа [362,9 K], добавлен 24.11.2010Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Минимальное остовное дерево связного взвешенного графа и его нахождение с помощью алгоритмов. Описание алгоритма Краскала, возможность строить дерево одновременно для нескольких компонент связности. Пример работы алгоритма Краскала, код программы.
курсовая работа [192,5 K], добавлен 27.03.2011
