Page 11 - 6769

Рисунок 3.4 – Головні контури графа

На рис. 3.4 зображено граф, в якому за базовий вузол прийнято
вузол D, вітки дерева зображені суцільними лініями, хорди –
пунктирними, головні контури – штрих-пунктирними. На підставі
рисунку наглядно видно, що головні контури можемо визначити
єдиним чином (провести їх іншим чином неможливо).У загальному
випадку нумерацію вершин графа (вузлів), ребер графа (віток дерева
та хорд ) та головних контурів можемо здійснювати довільним чином,
але корисно дотримуватись певних правил.
Зверніть увагу, ми спочатку пронумерували вітки дерева, а
потім хорди. Головні контури нумеруємо в порядку наростання
номерів хорд. Наприклад, найменшому номеру хорди, який дорівнює
4, відповідає перший номер головного контуру.
Перетин графа – замкнута поверхня, яка перетинає граф
таким чином, що частина графа розташована всередині поверхні. З
поверхні назовні виходять та входять вітки дерева чи хорди. Якщо з
перетину серед сукупності ребер виходить одна і тільки одна вітка
дерева (решта тільки хорди), то перетин називають головним
(фундаментальним). Кількість перетинів в графі може бути великою,
але кількість головних перетинів дорівнює q – 1.
Порівняйте рисунки 3.2 та 3.4. Ми змінили напрями віток
дерева лише з метою щоб вузли A, B та C стали головними
перетинами (поверхня головного перетину стиснулася в вузол).

11