 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
АЛГОРИТМ ФАЛКЕРСОНА
СЕТЕВЫЕ МОДЕЛИ
Основные понятия теории графов
Теория графов является эффективным алгоритмом формализации задач экономической и планово-производственной практики. Ее применяют в автоматизации управления производством, календарном и сетевом планировании, при оптимизации размещения производства, рационализации перевозок и т.д.
Представим множество точек на плоскости или в пространстве (вершины графа) и отрезки линий, соединяющих все или некоторые из этих точек. Взаимное расположение, длина, форма этих отрезков не имеют значения.
Если на отрезке указано направление, то он называется дугой.
Если ориентация не указана, отрезок называется ребром.
Совокупность вершин и дуг (ребер) называется графом.
Пример графа
Если концевые вершины дуги (ребра) совпадают, то дугу (ребро) называют петлей.
ПЕТЛЯ
Дуги и ребра с одинаковыми концевыми вершинами называются параллельными.
ПАРАЛЛЕЛЬНЫЕ ДУГА И РЕБРО
Граф называется конечным, если он содержит конечное число вершин.
Граф называется взвешенным, если каждая дуга (ребро) характеризуется одним или несколькими числами.
Если в графе все отрезки ориентированы, то он называется орграфом.
При изображении графа его вершины можно располагать произвольно и по своему усмотрению выбирать форму соединяющих их линий.
Графы называются изоморфными, если между их вершинами существует такое взаимно однозначное соответствие, при котором две вершины одного графа соединены отрезками тогда и только тогда, когда соответствующие вершины другого графа соединены отрезками. При этом направление дуг сохраняется.
| ИЗОМОРФНЫЕ ГРАФЫ | |
| 1 2 | 1 4 3 2 |
Граф называется простым, если он не содержит петель и параллельных дуг (ребер).
Путем в орграфе называется последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей.
Циклом называется путь, у которого совпадают начальная и конечная вершины.
Для графов существует способ упорядочения (алгоритм Фалкерсона).
1)Находят вершины графа, в которые не входит ни одна дуга. Эти вершины образуют первую группу. Нумеруют вершины группы в натуральном порядке 1,2,…. При этом присвоение номеров внутри группы может быть произвольным.
2)Мысленно вычеркивают все пронумерованные вершины и дуги из них выходящие. В полученном графе находят вершины графа, в которые не входит ни одна дуга. Эти вершины образуют вторую группу. И т.д.
Аналогично можно упорядочивать по дугам.
АЛГОРИТМ ФАЛКЕРСОНА
| 4 7 3 1 5 6 2 |
| 6-4 6-5 6-2 4-3 4-7 3-7 3-1 1-7 2-5 5-1 5-7 |
| 4 7 3 1 5 6 2 |
| 4 7 3 1 5 6 2 |
| 4 7 3 1 5 |
| 3 1 5 |
| 4 3 6 1 7 2 5 |
| 7 3 6 1 2 |
Пример 2
| 1 3 6 2 4 7 5 8 |
| 1-2 1-3 1-5 1-7 2-7 2-8 3-4 3-6 4-8 5-8 6-4 7-6 |
| 1 3 6 2 4 7 5 8 |
| 1 3 6 2 4 7 5 8 |
| 1 группа вершина 1 |
| 1 3 6 2 4 7 5 8 |
| Вторая группа вершины 3,2,5 |
| 1 3 6 2 4 7 5 8 |
| 1 3 6 2 4 7 5 8 |
| Третья группа вершина 7 |
| 1 3 6 2 4 7 5 8 |
| 1 3 6 2 4 7 5 8 |
| Четвертая группа вершина 6 |
| Пятая группа вершина 4 |
| Шестая группа вершина 8 |
| 1 7 6 4 8 |
Поиск по сайту: