Спирина, М.С. Дискретная математика

0 -й ярус —- 3-й ярус • 2 -й ярус 4 -й ярус 1-й ярус Уи Уп У\8 У 19 V20 Рис. 2.14. Иллюстрация графа-дерева распадается на два подграфа. В одном из них остается корневая вершина, и этот граф G, тоже будет являться деревом. В другом графе G\ выделим вершину, инцидентную удаленному мосту. Тог­ да второй подграф также будет являться деревом. Если в исходном графе вершина F принадлежала у-му ярусу, а дерево «обрубили» по ребру, соединявшему вершины t -го и ( / - 1)-го ярусов, причем s > t, то тогда В_частности, если s= t и F е Gu то вершина / ’будет корневой для G] и s' (F) =s - t= 0. Если s < t, то вершина заведомо принадле­ жит подграфу Gx. Наиболее характерные свойства деревьев, которые одновремен­ но служат эквивалентными определениями дерева, сформулиру­ ем в следующей теореме. Теорема 2.7. Граф G(V, X) (\V\ =n> 7) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий : граф G( V, X) связен и не содержит циклов', граф G( V, X) не содержит циклов и имеет п - 1ребро', граф G( V, X) связен и имеет п - 1 ребро', граф G{ V, X) не содержит циклов, но добавление ребра между несмежными вершинами приводит к появлению одного и только од­ ного элементарного цикла', граф G{ V, X) связный, но утрачивает это свойство после удале­ ния любого ребра ', в графе G( V, X) всякая пара вершин соединена цепью, и только одной. Итак, дерево с п вершинами имеет п - 1 ребро, поэтому оно будет минимальным связным графом. Висячие вершины, за ис - 4 Дискретная математика 81