Материал предоставлен http://it.rfet.ru

Деревья

Важным частным случаем графа является дерево. Это название связано с типичным видом некоторых представителей данного класса. Дадим определение.

Определение 6. Деревом называется связный граф, не содержащий циклов. Несвязный граф, не имеющий циклов, называют лесом. (В лесу, как известно, не меньше двух деревьев.)

На рисунках 6 и 7 приведены примеры деревьев. Как видит читатель, далеко не все они напоминают по форме дерево. Тем не менее, можно так деформировать граф на рисунке 7, что он станет полностью похож на граф с рисунка 6. Нас естественно будет интересовать вопрос о том, когда граф является деревом. Ответ на него сформулируем ниже, а сейчас укажем одно интересное свойство деревьев.

Рисунок 6. Дерево (похожее на куст)

Теорема 6. В любом дереве существует хотя бы одна вершина степени единица. (Такие вершины называют «висячими».)

Рисунок 7. Дерево (не похожее на дерево)

Теперь сформулируем теорему, являющуюся признаком дерева.

Теорема 7. Связный граф является деревом тогда и только тогда, когда количество его вершин на единицу превосходит количество ребер: %%p - q = 1%%

*Существует другая трактовка минимальности, связанная с тем, что каждому ребру графа приписано некоторое положительное число. Такое число называют весом ребра.

Одна из важных прикладных задач, относящихся к графам, это отыскание минимального остова* графа. Поясним, о чем идет речь. Пусть имеется связный граф , необходимо найти такой его подграф, который связен, содержит все вершины исходного графа, и при удалении любого ребра становится несвязным (в этом и заключено условие минимальности). Нетрудно догадаться, что такой минимальный остов является деревом.

Упражнение. Найдите три минимальных остова графа на рис.5.

Пути, циклы, связностьПланарные графы. Раскраски