Page 10 - 6769

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

Вершину графа, з якою збіжні виключно ребра, що виходять з
даної вершини, називають джерелом. Якщо вершина становить
виключно вхід таких ребер, то вона називається стоком.
Дерево графа – підграф який має всі пов’язані вершини графа і
не має ні одного контуру. На рис. 3.3, а, в, г наведено приклади дерев
графа, зображеного на рисунку 3.2. В одному графі можемо виділити
багато дерев. Для подальшої роботи з графом вибирають одне і дерев.
Вибір „доброго” дерева має велике значення. Від цього вибору може
залежати кількість розрахункових операцій, які потрібно буде
здійснити для одержання бажаного результату. Докладніше про це ми
довідаємося згодом.
Вітки дерева (вітки) - ребра, які належать дереву графа. В
будь-якому графі кількість віток дорівнює q – 1.
Хорда - ребро графа, яке не є віткою дерева. В будь-якому
графі кількість хорд дорівнює p – (q – 1).
Головний (фундаментальний) контур графа – елементарний
контур графа, в якому є одна і тільки одна хорда, що співпадає з
напрямом хорди. Кількість головних контурів дорівнює кількості хорд
(p – (q - 1)).

10