Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783).
Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года [см. [5]стр. 41-42]:
«Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B , C иD – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a , b , c , d , e , f , g «.
(РИСУНОК 1.1)
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал [см. [5]стр. 102-104]:
«Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими».
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:
«Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A , B , C , D . Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать».
Хабаровский мост
... Хабаровска, не желавшей смириться с утратой первоначального облика Амурского моста, было принято решение о реконструкции моста в двухпутный железнодорожный с совмещенным автодорожным проездом, с организацией ... находившаяся в аварийном состоянии, подлежала полной замене. Кроме того, мост через Амур был единственным однопутным участком на всем протяжении двухпутной магистрали от Москвы до ...
Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.
Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.
История с мостами города Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник по математике под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.
Задача № 569 . На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A ?
(РИСУНОК 1.2)
Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров E или F , чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A .
В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.
Задача о мостах леонард эйлер и теория графов
... Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами. Задача 1 . Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и ... случае получился бы граф соседства баронств с нечетным количеством нечетных вершин. 3. Применение теории графов. Чем больше я изучала теорию графов, тем больше ...
§2. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ
Теория графов, как было сказано выше, – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.
Определение 2.01. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.
Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин ) и отрезков (ребер ), оба конца которых принадлежат заданному множеству точек (см. рис. 2.1).
(РИСУНОК 2.1)
В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B ,C ,D . Иногда граф в целом будем обозначать одной заглавной буквой.
Определение 2.02., Определение 2.03.
Обозначение: O ‘ – граф с вершинами, не имеющий ребер (рис. 2.2).
(РИСУНОК 2.2)
Определение 2.04.
Обозначение: U ‘ – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n –угольник, в котором проведены все диагонали (рис. 2.3).
(РИСУНОК 2.3)
Определение 2.05.
Обозначение: p (A ) – степень вершины A . Например, на рисунке 2.1: p (A )=2, p (B )=2, p (C )=2, p (D )=1, p (E )=1.
Определение 2.06.
На рисунке 2.4 и 2.5 изображены однородные графы второй и третьей степени.
(РИСУНОК 2.4 и 2.5)
Определение 2.07.
На рисунке 2.6 изображен исходный граф G , состоящий из четырех вершин и трех отрезков, а на рисунке 2.7 – дополнение данного графа – граф G ‘ .
(РИСУНОК 2.6 и 2.7)
Мы видим, что на рисунке 2.5 ребра AC и BD пересекаются в точке, не являющейся вершиной графа. Но бывают случаи, когда данный граф необходимо представить на плоскости в таком виде, чтобы его ребра пересекались только в вершинах (этот вопрос будет рассмотрен подробно далее, в параграфе 5).
Определение 2.08.
Например, на рисунке 2.8 показан плоский граф, изоморфный (равный) графу на рисунке 2.5. Однако, заметим, что не каждый граф является плоским, хотя обратное утверждение верно, т. е. любой плоский граф можно представить в обычном виде.
(РИСУНОК 2.8)
Определение 2.09.
Понятия плоского графа и грани графа применяется при решении задач на «правильное» раскрашивание различных карт (подробнее об этом – в §4).
Свойства ортоцентра в теоремах и задачах
... HF = FM. По теореме о произведении отрезков хорд AF ⋅ FM = BF ⋅ FC. LF - высота в прямоугольном треугольнике ∆BLC => LF = (BF ⋅ FC)1/2. Площадь треугольника равна половине произведения высоты ... окружностей β и γ, отличная от вершины треугольника O2, значит H′ совпадает с H. Таким образом, точка H является ортоцентром ∆O1O2O3 и лежит на прямой AD. 2 способ. Точки ...
Определение 2.10.
Например, на рисунке 2.9 дан граф G ‘ , на которомпроложен путь от C доH 🙁C , F ); (F , B ); (B , A ); (A , H )или (C , D ); (D , E ); (E , A ); (A , H ).
(РИСУНОК 2.9)
Определение 2.11.
Вот пример цикла, проложенного на графе G (рис. 2.9): (A , B ); (B , F ); (F , C ); (C , D ); (D , E ); (E , A ).
Определение 2.12., Определение 2.13.
Пример: на графе G (рис. 2.9) проложен простой цикл (A , B ); (B , F ); (F , C ); (C , D ); (D , E ); (E , A ) длина пути этого цикла равна 6.
Определение 2.14., Определение 2.15.
(РИСУНОК 2.10 и 2.11)
На рисунке 2.10 изображен связный граф; на рисунке 2.11 – несвязный (т. к. существует минимум одна пара несвязных вершин – A и D ).
Определение 2.16.
Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли (рис.2.12).
(РИСУНОК 2.12)
Определение 2.17.
Пример: на рисунке 2.13 изображен лес, состоящий из трех деревьев.
(РИСУНОК 2.13)
Определение 2.13.
Итак, мы рассмотрели основные определения теории графов, без которых было бы невозможно доказательство теорем, а, следовательно и решение задач. Формулировки и доказательства ключевых теорем будут приведены ниже, в этом же параграфе объяснены базовые понятия теории.
§3. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ.
Опираясь на приведенные выше определения теории графов, приведем формулировки и доказательства теорем, которые затем найдут свои приложения при решении задач.
Теорема 3.1., Доказательство
Отсюда следует: p( A 1 )+р(А2 )+ … +p(An )=0,5N, или 2(p(A1 )+р(А 2 )+ … +p(An ))=N , где N — число ребер. ‡
Теорема 3.2., Доказательство
Эта теорема имеет немало любопытных следствий.
Следствие 1., Следствие 2.
Следствие 3. Число всех людей, когда-либо пожавших руку другим людям, нечетное число раз, является четным.
Теорема 3.3., Доказательство, Теорема 3.4.
Доказательство данной теоремы мы опускаем. Остановимся лишь на некотором ее пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из n школьников, обменивается фотографиями. В некоторый момент времени выясняется, что двое совершили одинаковое число обменов. Доказать, что среди школьников есть либо один еще не начинавший обмена, либо один уже завершивший его.
Теорема 3.5. Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.
Теория предельной полезности и трудовой стоимости
... следующих задач: рассмотрение теории трудовой стоимости и ее характеристики; рассмотрение теории предельной полезности и ее характеристики; рассмотрение правомерности теории трудовой стоимости и теории предельной полезности. В ... и dU, а формула предельной полезности приобретает вид: MU=dU/dQ (1.2) Таким образом, предельная полезность равна производной от функции полезности по количеству блага. При Δ ...
Рисунок 3.1 поясняет условие теоремы. На изображенном графе все 5 простых циклов четные.
(РИСУНОК 3.1)
Суть теоремы в том, что на этом графе невозможно найти цикл (как простой, так и непростой) нечетной длины, то есть содержащий нечетное число ребер.
Теорема 3.6., Теорема 3.7.
Доказательство этой теоремы очень интересно и характерно для теории графов. Его также следует считать конструктивным (обратите внимание на то, как •использована при этом теорема 3.6).
Для доказательства к исходному графу присоединяем ребро ( А , В ); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в нем можно проложить эйлеров цикл Ψ. И если теперь в этом цикле удалить ребро (А , В ), то останется искомая цепь АВ. ‡
На этом любопытном приеме основано доказательство следующей теоремы, которую следует считать обобщением теоремы 3.7.
Теорема 3.8., Теорема 3.9.
По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли (1821—1895).
Графы-деревья издавна привлекали внимание ученых. Сегодня двоичные деревья используются не только математиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6).
Теорема 3.10., Доказательство
(РИСУНОК 3.2)
φ 1
Это число можно представить в виде суммы: Г =φ1 +φ2 +φ3 + …, где φ3 – число граней, ограниченных тремя ребрами, φ4 — число граней, ограниченных четырьмя ребрами и т. д.
С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2 Р, в то же время 2Р =20=3φ3 + 4φ4 +… . Умножив равенство Г =7=φ3 + φ4 + φ5 + … на три, получим ЗГ =21=3( φ3 + φ4 + φ5 + …).
Ясно, что (3 φ3 + 3φ4 +3φ5 +…) < (3φ3 + 4φ4 + 5φ5 + …) или 3Г <2Р , но по условию, 2Р =20, а ЗГ =21; поэтому вывод, полученный при введенном нами предположении (граф плоский), противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами не является плоским. ‡
Теорема 3.11. (Теорема Понтрягина-Куратовского)
В заключение этого параграфа, на наш взгляд, следует упомянуть то, что в нем объяснялись только основные теоремы теории графов. Их практическое применение будет рассмотрено в следующих параграфах реферата.
§4. ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ.
В данном параграфе будут рассмотрены некоторые задачи, при решении которых используется теория графов. Они считаются классическими.
Задача 4.1.
1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок;
Теория автоматического управления
... 3. Воронов А.А. Основы теорем автоматического регулирования. 41-М.-А., Энергия, 1985г. 4. Бесекерский В.А. и др. Сборник задач по теории автоматического регулирования. М, Наука, 1965г. ... экстремального значения управляемой величины, и максимального быстродействия системы управления путем подстройки её параметров, и режима работы объекта оптимального в определенном, заданном смысле. Самонастройка ...
2. учитель литературы может дать один, либо второй, либо третий урок;
3. математик готов дать либо только первый, либо только второй урок;
4. преподаватель физкультуры согласен дать только последний урок.
Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?
Решение. Без сомнения, эту задачу можно решить путем обыкновенного перебора всех возможных вариантов, но решение будет наиболее простым, если вычертить граф в виде дерева. Требуемый граф изображен на рисунке 4.1. На нем выделены три возможных варианта расписания уроков.
(РИСУНОК 4.1)
Данная задача является классическим примером удачного использования теории графов. В настоящее время существует программа «Расписание 3.0» компьютерной фирмы ЛинTex, в которой она решена с использованием современных технологий.
Рассмотрим еще одну задачу, решением которой также является граф.
Задача 4.2.
Решение . Процесс решения задачи во всех подробностях мы рассматривать не будем. Заметим только, что задать возможный вариант решения, то есть описать точный состав экспедиции, можно с помощью четного графа, в котором вершины разделены на две группы, а ребра могут соединять лишь вершины разных групп.
Применительно к задаче об экспедиции одна группа вершин есть группа из 8 кандидатов, а вторая – из 6 должностей. Решение задачи изображено на четном графе (рис 4.2).
(РИСУНОК 4.2)
Задача 4.3.
Решение. Пусть A и B – данные города. Докажем сначала, что из A в B можно было проехать до закрытия на ремонт двух дорог. Рассмотрим для этого проекцию многогранника на некоторую прямую, не перпендикулярную ни одному из его ребер (при такой проекции вершины многогранника не сливаются).
Пусть A ‘ иB ‘ – проекции точек A иB , а M ‘ и N’ – крайние точки проекции многогранника (в точки M ‘ и N’ проецируютсявершины M и N ). Если идти из вершины A так, что в проекции движение будет происходить по направлению от M ‘ к N’ , то, в конце концов, мы обязательно попадем в вершину N . Аналогично из вершины B можно пройти в N . Таким образом, можно проехать из A в B (через N ).
Если полученный путь из A иB проходит через закрытую дорогу, то есть еще два объезда по граням, для которых это ребро является общим. Вторая закрытая дорога не может находиться сразу на двух этих объездах. Значит, из города A в городB можно проехать, по крайней мере, одним путем.
Итак, в данном параграфе рассмотрены некоторые задачи, для решения которых применяется теория графов. В §5 мы приведем условия и решения задач школьного курса математики.
Теория автоматического управления и автоматизация сварочных процессов
... современным состоянием и перспективами автоматизации сварочных процессов. Предметом дисциплины является теория автоматического регулирования в сварочных процессах. Отсюда возникают и задачи курса: овладение основами автоматики ... приближении (рис.1.1.2): Y(t) - Yтр(t) = ?Y(t) min.(1.1.4) Однако в теории принятия решений отклонение ?Y(t) не всегда дает объективную оценку достаточности управления или ...
§5. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ШКОЛЬНОМ
КУРСЕ МАТЕМАТИКИ.
В соответствии с вышесказанным, в данном параграфе будут рассмотрены задачи, которые используются в школе на уроках математики.
Условно их можно классифицировать, подразделив на несколько групп:
1. Задачи о мостах.
2. Логические задачи
3. Задачи о «правильном» раскрашивании карт
4. Задачи на построение уникурсальных графов
5.
Рассмотрим несколько типичных примеров решения задач каждого вида.
Одной из наиболее известных задач о мостах является эйлерова задача; все остальные сформулированы похожим образом и решаются по тому же принципу. Поэтому в данном параграфе мы не будем подробно останавливаться разборе этого типа задач.
Основой применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Это выявление логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов.
Задача 5.1.
Решение: Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности (рис 5.1).
(РИСУНОК 5.1)
Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, также стоит «правдолюб». У нас же стоит «лжец». Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним стоит «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.
Задача 5.2.
Решение: Решение этой задачи достигается построением следующего графа (рис 5.2), где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.
(РИСУНОК 5.2)
Иными словами, суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа.
Любая географическая карта является многоугольным графом, в котором страны будут гранями, границы – ребрами, а окружающий страны Мировой океан – бесконечной гранью.
Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют «правильно» раскрашенной.
Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому вопросу уделяется большое внимание в популярной литературе, и здесь мы не будем останавливаться на его рассмотрении.
Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от бумаги являются одним из математических развлечений. При решении подобных задач необходимо помнить следующее положение. Для того, чтобы на графе имелась цепь, соединяющая АА и ВВ, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы АА и ВВ были единственными нечетными вершинами, т. е. вершинами с нечетной степенью.
Теория автоматов (2)
... функции выходов. Таким образом, на уровне абстрактной теории понятие "работа автомата" понимается как преобразование входной информации в выходную. Структурная теория автоматов изучает общие при ... высокого уровня на язык машинных кодов и задача преобразования математических выражений. 1.2.1 Абстрактный автомат Абстрактный автомат - математический объект, представляющий собой совокупность элементов: ...
§6. ПРИЛОЖЕНИЕ ТЕОРИИ ГРАФОВ В РАЗЛИЧНЫХ
ОБЛАСТЯХ НАУКИ И ТЕХНИКИ.
Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо «да», либо «нет». Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. «Опрос» завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
Графы и химия
Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:
C n H
Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Структурные формулы простейших углеводородов показаны на рисунке 6.1 (а – метан CH 4 , б – этанC 2 H 6 ).
(РИСУНОК 6.1)
Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.
Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
Графы и биология
Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.
Нас будет интересовать лишь один вопрос: в скольких случаях n -е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.
Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
Ненасыщенные (непредельные) углеводороды (алкены)
... С СН3 ½ СН2=С—СН3 (3) изобутилен Очевидно, что при большем числе углеродных атомов непредельные углеводороды изостроения также могут иметь различное положение двойной связи. Таким образом, усложнение ... теории химического строения в ненасыщенных углеводородах углерод также имеет валентность равную четырем, но строение этих соединений отличается тем, что в их молекулах имеются пары углеродных атомов, ...
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов, доказательство которой и являлось целью данного параграфа.
