Page 3 - 4336

ЗМІСТ

ЗМІСТ .................................................................................................. 3

ВСТУП ................................................................................................. 6
РОЗДІЛ 1 АЛГОРИТМІЧНЕ ЗАБЕЗПЕЧЕННЯ

ПРИКЛАДНИХ ЗАВДАНЬ ТРАНСПОРТНО-

НАВІГАЦІЙНИХ ГІС ........................................................................ 7

1 ГРАФ ЯК МОДЕЛЬ ДОРОЖНЬОЇ МЕРЕЖІ. ОСНОВНІ

ПОНЯТТЯ ТА ВИЗНАЧЕННЯ З ТЕОРІЇ ГРАФІВ ......................... 7

1.1 Типи графів ........................................................................... 7

1.2 Степінь вершини графа ..................................................... 10

1.3 Способи задання графів ..................................................... 12

1.4 Маршрути, ланцюги і прості ланцюги ............................. 20
2 БАГАТОЗНАЧНІ ВІДОБРАЖЕННЯ. ТРАНЗИТИВНІ

ЗАМИКАННЯ. ЗНАХОДЖЕННЯ ТРАНЗИТИВНИХ

ЗАМИКАНЬ ПО МАТРИЦІ СУМІЖНОСТІ ................................. 25

2.1 Багатозначні відображення ............................................... 25

2.2 Транзитивні замикання ...................................................... 27

2.3 Знаходження транзитивних замикань по матриці

суміжності ......................................................................................... 29

3 ДОСЯЖНІСТЬ І КОНТРДОСЯЖНІСТЬ НА ГРАФАХ.

МАТРИЧНИЙ МЕТОД ЗНАХОДЖЕННЯ ШЛЯХІВ У

ГРАФАХ ............................................................................................ 34

3.1 Досяжність на графах ........................................................ 34

3.2 Контрдосяжність на графах .............................................. 36

3.3 Матричний метод знаходження шляхів у графах ........... 37

4 АЛГОРИТМИ ПОШУКУ ШЛЯХІВ ...................................... 40

4.1 Нормалізований граф, вага шляху .................................... 40
3