- •ОГЛАВЛЕНИЕ
- •ВВЕДЕНИЕ
- •ГЛАВА 1
- •1.1. Основное определение
- •1.2. Орграфы, псевдографы, мультиграфы и гиперграфы
- •1.3. Смежность
- •1.4. Изоморфизм графов
- •1.5. Элементы графов
- •1.6. Виды графов
- •1.7. Графы и отношения
- •1.8. Способы представления графов в памяти компьютера
- •ГЛАВА 2
- •2.1. Объединение графов и компоненты связности
- •2.2. Вершинная и реберная связность
- •2.3. Непересекающиеся цепи и разделяющие множества
- •2.4. Теорема Менгера
- •2.5. Теорема Холла
- •2.6. Связность в орграфах
- •2.7. Алгоритмы нахождения кратчайших путей
- •ГЛАВА 3
- •3.2. Потоки в сетях
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Приложение
МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УЛЬЯНОВСКОЕ ВЫСШЕЕ АВИАЦИОННОЕ УЧИЛИЩЕ ГРАЖДАНСКОЙ АВИАЦИИ (ИНСТИТУТ)
ТЕОРИЯ ГРАФОВ И СЕТЕЙ ПРИ МОДЕЛИРОВАНИИ ПРОЦЕССОВ УВД
Учебное пособие
Ульяновск 2009
ББК В176я7 + О580.3я7 Т 33
Теория графов и сетей при моделировании процессов УВД : учеб. пособие / сост. В. А. Карнаухов. – Ульяновск : УВАУ ГА(И), 2009. − 63 с.
Содержит основные положения теории графов и сетей, перечислены способы представления графов в памяти компьютера, необходимые для решения задач методами теории графов при помощи компьютерных технологий.
Изложено понятие связности в графах, орграфах, представлен теоретический материал о потоках в сетях, приведены алгоритмы нахождения кратчайших путей, алгоритм нахождения максимального потока, используемые при решении задач, которые находят свое практическое применение в ходе процессов планирования воздушного движения.
Разработановсоответствииспрограммойучебнойдисциплины«ТеорияУВД». Предназначено для курсантов и студентов заочной формы обучения специа-
лизации 160505.65.01 – Управление воздушным движением. Печатается по решению Редсовета училища.
© Ульяновск, УВАУ ГА(И), 2009
ОГЛАВЛЕНИЕ |
|
Введение......................................................................................................................... |
4 |
Глава 1. Основные положения теории графов........................................................... |
6 |
1.1. Основное определение...................................................................................... |
8 |
1.2. Орграфы, псевдографы, мультиграфы и гиперграфы.................................. |
10 |
1.3. Смежность........................................................................................................ |
11 |
1.4. Изоморфизм графов........................................................................................ |
11 |
1.5. Элементы графов.............................................................................................. |
12 |
1.6. Виды графов..................................................................................................... |
16 |
1.7. Графы и отношения......................................................................................... |
18 |
1.8. Способы представления графов в памяти компьютера............................. |
20 |
Глава 2. Связность графов......................................................................................... |
27 |
2.1. Объединение графов и компоненты связности............................................ |
27 |
2.2. Вершинная и реберная связность.................................................................. |
28 |
2.3. Непересекающиеся цепи и разделяющие множества............................... |
29 |
2.4. Теорема Менгера............................................................................................. |
30 |
2.5. Теорема Холла................................................................................................. |
33 |
2.6. Связность в орграфах...................................................................................... |
34 |
2.7. Алгоритмы нахождения кратчайших путей................................................. |
37 |
Глава 3. Транспортные сети....................................................................................... |
46 |
3.1. Моделирование процессов планирования воздушного движения............. |
46 |
3.2. Потоки в сетях.................................................................................................. |
52 |
Библиографический список....................................................................................... |
59 |
Приложение................................................................................................................. |
60 |
В. А. Карнаухов |
Теория графов и сетей при моделировании |
|
процессов УВД. Учебное пособие. |
ВВЕДЕНИЕ
Основная цель системы организации воздушного движения (ОВД) – наиболее эффективное использование воздушного пространства. В поиске новых условий функционирования систем, повышающих безопасность и экономичность, широко исследуются процессы в системе ОВД. Поскольку она является системой жизнеобеспечения и ее исследование существенно затруднено, применяют моделирование – распространенный метод исследования процессов и систем. Модели обладают подобием свойств реальных систем и процессов и отражают определенные количественные соотношения, имеющиеся в реальных системах.
Построение модели, отражающей совокупность всех свойств объектаоригинала, не имеет смысла, т. к. по сложности такая модель не будет уступать реальной системе, а это значит, что исследование на ней также сложно. В этом случае необходимы модели, отличающиеся уровнем абстрактного описания процессов и полнотой используемых соотношений. При исследовании систем применяют три вида моделей: блок-схемы или графы, математические и физические модели. Блок-схемы и графы называют иконографическими моделями. Их используют для представления структуры систем и соответствующих ей функциональных взаимодействий. Например, блок-схема совокупности контуров УВД: «диспетчер – радиолокатор, воздушное судно – пилот, радиопереговорное устройство – диспетчер». На практике приходится исследовать процессы в нескольких простейших контурах одновременно, в этом случае целесообразно рассматривать процессы в системе ОВД не по отношению к отдельному ВС, а по отношению к потокам.
Предметом исследования являются процессы, характеризующиеся степенью полноты загруженности зоны, задержками ВС или степенью возможных отказов. Они могут быть представлены в виде количественных характеристик, поз-
© НИЛ НОТ НИО УВАУ ГА(и), 2012 г |
4 |
В. А. Карнаухов |
Теория графов и сетей при моделировании |
|
процессов УВД. Учебное пособие. |
воляющих дать оценку использования воздушного пространства, выбранного для исследования. При этом воздушное пространство (зону УВД) или отдельные элементы, между которыми происходит движение ВС, удобно представить в виде сети маршрутов или связей. Такие сети моделируются в виде графов (или орграфов), где стрелки указывают направление потока сигналов, управляющих процессами или несущих о них информацию.
С помощью таких графов моделируются, например, сети радиосвязи борт – земля в системе УВД, когда требуется оценить их надежность. При сложной структуре сети авиатрасс с помощью графов также решается задача определения предельной пропускной способности при минимальных затратах.
Данное учебное пособие состоит из трех глав.
Первая глава является вводной. В ней представлена информация об общих положениях теории графов, которая знакомит читателя с понятием графа, его разновидностями и свойствами. Также перечислены способы представления графов в памяти компьютера, необходимые при решении методами теории графов задач с использованием компьютерных технологий.
Материал второй главы представляет собой подробное описание понятия связности, призванное подвести обучающихся к пониманию алгоритмов решения задач о нахождении кратчайших путей в графе. Их использование может легко найти практическое применение при моделировании процессов УВД.
Третья глава посвящена описанию потоков в сетях: дано понятие потока, приведены задачи планирования потока на сетях, рассмотрен алгоритм нахождения максимального потока. Данный алгоритм, применимый в графах, также может быть использован при планировании воздушного движения.
Таким образом, в предложенном учебном пособии содержатся общие сведения по теории графов, а также изложения процессов УВД на основе построения графов. Особое внимание сосредоточено на описании эффективных алгоритмов анализа графов, что позволяет решать практические задачи.
© НИЛ НОТ НИО УВАУ ГА(и), 2012 г |
5 |