Программирование на сетях

  • Просмотров 193
  • Скачиваний 7
  • Размер файла 271
    Кб

Содержание: Введение 2 1. Основные понятия теории графов. 3 2. Матричные способы задания графов. 4 3. Упорядочение элементов орграфа. 6 4. Постановка задачи о максимальном потоке. Основные определения. 8 5. Разрез на сети. 11 6. Алгоритм решения задачи о максимальном потоке. 13 Заключение. 20 Список использованной литературы 21 Введение В последнее время в различных областях знаний широко применяется теория графов. С помощью теории графов

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

пространства и множество отрезков кривых или прямых линий, соединяющих все или некоторые из этих точек. Формально граф G определяется заданием двух множеств X и U и обозначается G=(XU). Элементы xB1B, xB2B, …, xBn B множества X называются вершинами и изображаются точками. Элементами uB1B, uB2B, …, uBm множества U являются пары связанных между собой элементов множества X и изображаются отрезками. Взаимное расположение, форма и длины отрезков

значения не имеют. Если в паре вершин xBi Bи B BxBj Bуказано направление связи, то есть указано, какая вершина является первой, то отрезок UB1 Bназывается дугой, а если ориентация не указана, - ребром. Если в графе G все элементы множества U изображаются дугами, то граф называется ориентированным (орграф), если ребрами, - неориентированным. На практике используются графы, в которых множества X и U состоят из конечного числа элементов, то есть

конечные графы. На рисунке располагать вершины графа можно произвольно. Также произвольно выбирается и форма соединяющих их линий. Поэтому один и тот же граф (граф с одной и той же информацией) может быть представлен в различных видах. Такие графы называются изоморфными. Смежными называют вершины графа, если они различны и существует дуга (ребро), которая соединяет эти вершины. Если две дуги (ребра) имеют общую концевую вершину,