Cтраница 2
Выполнив ЧН на / - 1 листьях, находим, что / - и лист каждого подставляемого дерева теперь имеет отца, отличного от отца 1-го листа любого другого подставляемого дерева. Множество таких отцов обозначим через F. Если мы смогли выполнить операции ЧН длины с - 1 на этих отцах, то можем выполнить ЧН длины с на листьях. Множество, оставшееся от S, можно, следовательно, рассматривать как произвольное дерево с 2 ( 1 / 2 листьями, которые принадлежат F. По предположению индукции для с и / неравенство (4.5) справедливо. [16]
Ребро с концами A -, Bj обозначается AfBj. Путь графа, в к-ром начальная и конечная вершины совпадают, а остальные вершины различны. С не существует связного подграфа, содержащего Н и с ним: ie совпадающего. Важными хар-ками графа являются числа Лос - 1 - ранг графа i дг al - R - число связности графа. Число связности N совпадает с минимальным шелом независимых контуров графа, порож-ающпх любой его контур. Число связности произвольного дерева равно нулю. [17]
Ребро с концами A /, Bj обозначается Aflj. Путь графа, в к-ром начальная и конечная вершины совпадают, а остальные вершины различны. G не существует связного подграфа, содержащего Я и с ним не совпадающего. Связный граф, не содержащий ни одного контура, наз. G может быть представлен в виде их объединения. Важными хар-ками графа являются числа Яа - 1 - ранг графа и N a - R - число связности графа. V совпадает с минимальным числом независимых контуров графа, порождающих любой его контур. Число связности произвольного дерева равно нулю. [18]