Дискретная математика

143 На рис. 5.20, в) приведены всевозможные (непомеченные) деревья с четырьмя вершинами и на рис. 5.20, г) с пятью вершинами. Теорема 5.10, В дереве любые две вершины соединены единственной простой цепью. Доказательство. Существование цепи следует из связности графа. Если бы было две цепи, соединяющих заданные вершины, то получили бы цикл, а в дереве нет циклов. Теорема 5.11. Число ребер у дерева с п вершинами равно и-1. Доказательство проведем индукцией. Для графа с двумя вершинами - очевидно. Предположим, наше утверждение верно для графов, имеющих меньше чем к вершин. Докажем для графа с к вершинами. Удаление любого ребра из дерева G делают G несвязным. Так как мы разрываем связь только между двумя вершинами, то получаемый граф будет иметь в точности две компоненты. Положим, что получили компоненты О/ и О.л Пусть в G/ имеется hi вершин, & ъ G2 - вершин; при этом к} + кз = к. По предположению индукции в каждой компоненте число ребер ровно на единицу меньше числа вершин, т.е. mj= к; -1, к2-1. Таким образом, общее число ребер в G будет mj+ т2+\ = к] -1 + Ь ~ к -\. Следовательно, утверждение верно и для графа с к вершинами и, по методу математической индукции, теорема доказана. Теорема 5.12. Число различных помеченных деревьев, которые можно построить на п вершинах, равно п"'~. Без доказательства. Очевидно, что это число деревьев при больших значениях п велико, например если п=10, то число различных деревьев равно Л'=10'*=100 ООО ООО. Теорема 5.13. В любом нетривиальном дереве имеются, по крайней две висячие вершины. Доказательство. Рассмотрим дерево G(V,)0. Дерево - связный граф, следовательно, для любой v,, v, sV, её локальная степень больше или равна единице: degiv;) > 1. Далее от противного. Пусть для любой v „ v, eV, имеет место; deg (vi) >