Теория графов и комбинаторика

Таотама 9.2. Граф & являетоя деревом тогда и тслъко тогда, когда он ацшипгеесккй, и при ооединении рзйром произвольных двух ноомежных вершин получается граф, имещяй ровно лчн цикл. Доказательотво этой теоремы предоставляется читателю в ка - чоотае упражкени/:. Если граф имеет остов Т , то он .чвляетоя связным, т . к . аодв^1--.аат овяэный подграф, нключагавдИ во а вершпш & . Обратно, любой овяаный граф имеет остов, Дейотвительно, воли ~ ацик­ лический, то он c a f чвляетоя ОБОИМ OCTODCM . Ееж ^ йглеот циклы, т о , последовательно удаляя ре<3ра и з циклов до получения ацшши- ч е с к с г о подграфа, получим оотов. Заметим, что удаление ребра b s цикла графа (Р не нарушает с-чзноота графа, т . к . такие pedpa HL являются тостами. Таким образом, доказана Теорема 5 . 3 . Граф & - связный тогда и только тогда, когда он имоет остов, . Читателю предаагается доказать, что любой лео, имеющий бо­ л е е одной вершины, является д»удс.';;^ным графом. Из теорем S.I и 3 . 6 следует, что дерево - это рейерго-ьрити- •Ч0О1ШЙ связный гр £ "*|, ОНО имвет HaHMeHbfflLj чиоло рейер при задан­ ном числе в е рши . Каждое рябро дерева является мсотом, 59.Й. Овивнтитюванрше деревья. Упстдиочение вет>ш11 Ориентирован!.-м деревом (корневым деревом) назтеаетоя орграф О' = С V, Г ) I удовлвтворяшций уоловижл": V '• ilTo) ^ 0 ; - корень дерева;" 2 . С P - ( U - ) = 0 ' По аналогии с §9.1 можно доказать следующую теорему. Тдстема 9 . 4 . Если G - С ^ > Г ) - ко1®едов дерево с ксрн^см •% . тс V t r e V 3 1 с т Г о - г ) - путь; '' Уровнег вершины 1Г дерева G называется дащна (Уо-^')-цути. Уровень тХо а О . асотой дерев йаанзаетоя наибольший уровень его вершин. Пусть 6 V . Если в <9 путь, тс говорят, ч т о вершина ''I продшаствует вершине ilj, ( о л е д а е т за 1Гс ). Очевидно, лвбая вершина уровня и оледует ровно за одной аершаной уровней ( " " -О, " - » • Вершине, кстсрай не предшеотвует никаким вершинам, т . е . не имеющая выходных д у г С Г с ^ ) У, иавынаатоя заключительной. 56