an> , v 4 ) , (v 4 , v 3 ).
В
Граф називається зв'язковим, якщо в ньому для кожної пари вершин знайдеться з'єднує їх ланцюг.
Зв'язний і незв'язних граф представлений на рис.3.9.
В
Будь граф можна розглядати як деяку сукупність зв'язкових графів. Кожен з цих графів називається компонентом вихідного графа. p align="justify"> Незв'язний граф, зображений на рис. 3.9, має два компоненти. p align="justify"> Безліч дуг, виключення яких з графа збільшує число його компонентів, називається розрізом.
Для зв'язного графа, зображеного на рис. 3.9, розрізом є виділена дуга e, так як її видалення збільшує число компонентів до двох. p align="justify"> Нехай G = (V, E), V Вў ГЌ V, тоді граф, множина вершин якого співпадає з V Вў , а безліч дуг включає всі дуги множини E з кінцевими вершинами в V Вў , називається подграфом графа G, породженим V Вў .
Нехай E Вў ГЌ E, тоді граф, для якого безліч дуг збігається з E Вў , а безліч вершин включає вершини, інцідентние дуг з E Вў , називається подграфом графа G, породженим E Вў .
Граф називається повним, якщо будь-які дві його вершини суміжні.
Граф G називається порожнім, якщо в ньому немає ребер.
Граф, який не містить циклів, називається ациклічним.
Зв'язний неорієнтоване ациклічний граф називається деревом, безліч дерев називається лісом.
Якщо ребра, складові дерево, замінити орієнтованими дугами, то отримаємо орієнтоване дерево. Якщо з контексту ясно, про якому дереві йдеться, то надалі слово В«орієнтованеВ» будемо опускати. p align="justify"> Для орієнтованого дерева має сенс ввести поняття кореня. Мінімальна за потужністю безліч вершин орієнтованого дерева, з яких існують шляхи в усі решта вершини, будемо називати безліччю коренів. p align="justify"> покриваємо (остовне) деревом графа G називається дерево, яке є подграфом графа G і містить всі його вершини.
Якщо граф G незв'язний, то безліч, що складається з основних дерев кожної компоненти, називається покриває (остовне) лісом. ...
