Алгоритм Дейкстра

Цикломатичне число і фундаментальні цикли

Цикломатичрим числом графа G=(V,E) називається з k зв'язковими компонентами називається число (G)=|E|-|V|+k.Фундаментальним циклом графа G=(V,E) з основним деревом T=(V,E') називається простий цикл, одержуваний у результаті додавання в T одного з ребер G, не приналежного E'.

Твердження 1. Кількість фундаментальних циклів графа G=(V,E) при будь-якому фіксованому основним дереві T=(V,E') дорівнює цикломатичному числу G.

Доказ: відповідно до лемма 3 п.2, k=|V|-|E'|, отже, <кількість ребер G, не приналежних E'> = |E|-|E'| = |E|-(|V|-k) = (G). При додаванні кожного з цих ребер у T з'являється рівно один простий цикл у силу теоремі 3 п.6; всі одержувані при цьому прості цикли різні, тому що кожний з них містить принаймні одне унікальне ребро - те саме ребро G, не приналежне E', що було додано в дерево.

~

Компланарні графи

Зіставивши вершинам графа крапки на чи площині в просторі, а ребрам - лінії, що з'єднують крапки, що відповідають кінцям ребра, можна одержати діаграму - візуальне представлення даного графа.

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

Теорема 1. Для будь-якого графа існує геометрична реалізація в тривимірному евклідовому просторі.

Доказ:

1.реалізуємо |V| крапок, що відповідають вершинам графа, на одній прямій;

2.проведемо через цю пряму |E| різних на півплощин;

3.реалізуємо кожне ребро у своїй на півплощині.

~

Виникає питання: чи будь-який граф можна реалізувати на площині? Відповідь - негативний. Геометричну реалізацію на площині допускають лише деякі графи; такі графи називаються компланарними.

Для наступного викладу нам знадобиться поняття грані. Неформально визначимо грань як частина площини, на які площина "розрізається" лініями геометричної реалізації графа. Завжди існує необмежена зовнішня грань.

- 7 вершин, 8 ребер, 3 грані

Формула Ейлера. Для будь-якої геометричної реалізації графа G=(V,E) на площині вірно: p-q+r=2, де p=|V|, q=|E|, r - число граней (без доказу).

Теорема 2. Якщо в зв'язковому планарним графі немає циклів довжини менше k і k3, то qk(p-2)/(k-2), де p=|V|, q=|E|.

Доказ (не зовсім формальне): нехай граф реалізований на площині і при цьому вийшло r граней. Нехай qi - число сторін у i-й грані (див. малюнок). Кожне ребро є стороною двох граней, тому 2q=Sum(qi, i=1..r). По умови в графі немає циклів довжини менше k, але тоді qik (тому що сторони грані утворять цикл) і 2q=Sum(qi, i=1..r)kr. По формулі Эйлера r=2-p+q, отже, 2qk(2-p+q), з чого випливає доказувана нерівність.