Множества. Комбинаторика. Отношения (стр. 24 )

>. <

Лемма 2. .

Доказательство. . <

ТЕОРЕМА. Пусть – число всех попарно неизоморфных графов с h рёбрами без изолированных вершин. Тогда <.

Доказательство. Граф с h рёбрами имеет не более 2 вершин. Занумеруем вершины графа числами 1,2, …. Число пар вершин, которые могут связываться рёбрами, не превосходит величины

.

Из r рёбер графа с h рёбрами можно построить не более графов, т. е.

<

<. <

Упражнения

Докажите, что:

1) число всех n – вершинных графов с перенумерованными вершинами равно 2;

2) число всех n – вершинных графов с перенумерованными вершинами без изолированных вершин равно .

Указание. В задаче 2) использовать принцип включения и исключения.

3.1.11.Деревья

Граф без циклов называется лесом. Связный граф, не содержащий простых циклов, называется деревом.

ТЕОРЕМА. Граф является деревом = между любыми двумя его различными вершинами существует единственная цепь.

Доказательство очевидно. <

ТЕОРЕМА. Связный граф является деревом , число вершин в нём на единицу больше числа рёбер.

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

Пусть в связном графе n вершин и h рёбер, причём. N=k-1. Если в графе есть циклы, то из каждого цикла удаляем по одному ребру. В результате получим остовное дерево, в котором число вершин n, а рёбер , где s–число удалённых рёбер. Из необходимой части теоремы , т. е. исходный граф не имеет циклов. <

Число называется цикломатическим числом связного графа с n вершинами и h рёбрами.

Следствие. Связный граф является деревом , его цикломатическое число равно нулю.

Упражнение

1) Перечислить все восьмивершинные деревья (23).

3.1.12 Корневое дерево

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

Базис индукции. Фигура рис.1 является деревом с корнем а.

Гипотеза индукции. Пусть А – дерево с корнем а, В – дерево с корнем в (рис. 2).

Индуктивный переход. Тогда фигура С, полученная подключением к корню нового ребра (рис.3 а), тоже дерево. Фигура Д, полученная из А и В отождествлением их корней, – тоже дерево (рис.3 б). Других деревьев нет.

Плоскую геометрическую реализацию дерева, в которой рёбра представляют отрезки прямых, а корень изображён вершиной со стрелкой, будем называть укладкой дерева. Стрелка указывает на то, что плоское корневое дерево изображается на плоскости с разрезом, представляющим собой полупрямую, исходящую из корня. Тем самым можно считать заданным направление подсчёта рёбер в ярусах слева направо.

Каждому плоскому корневому дереву с h рёбрами можно однозначно сопоставить двоичный вектор длины 2h, называемый кодом дерева. Дереву с одним ребром сопоставим вектор 01. Если деревьям А и В (рис.2) сопоставлены коды и , то дереву С, полученному подключением ребра, – код 01, дереву Д, полученному отождествлением корней, – код .

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

ТЕОРЕМА. <.

Доказательство. Число укладок равно числу кодов длины 2h, поэтому меньше числа кортежей длины 2h из нулей и единиц, в которых нулей и единиц поровну, а оно меньше числа размещений с повторениями из 2 по 2h. Отсюда

<< <

Упражнение

1) Перечислить все четырехреберные:

а) корневые деревья; б) укладки корневых деревьев.

Задача. По заданному коду 001010011011 построить плоское корневое дерево.

Решение. Двигаемся от корня каждый раз по новому ребру, если в коде встретится 0, вправо от уже построенных рёбер, и, возвращаясь по ребру, в случае, если в коде встретили 1.

3.2 Сети

3.2.1 Сильно связные сети

В дальнейшем под словом сеть будем подразумевать двухполюсную сеть. Сеть называется связной, если соответствующий граф связный. Вместо слов “цепь, соединяющая полюса” будем говорить “цепь”. Связная цепь называется сильно связной, если через каждое её ребро проходит цепь.

Лемма. Пусть Г=Г(а, в) – произвольная сеть с полюсами а и в и пусть через вершины и сети Г проходят цепи. Если вершины и можно соединить маршрутом, то существует цепь, проходящая через и .