Теорія графів

Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали і т. п. розглядаються як вершини, а з'єднують їхні дороги, інженерні мережі, лінії електропередачі і т. п. - як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.


Формальне означення графа:
Нехай X = { x₁,…,x_n} – деяка скінченна множина (множина вершин), M₂ – множина всіх невпорядкованих пар елементів з X,
M₂ = { (x_i,x_j ): x_i ∈ X, x_j ∈ X, i ≠ j}

1. Граф G(X,W) – пара множин X,W ⊂ M₂. Множина X – це множина вершин, множина W – це множина ребер. Якщо (x_i,x_j ) ∈ W, то ми говоримо, що ребро (x_i,x_j ) сполучає вершину x_i з вершиною x_j; інша термінологія – ребро (x_i,x_j ) і вершини x_i та x_j інцидентні. 2. Граф G(X,W) називається повним, якщо W = M₂.
Якщо множина X містить n вершин, то, очевидно, число ребер повного графа дорівнює C_n². Повний граф з n вершинами позначається K_n.
3. Граф G(X,W) називається порожнім, якщо W = ∅.
4. Вершини x_i та x_j графа G(X,W) інцидентні, якщо (x_i,x_j ) ∈ W.
5. Степенем d( x_i ) вершини x_i графа G(X,W) називається число вершин x_j ,які інцидентні вершині x_i (число відрізків, які виходять з вершини x_i ).
6. Якщо d( x_i ) =1, то вершина x_i називається кінцевою вершиною графа G(X,W). Якщо d( x_i ) = 0, то вершина x_i називається ізольованою.