Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО НАУКИ и высшего образования

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования «Кабардино-Балкарский государственный университет им. Х.М. Бербекова» (КБГУ)

ИНСТИТУТ ФИЗИКИ И МАТЕМАТИКИ

КАФЕДРА АЛГЕБРЫ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

КУРСОВАЯ РАБОТА

на тему: «Деревья в комбинаторике»

Биттирова Л.М.

Нальчик, 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 по тереме Кэли имеем 10⁸ различных деревьев, но из них только 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. Путь в каждую из них из вершины В содержит в точности один правый поворот. Число таких путей мы уже умеем находить. Оно равно . Вообще, искомое число композиций равно

3. Деревья, вероятность, генетика

Деревья полезно использовать для наглядного описания вероятностей независимых и равновозможных событий, составляющих полную группу. Дерево можно, например, построить для иллюстрации всех исходов при двукратном бросании игральной кости (рис. 2.6).

В этом случае события «выпало одно очко», «выпало два очка», «выпало три очка», «выпало четыре очка», «выпало пять очков» и «выпало шесть очков» равновозможные, несовместные и составляют полную группу. На рисунке 2.3 ярус дерева показывает номер соответствующего события:

1-й ярус -- не бросалась ни одна кость, 2-й ярус -- бросалась одна кость, 3-й ярус -- две и т. д. Сами события характеризуются ребрами, входящими в интересующий нас ярус.

Эти ребра при бросании двух костей показывают, например, все 36 равновозможных исходов. При этом ясно, что сумма вероятностей событий в каждом ярусе равна 1, а именно:

Р(1) + Р(2) + Р(3) + Р(4) + Р(5) + Р(6) =1; (1) + Р(1) * Р(2) + Р(1) Р(3) + Р(1) * Р(4) + Р(1) * Р(6) + Р(1) * Р(6) + Р(2) * Р(1) +......+ (6) = 1.

Приведем примеры использования деревьев в генетике. С помощью дерева можно наглядно представить наследование пары генов G и g, передаваемых потомку родителями. Потомок получает эти гены в одной из комбинаций: GG, gg или Gg. Генетически комбинация Gg не отличается от комбинации gG.

В генетика допускается, что наследование данного гена происходит случайно, независимо и с равными вероятностями для всех потомков (у растений, например, их может быть очень много). Пусть ген G наследуется (и от отца и от матери) с вероятностью р, ген g -- с вероятностью q. В этом случае отца в смысле унаследования гена можно уподобить, например, одной бросаемой монете, мать --второй (рис. 2.7); тогда р + q = 1.

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

Теперь от родителей перейдем к «дедушкам» и «бабушкам» и продлим дерево еще на один ярус.

Когда сочетаются браком двоюродные брат и сестра, они могут передать своему ребенку копии пар генов, которыми обладали их общие дедушка и бабушка (возможными мутациями этих генов пренебрегаем).

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

Граф, описывающий ситуацию, которая нас интересует, в случаях так называемого кровного родства деревом не является --две его висячие вершины «слипаются» (рис. 2.8).

Введем «коэффициент кровного родства» по формуле , где -- вероятность того, что оба гена С являются копиями генов G. Оказывается при этом, что вероятность нетрудно подсчитать. Рассмотрим один из генов, который С унаследовал от своего отца A. Вероятность того, что А унаследовал этот ген от своего деда D, равна . Вероятность того, что дедушка передал копию того же гена В, также равна , и вероятность того, что В передал копию этого гена С, равна . Все эти события независимые, и, следовательно,

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

Заключение

Исторически сложилось так, что теория графов зародилась именно в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания.

Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнинга в 30-е годы XX столетия.

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

Широкое применение находят графы в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.

графы комбинаторика теореме число

Литература

1. Полякова О.Р. Элементы теория графов и комбинаторики [Электронный ресурс]: учебное пособие/ Полякова О.Р.-- Электрон. текстовые данные.-- Санкт-Петербург: Санкт-Петербургский государственный архитектурно-строительный университет, ЭБС АСВ, 2017.-- 84 c.

2. Храмова Т.В. Дискретная математика. Элементы теории графов [Электронный ресурс]: учебное пособие/ Храмова Т.В.-- Электрон. текстовые данные.-- Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2014.-- 43 c

3. Князьков, В.С. Введение в теорию графов: учебное пособие / В.С. Князьков, Т.В. Волченская. -- 2-е изд. -- Москва: ИНТУИТ, 2016. -- 76 с. -- Текст: электронный // Лань: электронно-библиотечная система. --

4. Просолупов, Е.В. Курс лекций по дискретной математике: учебное пособие / Е.В. Просолупов. -- Санкт-Петербург: СПбГУ, [б. г.]. -- Часть 3: Теория алгоритмов и теория графов -- 2014. -- 84 с. -- ISBN 978-5-288-05524-9. -- Текст: электронный // Лань: электронно-библиотечная система.

5. Одинец В.П. Избранные главы теории графов [Электронный ресурс]/ Одинец В.П., Шлензак В.А.-- Электрон. текстовые данные.-- Москва, Ижевск: Регулярная и хаотическая динамика, Ижевский институт компьютерных исследований, 2009.-- 504 c.

6. Храмова Т.В. Лекции по теории графов [Электронный ресурс]: учебное пособие/ Храмова Т.В.-- Электрон. текстовые данные.-- Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2011.-- 98 c.

7. Годунова Е.К. Введение в теорию графов. Индивидуальные задания [Электронный ресурс]/ Годунова Е.К.-- Электрон. текстовые данные.-- Москва: Прометей, 2012.-- 44 c.

8. Бояринцева, Т.И. Теория графов: метод. указания: учебно-методическое пособие / Т.И. Бояринцева, А.А. Мастихина. -- Москва: МГТУ им. Н.Э. Баумана, 2014. -- 37 с. -- ISBN 978-5-7038-3994-2. -- Текст: электронный // Лань: электронно-библиотечная система.

9. Мутанов Г.М. Теория графов [Электронный ресурс]: учебное пособие для студентов математических специальностей вузов/ Мутанов Г.М., Акбердин Р.А.-- Электрон. текстовые данные.-- Алматы: Казахский национальный университет им. аль-Фараби, 2012.-- 255 c

10. Специальные разделы теории графов: учебное пособие / Л.А. Гладков, Н.В. Гладкова, В.В. Курейчик, В.М. Курейчик. -- Ростов-на-Дону: ЮФУ, 2018. -- 111 с. -- ISBN 978-5-9275-2779-3. -- Текст: электронный // Лань: электронно-библиотечная система.

Размещено на Allbest.ru