Определение дерева. Теорема о связи любых его двух вершин.

Не ориентированный связанный граф, не содержащий циклов, называется деревом. Если граф не связан, а каждая его компонента дерево, то граф называется лесом. Свойства деревьев: 1)в дереве любая пара вершин соединяется единственной простой цепью. (если бы существовала не единственная цепь, то существовал бы цикл, а дерево циклов не имеет). Концевая вершина называется листом. Звездный граф – содержи только концевые ребра. 2) каждое дерево имеет по крайней мере одно концевое ребро и две концевых (висячих) вершин. 3)Теорема (о связи между вершинами и ребрами дерева): пусть имеем дерево, в котором n вершин и m ребер, тогда m=n-1. Доказательство: по индукции: для графа K2 (одно ребро и две вершины) это очевидно. Пусть теорема справедлива для любого числа вершин <n. Очевидно, каждое ребро дерева является мостом. Удалим в дереве какое-нибудь ребро, тогда получим две компоненты связности, для каждой из которых теорема справедлива: m1=n1-1, m2=n2-1, но n1+n2=n, а m=m1+m2+1. Типа, теорема доказана .

Задача о минимальном соединеии, алгоритм получения.

Задача: имеется n пунктов. Имеется стоимость строительства между каждыми пунктами. Требуется эти пункты соединить наиболее дешевой сетью. Это будет дерево. Алгоритм построения min дерева схож с алгоритмом построения оставного дерева. Только здесь нужно выбирать наиболее дешевое ребро. 1) берем любую вершину и смежное к ней самое дешевое ребро (или берем самое дешевое ребро), 2) выбираем самое дешевое ребро, смежное к полученной вершине шага 1, 3) рассматриваем все смежные ребра к вершинам пункта 2, выбирается самое дешевое и с инцидентной ему вершиной, не вошедшей в вершины пункта 2.

Планарность: оновные определения, теорема Эйлера, следствие.

Граф G называется укладываемым на поверхность S, если его можно так нарисовать на этой поверхности, что ребра будут пересекаться только в вершинах. Граф называется планарным, если его можно уложить на плоскости. Всякая укладка на плоскости называется плоским графом. Пример: полный граф К5 никогда не будет плоским. Часть пространства называетс гранью графа, если любые две внутренние точки можно соединить непрерывной линией, которая не пересекает ребер и вершин. Неограниченная часть пространства называется внешней гранью. Если взять дерево, то оно имеет только внешнюю грань. Теорема: Пусть имеем связный плоский граф, у которого n вершин, m ребер и r граней (включая внешние), то n-m+r=2 (1). Эквивалентная теорема: если не выполнимо (1), то граф не является планарным. Доказательство: пусть имеем связный плоский граф. Построим его оставное дерево. У дерева r=1, m=n-1, тогда n-m+r=n-n+1+1=2. Будем восстанавливать дерево. Очевидно, что если мы ребром соединим две концевые точки, то внешняя грань уберется, появляется внутренняя и чесло ребер увеличивается на 1. если соединим две внутренние точки, то число внутренних граней +1 и число ребер +1. Следствие: если каждая грань плоского графа ограничена простым циклом длины p, то p*(n-2)/(p-2). Доказательство: решив систему уравнений {pr=2m; n-m+r=2}, полчим данное уравнение. (стоит проверить). В качестве примера приводится граф с p=3, n=4.