и G має тільки одну сильно зв'язну компоненту, тобто якщо p = 1.
# # # v1 ----- Г v2 | 1 1 1 1 | | 1 0 0 0 |
| | | 0 1 1 0 | | 0 1 0 0 |
| | A (R *) = | 0 0 1 0 | A (RO) = | 0 0 1 0 |
v v | 0 0 1 1 | | 0 0 0 1 |
v4 ----- Г v3 p = 4
Таким чином, Gi = ({vi}, Ф), I in N4, є сильно зв'язковими компонентами заданого графа.
Шлях (орієнтована ланцюг), що містить всі дуги орграфа, називається ейлеровим. Зв'язний орграф називається ейлерова, якщо в ньому є замкнутий Ейлером шлях.
Теорема. Зв'язний орграф G містить відкритий Ейлером шлях тоді і тільки тоді, коли в ньому є дві такі вершини v1, v2, що
delta + (v1) = delta-(v1) +1, delta + (v2) = delta-(v2) -1, і
delta + (v) = delta-(v) для будь-якої вершини v, відмінної від v1 і v2.
Контур (замкнутий шлях) орграфа G називається гамильтоновой, якщо він містить всі вершини орграфа G. Гамільтон ГРАФ - це орграф, що має гамільтонів контур. p> Розпізнавання гамильтоновой орграфов і побудова гамільтонових контурів так само складні, як і для неорієнтованих графів. Розглянемо одне з достатніх умов гамильтоновой орграфа.
Теорема (Мейніел, 1973). Нехай G - сільносвязний орграф порядку n> 1 без петель і паралельних дуг. Якщо для будь-якої пари v і w його незбіжних несуміжних вершин справедливо нерівність
delta (v) + delta (w)> = 2 * n-1,
то в G є гамільтонів контур.
Нехай G = (V, E) - ациклічні Орграфа. Вершину v in V називається лист, якщо delta + (v) = 0. Якщо (v, w) in E, то v є безпосередніми предками w, а w - БЕЗПОСЕРЕДНІМ Нащадки v. Якщо існує маршрут з v у w, то говорять, що v є предками w, а w - нащадки v. Ці поняття не мають сенсу для графів, що мають цикли, так як в цьому випадку вершини в циклі були б нащадками і предками самих себе!
+ Гџ ------ v1 ----- Г + v4
v2 <----------------- v3 -----------> v5 <--------- v6
З вершин v2, v4, v5 дуги не виходять (листя графа), v1 є предком v5, v5 є нащадком v1 і прямим нащадком v3 і т.д.
Існує тісний зв'язок між ациклическими графами і частково впорядкованими відносинами. Часткові порядки будуть засновані скоріше на ставленні <, ніж на ставленні <=, і, отже, є Нерефлексівное і транзитивними.
Твердження:
а) Нехай G = (V, E) - а-ікліческій орграф і ставлення <визначається наступним чином: v
б) Нехай відношення <є частковим відношенням порядку на кінцевій множині V. Тоді, якщо E = {(v, w): v ОРІЄНТОВАНИЙ ДЕРЕВО T = (V, E) - е-о ациклічний орграф, в якому одна вершина vr in V не має предків і називається КОРЕНЕМ, а кожна інша вершина має рівно одного безпосереднього предка. Корінь з'єднується з будь інший вершиною єдиним маршрутом. Бінарногодерева - е-о орієнтоване дерево, в якому кожна вершина має не більше двох безпосередніх нащадків, тобто delta + (v) <= 2 для всіх v in V. Бінарне дерево є ПОВНИМ, якщо кожна вершина, яка не є листом дерева, має рівно 2 безпосередніх нащадка. Очевидно узагальнення на k-арное дерево. p> РІВЕНЬ ВЕРШИНИ - м-ксімальная довжина маршруту від цієї вершини до листа дерева.
ГЛУБИНА ВЕРШИНИ - д-іна шляху від кореня до цієї вершини.
ГЛУБИНА ОРДЕРЕВА - д-іна найдовшого шляху в Т.
Затвердження. Для повного k-арного ордерева, в якому всі l листя мають однакову глибину d, справедливо наступне:
l <= k ^ d; d = log (k) l.
планарности
Плоский граф - г-аф з вершинами, розташованими на площині і непересічними ребрами. Планарний граф ізоморфний плоскому. Всякий подграф планарного графа планарії. Задача про трьох будинках і трьох колодязях. Провести від кожного з трьох будинків доріжки до всіх трьом криниць так, щоб доріжки не перетиналися. Граф цього завдання не є планарним. Грань графа - м-ожество всіх точок площини, кожна пара яких може бути з'єднана жорданової кривої. Кордон грані - м-ожество вершин і ребер, що належать грані. Всякий плоский граф має одну, і притому єдину, необмежену грань. Ця грань є зовнішньою межею графа, решта - в-ранкові. p> Теорема Ейлера. Для всякого зв'язного плоского графа n-m + f = 2, де n - ч-сло вершин, m - ч-сло ребер, f - ч-сло граней. Подразбіеніе ребра - у-Ален ребра і додавання двох нових, інцідентних вершин віддаленого ребра і з'єднаних між собою новою вершиною. Два графа називаються гомеоморфними, якщо обидва вони можуть бути отримані з одного і того ж графа подразбіеніем його ребер. p> Теорема Понтрягіна-Куратовског о. Граф планарії тоді і тільки тоді, коли він не містить подграфов, гомеоморфних K5 і K3, 3. Дерева та ліс. Дерево - з-язний граф без циклів. Ліс (Або ациклічний граф) - н-ографія без циклів (може бути і незв'язним). p> Теорема. Для Неограф G з ...
