Page 7 - 4336

РОЗДІІЛ 1

АЛЛГОРИИТМІЧЧНЕ ЗААБЕЗПЕЕЧЕНННЯ ПРИИКЛАДДНИХ

ЗЗАВДААНЬ ТРАРАНСПООРТНОО-НАВВІГАЦІЙЙНИХХ ГІС

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

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

Числоове модделюванння навіігаційниих мерееж (напприклад,,

мерреж доріг) тісно пов'язанне з теоррією граффів, яка математтичнимии

меттодами маніпуулює сструктуррами т типу ““вершинна-дуга”..

Напприклад,, якщо гграф є ммоделлюю деякоїї дорожнньої меррежі, тоо

перрехрестя і перетиини вулииць преддставляюються верршинамии графа,,

а дууги інтеррпретуюють дозвоолені наапрями рруху міжж перехреестями іі

перретинамии вулицць. Моодель гррафа у своїй основіі добрее

преедставляє струкктури ввекторноого типпу із ццифрових карт,,

незалежно від їх прризначенння.

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

Граф задаєтьсся множжиною тоочок абоо вершиин v , v ,, ..., v іі
n
2
1
мноожиною ліній аббо реберр e , e , ... , e , щщо з'єднуують міжж собоюю
2
1
m
всі або часттини точчок (рис.. 1.1).

а б в

Риисунок 11.1 – Приклади гграфів

Нехайй V  деяка неппорожняя скінчеенна множина, а V (2)  

мноожина вссіх двоххелементтних піддмножинн (невпор рядковааних парр

різнних елемментів) ммножинии V.

7