МИНИСТЕРСТВО НАУКИ и высшего образования
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования «Кабардино-Балкарский государственный университет им. Х.М. Бербекова» (КБГУ)
ИНСТИТУТ ФИЗИКИ И МАТЕМАТИКИ
КАФЕДРА АЛГЕБРЫ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
КУРСОВАЯ РАБОТА
на тему: «Деревья в комбинаторике»
Биттирова Л.М.
Нальчик, 2020 г.
Введение
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.
Например, Задача о Кенигсбергских мостах: обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена Эйлером в 1736 году. Задача о трех домах и трех колодцах: имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена Куратовским в 1930 году. Задача о четырех красках: любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.
Теория графов является важным разделом современной математики. Практическая ее роль особенно возросла за последнее время в связи с распространением вычислительной техники. Успех применения графов можно объяснить тем, что они являются удобным языком для формулировки и эффективным инструментом для решения задач, относящихся к широкому кругу проблем, таких, например, как теория игр, программирование, конструирование электрических и контактных цепей, задачи экономики, управления. Поэтому владение методами теории графов является необходимой составной частью образования специалистов, занимающихся вопросами высшей и прикладной математики.
В данной работе изучаются деревья, а именно использование деревьев в комбинаторике и генетике.
1. Дерево и лес
Определение. Деревом называется всякий связный граф, не имеющий циклов (рис. 1.1).
Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом.
Для каждой пары вершин дерева существует единственный соединяющий их путь.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 1.42 висячие вершины выделены закрашенными кружками).
Определение. Лесом называется несвязный граф, представляющий объединение деревьев (рис. 1.2 и 1.3).
Всякое ребро в дереве (и в лесе) является мостом. Оказывается, что в любом дереве с пятью вершинами всегда будет четыре ребра.
Из определений дерева и леса следует, что:
a) дерево не имеет кратных ребер;
b) при добавлении в дерево ребра образуются цикл;
c) при удалении ребра дерева распадается на компоненты, каждая из которых есть дерево или изолированная вершина;
d) связными компонентами леса являются деревья.
Теорема (о числе ребер дерева). Дерево с b вершинами имеет ребро.
Для того чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трех деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с b вершинами можно получить b деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить ребро из дерева Г. Итак, действительно, в дереве с b вершинами ребро.
Теорема (о висячих вершинах дерева) Дерево, содержащее две и более вершин, имеет по крайней мере, две висячие вершины.
Доказательство. Пусть граф G=(V,E) является деревом, имеющим по крайней мере две вершины. Рассмотрим на этом графе цепь максимальной длины . Покажем, что крайние вершины и этой цепи будут висячими, т.е., что им инцидентны только ребра и соответственно. Т.к. при этом рассуждения будут одинаковыми для обеих вершин, то доказательство приведем, например, только для вершины .
Допустим, что вершина не является висячей. Тогда существует некоторое ребро которое инцидентно вершине и еще некоторой вершине . Т.к. в дереве нет циклов, то не совпадает ни с одной из вершин . В таком случае получается новая цепь , имеющая длину , а это противоречит тому, что максимальная длина цепи в заданном дереве. Т.о. вершина - висячая. Ч.т.д.
Теорема Кэли (о числе помеченных деревьев). Число различных помеченных деревьев, которые можно построить на данных n вершинах равно .
Доказательство: Любому дереву T с n вершинами поставим в соответствие некоторый символ - упорядоченную последовательность n-2 номеров вершин , среди которых могут быть и повторяющиеся, где - номер вершины, выбранной первой. Это последовательность L(T) для дерева T строится следующим образом. Для множества вершин введем последовательность . Далее выбираем висячую вершину с наименьшим номером . Тогда число включается в символ L(T), после чего удаляется висячая вершина с номером вместе со связанным с ней концевым ребром. Этот процесс повторяет до тех пор, пока не будет найдены все n-2 элемента последовательности , причем через n-2 шагов от дерева T остается единственное ребро, положение которого определяется парой номеров вершин, оставшихся в последовательности. Т.о. каждому дереву T поставлена в соответствие упорядоченная последовательность , т.е. . Так определимое отображение множества помеченных деревьев с n вершинами на множестве всех символов - последовательностей будет взаимно-однозначным. Инъективность доказывается индукцией по числу вершин, а суръективность - построением дерева по его символу, восстанавливая на каждом шаге висячие вершины и концевые ребра. Т.к. в символе каждый член может принимать любые из n значений, то по формуле для числа размещений с повторениями получаем таких символов и, значит, в силу биективности отображения имеется столько же различных помеченных деревьев. Ч.т.д.
Использованная в доказательстве теоремы Кэли последовательность L(T) называется символом дерева Т или еще кодом Прюфера Т. Многие из помеченных деревьев с n вершинами являются изоморфными, т.е. отличаются только нумерацией вершин. Например, при n=10 по тереме Кэли имеем 108 различных деревьев, но из них только 106 деревьев неизоморфны.
Пример. Кубок по настольному теннису разыгрывается по олимпийской системе. Встречи проводятся без ничьих. К очередному туру допускается только победившая в предыдущем туре команда. Проигравшие выбывают из игры. Для завоевания кубка команда должна победить во всех турах.
На участие в розыгрыше кубка поданы заявки от 16 команд. Схема проведения игр изображается графом на рисунке 1.4.
Вершины нижнего «яруса» дерева (закрашенные) интерпретируем как команды, участвующие в розыгрыше кубка, вершины второго снизу яруса -- как команды-победительницы в финала, вершины третьего яруса -- как команды-победительницы в финала и т. д.
Какую информацию можно получить с помощью этого дерева? Непосредственно с него считываются:
1) число всех участников розыгрыша кубка (число закрашенных вершин);
2) число этапов проведения розыгрыша (число «ярусов» из вершин в дереве, не считая нижнего);
3) число команд, участвующих в финала, в финала, в финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);
4) число матчей, которые придется сыграть командам для выявления обладателя кубка (число незакрашенных вершин в графе). Кстати, это число легко определяется и без дерева. (В каждом матче выбывает одна команда. Для того чтобы была выявлена команда-победительница, остальные должны выбыть из соревнования. Поэтому число матчей равно числу команд без одной, а именно 15.)
2. Деревья в комбинаторике
2.1 Деревья и перестановки из n элементов
С помощью леса можно представить перестановки из n элементов множества и подсчитать их число. Для такой лес изображен на рисунке 2.1.
Всевозможные перестановки прочитываются по этой схеме от корневой до висячей вершины соответствующего дерева. Ярус показывает номер места, на котором расположен элемент. Число висячих вершин леса равно числу перестановок.
2.2 Маршруты по местности и число сочетаний
Рассмотрим подмножества множества, состоящего из пяти элементов, и подсчитаем их число. При этом записывать подмножества будем не с помощью букв, как обычно, а в виде последовательностей длиной пять, составленных из нулей и единиц. Каждая из единиц показывает на наличие в подмножестве соответствующего элемента. Например, подмножества, содержащие один элемент, будут изображаться следующими последовательностями: 10000, 01000, 00100, 00010, 00001. Пустое подмножество Ш будет соответствовать последовательности 00000. Подмножества, содержащие по два элемента из пяти, запишутся с помощью следующих последовательностей: 11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011. Всего их .
Вообще, число сочетаний из n элементов по m равно числу всевозможных последовательностей из m единиц и нулей.
После этого небольшого предисловия перейдем к подсчету числа возможных путей на рисунке 2.2 из пункта А к пунктам . Направления следования по этим путям указаны на рисунке стрелками. Один из возможных путей выделен для наглядности жирной линией. Замечаем, что все пути от A до (I =1, 2, 3, 4, 5, 6, 7) имеют одинаковую длину. Она равна наибольшему номеру яруса.
Каждому из путей поставим в однозначное соответствие «свою» последовательность из нулей и единиц. Для этого каждый поворот направо при следовании по маршруту от A до (I =1, 2, 3, 4, 5, 6, 7) будем обозначать единицей, каждый поворот налево -- нулем. Тогда, например, пути, выделенному жирной линией на рисунке 2.2, будет поставлена в соответствие последовательность «длины» шесть: 101000. Ясно, что разным путям будут соответствовать разные последовательности указанного вида. Нетрудно убедиться и в том, что рассматриваемое отображение не только однозначно, оно и взаимно однозначно. Действительно, любая последовательность рассматриваемого вида определяет единственный путь от А до некоторого , при этом разные последовательности определяют разные пути.
Попасть, например, из А в можно разными путями, но во всех случаях придется повернуть два раза вправо и два раза влево. Поэтому число путей, ведущих из А в , равно . Аналогично, число различных путей, ведущих из А в равно , из А в равно и т. д.
Число путей из А во все (I =1, 2, 3, 4, 5, 6, 7) равно
2.3 Разбиение и композиции натуральных чисел
Задачи на разбиение натуральных чисел впервые решались еще в XVII веке Г. В. Лейбницем. Родственные им задачи и сейчас занимают важное место в современной комбинаторике.
Разбиение натурального числа -- это его представление в виде суммы натуральных слагаемых. Приведем всевозможные разбиения чисел З и 4:
3 = 3, 3 = 2 + 1, 3 = 1 + 1 + 1; 4 = 4, 4 = 3 + 1, 4 = 2 + 2,
4 = 2 +1 + 1, 4 = 1 + 1 + 1 + 1.
Что же такое композиция натурального числа? Это его «разбиение» с учетом порядка расстановки слагаемых. Например, число 5 может быть представлено в виде суммы 2 + 3 или 3 + 2. Обе эти записи обозначают одно и то же разбиение, но две разные композиции. Ясно, что число композиций для данного натурального числа, вообще говоря, больше числа его разбиений. Приведем всевозможные композиции чисел З и 4:
3 = 3, 3 = 2 + 1, 3 = 1 + 2, 3 = 1 + 1 + 1, 4 = 4, 4 = 3+1, 4 = 1 + 3, 4 = 2 + 2, 4 = 2 + 1 + 1, 4 = 1 + 2 + 1, 4 = 1 + 1+2, 4 = 1 + 1 + 1 + 1.
Две композиции считаются равными только в том случае, если они состоят из одинакового числа соответственно равных слагаемых, расположенных в одинаковом порядке.
Всевозможные композиции любого натурального числа n можно представить с помощью дерева, способ построения которого должен быть ясен из рассмотрения рисунка 2.3, где изображено такое дерево для случая n = 5.
Число, которое представляется набором композиций для каждого соответствующего яруса дерева, на рисунке 2.3 выделяемся с помощью кружочка. Например, в ярусе 3 находим, следуя по вертикали сверху вниз, всевозможные композиции числа 3 в определенной очередности: 1 + 1 + 1, 1 + 2 и т. д. Число композиций при переходе от яруса k к ярусу k + 1, как это видно, например, из рисунка 2.3, удваивается (в каждую вершину входит одно ребро, а выходят в следующий ярус два), а при k = 1 оно равно единице. Поэтому число композиций для произвольного яруса k равно .
Вернемся теперь к графам того «типа», пример которого был изображен на рисунке 2.2. Подвергнем такой граф «операции расслоения». Станем «раздваивать» вершины, в которые входят по два ребра (рис. 2.3).
Нетрудно заметить, что «расслоенный» граф представляет собой дерево, «устроенное» в точности так, как дерево, изображенное на рисунке 2.3 (если не принимать во внимание крайней слева вершины и ребра, которому она принадлежит). В каждую вершину графа (кроме корневой) на рисунке 2.4(б) входит одно ребро, из каждой (кроме висячих) выходят по два ребра.
Спрашивается, как осуществить над деревом, изображенным на рисунке 2.4(б), операцию, обратную операции расслоения, чтобы при этом вновь получился граф, изображенный на рисунке 2.4(а).
Для этого нужно слить между собой те вершины дерева, изображенного на рисунке 2.4(б), для попадания в которые при следовании из корневой его вершины в висячие приходится сделать одинаковое число правых поворотов.
Поставим теперь следующий вопрос. Сколько композиций, насчитывающих слагаемых, может содержать данное натуральное число n? Имеем в виду, что композиции данного натурального числа могут отличаться количеством слагаемых. Чтобы ответить на этот вопрос, можно осуществить для дерева, представленного на рисунке 2.3, операцию, обратную операции расслоения (она не имеет смысла только для крайней слева вершины и ребра, которому она принадлежит). Это же дерево с более удобными для описания такой операции обозначениями изображено на рисунке 2.5. При этом, очевидно, сольются вершины G, K, N и S. Путь в каждую из них из вершины В содержит в точности один правый поворот. Число таких путей мы уже умеем находить. Оно равно . Вообще, искомое число композиций равно