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

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

Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.

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

Рассмотрим конечный ориентированный граф Г=(X,u), в котором Х={x1,...,xn}-множество вершин, U – множество дуг.

Пусть x??X. Обозначим E+(x) – множество дуг графа, входящих в х, E-(x) – выходящих из х.

Множества начальных вершин дуг из Е+(х) и множество конечных вершин дуг из Е-(х) обозначим соответственно S+(x) и S-(x).

E+(x) E-(x)

y x y

S+(x) S-(x)

Рис. 3. Окрестность вершины графа.

Граф Г называют транспортной сетью, если каждой дуге u соответствует целое число c(u)>=0 и найдутся x0 и z из Х такие, что Е+(х0)=

Е-(z)= . Вершина х0 называется истоком, z-стоком, c(u) – пропускной способностью дуги. Потоком в транспортной сети называют целочисленную функцию ф(u), удовлетворяющую следующим условиям :

1) 0<=ф(u)<=с(u)

2) ф(u) - ф(u) = 0 для любой вершины x=/=x0, x=/=z.

u??Е+(х) u??Е-(х)

При этом поток не может «накапливаться» ни в одной вершине транспортной сети, кроме истока х0 и стока z, поэтому

ф(u) = ф(u) = Ф.

u??Е+(х) u??Е-(х)

Величину Ф называют потоком транспортной сети. Дуга u называется насыщенной, если ф(u)=c(u). Поток Ф называется полным, если каждый путь из х0 в z содержит хотя бы одну насыщенную дугу.

Рассмотрим разбиение R множества вершин сети Х = Х1UX2,

X1?X2??X1?X2=?, x0?X1, z?X2, называемое разрезом сети.

Сумма пропускных способностей множества {(xi,xj), xi из X1, Xj из Х2} определяет пропускную способность разреза R : r(R) = c(u),

u?{(xi,xj):xi ?X1, xj?X2}

Поскольку для любой дуги u выполняется неравенство ф(u)<=c(u), то Ф<=r(R).

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Актуальность
Цель
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.Архитектура имитационной модели глобальной сети
Заключение
Список литературы :