Дополнение. Деревья

1 2 3 4 5

Рис 6. Связные и несвязные графы.

Рис 5. Стандартные неплоские графы.

Рис 4. Редукция графов.

Рис 3. Плоский граф.

Утверждение 3. Композиция изоморфизмов и обратное изоморфизму отображение сами являются изоморфизмами.

Теорема 2. Следующие величины и свойства являются инвариантами графа , то есть сохраняются при изоморфизмах:

1). - числовершин графа;

2). - числоребер и дуг графа;

3). - число дуг графа;

4). - числоребер графа;

5). - числоциклов в графе;

6). - числоконтуров в графе;

7). - числопетель в графе;

8). - числолистьев в графе;

9). - числовершин графа степени ;

10). - числовершин графа полустепени захода ;

11). - числовершин графа полустепени исхода ;

12). Связность графа;

13). Эйлеровость, гамильтоновость и планарность графа;

Определение 27. Редукцией графа называется «стирание» вершины степени .

редукция

Утверждение 4. Если редуцированный граф не плоский, то и сам граф неплоский.

Утверждение 5. Если подграф не плоский, то и сам граф неплоский.

Теорема 3. Граф не является плоским тогда и только тогда, когда с помощью операций перехода к подграфу и редукции он сводится к одному из двух стандартных неплоских графов .

Определение 28. Граф называется двудольным, если множество его вершин можно разбить на два таких непересекающихся множества (доли), что и (где - пустое множество), причем – смежные только, если , а или наоборот . Если при этом каждая вершина множества соединена с каждой вершиной множества , то двудольный граф называется полным двудольным графом.

Граф – полный двудольный, а - просто полный.

Определение 29. Граф называется связным, если любые две вершины можно соединить некоторой цепью.

Связный Несвязный.

Определение 30. Связная компонента графа - это максимальный связный подграф.

Рис 7.

– связные компоненты.

Теорема 4. Каждая вершина графа содержится в некоторой связной компоненте.

Доказательство. Возьмем вершину графа и все вершины, с которыми данную вершину можно соединить цепью. Получим часть графа, которая и будет компонентой.

Определение 31. Сетью называется связный ориентированный граф без петель и циклов.

Вершины с полустепенью захода , называются входами, и с полустепенью исхода , называются выходами.

Определение 32. Говорят, что дуга направлена от входа к выходу, если она лежит на некотором пути от некоторого входа к некоторому выходу.

Теорема 5. Каждая сеть содержит как входы, так и выходы, причем каждая дуга сети ориентирована от входа к выходу.

Доказательство. Пусть - вершина сети. Либо - выход, либо существует такая вершина и дуга , что . Либо - выход, либо существует такая вершина и дуга , что , и т.д. В силу конечности графа получаем конечную цепочку вершин , которая обрывается на вершине , являющейся, очевидно, выходом. Аналогично доказывается существование хотя бы одного входа сети. Если - дуга сети, то от начинается цепь, заканчивающаяся выходом и в заканчивается некоторая цепь, начинающаяся на входе. Таким образом, соединяя обе цепи дугой получаем цепь от входа к выходу, содержащую . Теорема доказана.

Определение 33. Деревом называется связный неориентированный граф без петель и циклов (в котором выделена одна вершина, называемая корнем дерева).

Теорема 6. Пусть - связный неориентированный граф с выделенной вершиной. Тогда следующие свойства эквивалентны:

1). - дерево;

2). В графе нет простых циклов (в частности петль);

3). Любые две вершины графа связаны единственной простой цепью;

4). Число ребер на 1 меньше числа вершин: = - числовершин графа.

Определение 34. Уровень корня по определению равен нулю. Число ребер цепи, соединяющей вершину с корнем называется уровнем вершины. Высотой дерева называется максимальный уровень его вершин.

Замечание. Деревья часто рисуют корнем вверх, поэтому вместо высоты дерева говорят о его глубине.