Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
ГЛ. 2. СЕТИ
229
аі\ образами корпит щ из ЙЛі и Ж будут либо изолировап-ные вершины (іі (если символ а і встречается один раз и только в одном наборе), либо связная компонента Л% — в остальных случаях; образами наборов (і^і) будут круги (соответственно вершины, дуги).
Можно показать, что для каждой счетной сети существует геометрическая реализация.
Пример 2. Построив геометрическую реализацию сети из примера 1, мы получим фигуру, изображенную на рис. 2.
Данная фигура напоминает схему радиоприемника, из которой удалены все элементы; лампы, емкости, индуктивности и т. п.
Определение. Сети Ж {е'0\ Е[1 Е'^ ? > ?) и (Е0;
Е[, Е1, ...) называются изоморфными, если можно установить взаимно однозначное соответствие между объектами множеств Ж л ?01", а также между объектами из наборов 91' и ЭН' так, что;
1) соответствующие наборы Ег и Е" состоят из соответствующих объектов (с учетом кратности их вхождений) ;
2) наборы Е0 и Е0 соответствуют друг другу.
Очевидно, что абстрактная сеть изоморфна своей геометрической реализации. Поскольку нас будут интересовать сети с точностью до изоморфизма, то вместо абстрактных сетей можно рассматривать их геометрические реализации. В этом смысле сети представляют собой геометрические объекты.
Рассмотрим теперь некоторые классы сетей.
230 ч. III. ГРАФЫ И СЕТИ
Очевидно, что класс сетей, у которых Е0 — А и каждый набор (1^1) состоит из двух объектов множества ?01, совпадает с классом графов.
Другой класс сетей дают так называемые деревья. Деревом называется конечный связный граф с выделен-
Ъв
Рис, 3
ной вершиной, именуемой корпем, не содержащий циклов.
Очевидно, что дерево — однополюсная сеть, т. е. Ей={а).
Приведем другое определение дерева, эквивалентное первому и основанное на индукции. Проще всего воспользоваться определением в геометрической форме.
I
Рис. 6
изображенная на
Индуктивный переход. Пусть А (рис. 4, а) — дерево с корнем а и В {рис. 4, б) — дерево с корнем Ь.
Тогда фигура С {рис. 5, а), полученная из А «подключением» к корню а нового ребра, будет деревом с корнем с. Далее, фигура В (рис. 5, б), нолученная из А и В путем объединения корней, будет деревом с корнем с, где с = а = Ь.
Легко видеть, что это индуктивное определение дерева можно сформулировать и в терминах абстрактной сети.
Рис. 5
Базис индукции. Фигура, рис. 3, является деревом с корнем а.
ГЛ. 2. СЕТИ
231
Базис индукции. Сеть Щ?0; ?1), где = {а, яЛ, Ео =(а), Е, = (а, щ), является деревом с корнем а.
Индуктивный переход. Пусть А = ЭИХ (^о; Е'и ...) и В =2Л3 (Е1; Е[, .. .)являются деревьями с корнями а и Ь, где 2^1 П ЗИ2 = Л, Е0 = (а) и ?0 = (Ь). Тогда сеть С=$1(?0; Е, Е'и ...)является деревом с корнем с, если
аП = ЗП111{с>, ?„ = (с), ? = (а, с),
где с — новый объект.
Далее, сеть О =?= 21?' (?70; Е\, ..., Е\, .,является деревом с корнем в вершине с, если
аЯ'«(а»1\а)и(2ДЛб)и{с}) ?0 = (с)
и пабор ?* (соответственно ?"1) получается из набора ?*(?|) заменой всех вхождений символа а(&) на с, где с — новый объект.
Геометрическое определение дерева позволяет осуществить его геометрическую реализацию на плоскости.
Плоскую геометрическую реализацию дерева, в которой ребра представляют отрезки прямых, а корень изображен вершиной с дополнительным отрезком — стрелкой (см. рис. 6), будем называть укладкой дерева.
Пример 3. Пусть
2? - (0, 1,* 2, ..., 10), 21 = {?„; Е1 ?„},
где
?„ = (0), ?,=(0,1), ?3 = (0,2), ?, = (0,3),
?* = (1,4), ?5 = (1, 5), ?« = (1/6), ?х = (3, 7)\
?* = (3, 8) , ?,=(4,9), ?ю = (4, 10).
232
Ч. III. ГРАФЫ И СЕТИ
Очевидно, что ЙЯ(Е',у, Еи ..., Е10)—дерево. На рис. 7 изображено несколько укладок данного дерева.
Рассмотрим произвольную укладку дерева. Если двигаться по дереву от корня к концевым вершинам, то можно осуществить ориентацию ребер дерева. При этом в каждую вершину (включая корень) входит
Ж некоторое ребро и из каждой вершины, кроме концевых, исходит несколько ребер. Данное обстоятельство позволяет упорядочить исходящие ребра в каждой вершине, например, в порядке их следования,- двигаясь от входящего ребра (см. рис. 8) по часовой стрелке.
Гис. 8 Естествеппо считать, что две укладки одно-
' го дерева одинаковы, если порядки следования исходящих ребер для соответствующих вершин совпадают. Таким образом, укладка дерева полностью определяется порядками следования исходящих ребер.
§ 2. Оценка числа сетей
Мы начнем с рассмотрения простой задачи. Обозначим через 6(Н) максимальное число попарно неизоморфных деревьев с к ребрами, а через б* (Ь)—число укладок деревьев из соответствующего множества.
Теорема 4. б(й)<6*(Л)<4Л.
Доказательство. Так как укладки для неизо-морфиых деревьев различны, то б(/г) 6* (Л).
Каждой укладке дерева с к ребрами можно сопоставить взаимно однозначным образом кортеж из 0 и 1 длины 2/к Для этого воспользуемся индуктивным определением дерева.
Базис индукции. Укладке дерева, содержащего ровно одно ребро* отнесем кортеж ОТ Его длнна равна 2.
Индуктивный переход. Пусть укладкам деревьев А и В, имеющих срответственно кл и к% ребер, сопоставлены кортежи а и р длины 2^1 и 2к2, Тогда укладке дерева С, полученной из укладки дерева А путем подключения ребра, сопоставим кортеж 0а4. Его длина равна 2(^+1), т. е. удвоенному числу ребер дерева А. Далее, укладке дерева В, полученной из укладок деревьев А -в. В путем объединения корней, сопоставим ар или Ра в зависимости от порядка их следования. Каждый из кортежей имеет длипу 2(/>1 + Ьг), т. с. равную удвоенному числу ребер дерева В,
