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. -- Текст: электронный // Лань: электронно-библиотечная система.