перейти к полному списку дипломных проектов

Ссылка на скачивания файла в формате .doc находится в конце странички

Алгоритм Форда-Фалкерсона

Предполагается, что путь из истока в сток с ненулевыми пропускными способностями входящих в него дуг существует.

I. Увеличение потока.

1. Присвоить истоку х0 пометку (+х0, d(x0) = ). Это означает, что вход в исток не ограничен; величина d всегда показывает, на сколько может быть увеличен поток, входящий в помеченную вершину. Здесь символ обозначает достаточно большое число – начальное значение пометки.

2. Взять некоторую вершину xi с пометкой, которая в общем случае имеет вид (+ или – xk, d(xi)), где xk – обозначение вершины, d(xi) – некоторое число. Каждой непомеченной вершине xj из S-(xi), для которой ф(xi,xj)<с(xi,xj), присвоить пометку (+xi, min[d(xi),c(xi,xj)-ф(xi,xj)]). Это означает, что поток в дуге (xi,xj) может быть увеличен (знак плюс) на величину, определяемую минимумом. Каждой непомеченной вершине xj из S+(xi), такой, что ф(xj,xi)>0 присвоить пометку (-xi, min[d(xi), ф(xj,xi)]), что означает возможность уменьшения потока на величину, определяемую минимумом.

3. Если сток не помечен и можно пометить какую-либо вершину, кроме стока, то перейти к п.2.

4. Если оказался помеченным сток z, и в его пометку входит число d(z), то между вершинами x0 и z найдется цепь, все вершины которой помечены номерами предыдущих вершин. Для каждой помеченной вершины х в этой цепи изменить величину потока : ф'(y,x)=ф(y,x)+d(z), если х имеет пометку (+y,d(x)) или ф'(y,x)=ф(y,x)-d(z), если х имеет пометку (-y,d(x)). Пометка вершины х стирается, назначенные потоки запоминаются. При достижении (в процессе стирания пометок вершин цепи) истока х0 перейти к п.1; если же ни одну вершину пометить не удается и сток z не помечен, то перейти к построению разреза.

II.Построение разреза.

Искомый минимальный размер R определяется двумя множествами Х1 и Х2, где Х1 – все помеченные вершины, Х2 – вершины, которые не удается пометить. При этом полный поток Ф=Ф* должен быть равен величине полученного минимального разреза.

2.Сетевые структуры на базе

теоретико-графовых моделей

скачать бесплатно Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей

Содержание дипломной работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Актуальность
Цель
1.1. Основные понятия теории графов
1.2. Графовые алгоритмы
Алгоритм Форда-Беллмана
Алгоритм Дейкстры нахождения кратчайших расстояний от источника до всех остальных вершин применим только тогда
Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.
Теорема Форда-Фалкерсона : максимальный поток в сети равен минимальной величине разрезов в этой сети.
Алгоритм Форда-Фалкерсона
2.1. Методы построения сетевых структур
2.2. Классификация существующих методов организации сетей
Типы кабелей
Толстый кабель обеспечивает передачу сигналов на большие расстояния
Витая пара дешевле коаксиального кабеля и менее надежна. Использование неэкранированной витой пары позволяет реализовать длину сегментов соединения до 100 метров. Для подключения витой пары используются восьмиконтактные коннекторы RG-45.
Оптоволоконный кабель имеет высокую стоимость и обладает рядом преимуществ : слабое затухание сигнала
Платы сетевого адаптера
2.3. Глобальная сеть Internet
Зарезервированные сокеты
Транслирующие серверы
Адресация Internet
Служба доменных имен (DNS)
2.4. Основы сетевой маршрутизации
Компоненты маршрутизации
Определение маршрута
Коммутация
2.5. Алгоритмы маршрутизации
Цели разработки алгоритмов маршрутизации
Оптимальность
Простота и низкие непроизводительные затраты
Живучесть и стабильность
Быстрая сходимость
Гибкость
Типы алгоритмов
Статические или динамические алгоритмы
Одномаршрутные или многомаршрутные алгоритмы
Одноуровневые или иерархические алгоритмы
Алгоритмы с интеллектом в главной вычислительной машине или в роутере
Внутридоменные или междоменные алгоритмы
Алгоритмы состояния канала или вектора расстояния
Показатели алгоритмов (метрики)
Длина маршрута
Надежность
Задержка
Полоса пропускания
Нагрузка
Стоимость связи
3.1. Описание стандартного броузера
3.2. Характеристика существующих систем поиска
3.3. Особенности создания поисковых систем в визуальных средах программирования
Приложения для работы в Internet
4.1.Архитектура системы “Броузер”
4.2.Основные процедуры броузера
4.3.Архитектура имитационной модели глобальной сети
Заключение
Список литературы :