7 группа/

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск

Связность графа

Определение Связнности- Граф называется связным, если любая пара его вершин связана. Покажите, что отношение связанности вершин является отношением эквивалентности Определение Связные компонент.-Связными компонентами графа называются подграфы данного графа, вершины которых являются классами эквивалентности отношения свзанности в данном графе. Докажите, что связная компонента является связным графом. Определение Цикломатическое число - Цикломатическим числом графа называется число связных компонент графа плюс число рёбер минус число вершин.


Rew.jpg

Определение Дерево Связный граф без циклов называется деревом.

Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеологические деревья. Пример 5 (генеологическое дерево). На рисунке показано библейское генеологическое дерево. Докажите, что граф является деревом тогда и только тогда, когда любая пара различных вершин соединена единственной цепью. Докажите, что граф является деревом тогда и только тогда, когда он связен, но после удаления любого ребра становится несвязным. Докажите, что количество рёбер дерева на единицу меньше количества вершин.Оспределение 14 (Лес, листья). Граф без циклов называется лесом. Вершины степени 1 в дереве называются листьями. New.jpg