ВЛАДИМИРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙУНИВЕРСИТЕТ
РЕФЕРАТ
«ТЕОРИЯ ГРАФОВ»
Выполнила:
Зудина Т.В.
Владимир 2001
СОДЕРЖАНИЕ:
1. Введение
2. История возникновения теории графов
3. Основные определения теории графов
4. Основные теоремы теории графов
5. Задачи на применение теории графов
6. Применение теории графов в школьном курсе математики
7. Приложение теории графов в различных областях науки итехники
8. Последние достижения теории графов
9. Вывод
§1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.
Родоначальником теории графов принятосчитать математика Леонарда Эйлера (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), из современныхматематиков – К. Берж, О. Оре, А. Зыков.
§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. Граф, степени всех k вершин которого одинаковы, называется однороднымграфомстепениk.
На рисунке 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).
Определение 2.10. Путемот AдоXназывается последовательность ребер, ведущая от A к X,такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро невстречается более одного раза.
Например, на рисунке 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. Две вершины AиBвграфе называются связными(несвязными), если в немсуществует (не существует) путь, ведущий из Aв B.
Определение 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. Дерево, все n вершин которого имеют номера от 1 до n,называют деревом с перенумерованными вершинами.
Итак, мы рассмотрели основные определения теорииграфов, без которых было бы невозможно доказательство теорем, а, следовательнои решение задач. Формулировки и доказательства ключевых теорем будут приведеныниже, в этом же параграфе объяснены базовые понятия теории.
§3. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ.
Опираясь на приведенные выше определения теорииграфов, приведем формулировки и доказательства теорем, которые затем найдутсвои приложения при решении задач.
Теорема 3.1. Удвоенная сумма степеней вершин любого графа равна числу его ребер.
Доказательство.Пусть А1,А2,А3, ...,An— вершиныданного графа, a p(A1), р(А2), ..., p(An) – степени этих вершин. Подсчитаем число ребер, сходящихсяв каждой вершине, и просуммируем эти числа. Это равносильно нахождению суммыстепеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оноведь всегда соединяет две вершины).
Отсюда следует: p(A1)+р(А2)+… +p(An)=0,5N,или 2(p(A1)+р(А2)+… +p(An))=N, где N — числоребер.
Теорема 3.2. Числонечетных вершин любого графа четно.
Доказательство.Пусть a1, a2, a3, …, ak — это степени четных вершин графа, а b1, b2, b3, …, bm—степенинечетных вершин графа. Сумма a1+a2+a3+…+ak+b1+b2+b3+…+bmровно в два раза превышает число ребер графа.Сумма a1+a2+a3+…+akчетная (как сумма четных чисел), тогда сумма b1+b2+b3+…+bm должна быть четной. Это возможно лишь в том случае,если m — четное, то есть четным является и число нечетныхвершин графа. Что и требовалось доказать.
Этатеорема имеет немало любопытных следствий.
Следствие 1. Нечетное число знакомых в любойкомпании всегда четно.
Следствие 2. Число вершин многогранника, в которых сходитсянечетное число ребер, четно.
Следствие 3. Число всех людей, когда-либо пожавших руку другим людям, нечетноечисло раз, является четным.
Теорема 3.3. Во всяком графе с nвершинами, где nбольше илиравно 2, всегда найдутся две или более вершины с одинаковыми степенями.
Доказательство.Если граф имеет nвершин,то каждая из них может иметь степень 0, 1, 2, ..., (n-1). Предположим, что в некотором графе все его вершиныимеют различную степень, то есть, и покажем, что этого быть не может.Действительно, если р(А)=0, то это значит, что А —изолированная вершина, и поэтому в графе не найдется вершины Х состепенью р(Х)=n-1. В самом деле, эта вершина должна бытьсоединена с (n-1)вершиной, в том числе и с А, но ведь А оказалась изолированной.Следовательно, в графе, имеющем n вершин, не могут быть одновременно вершины степени 0и (n-1). Это значит, что из nвершин найдутся две, имеющие одинаковые степени.
Теорема 3.4. Если в графе с nвершинами (nбольше илиравно 2) только одна пара имеет одинаковую степень, то в этом графе всегданайдется либо единственная изолированная вершина, либо единственная вершина,соединенная со всеми другими.
Доказательство данной теоремы мы опускаем. Остановимсялишь на некотором ее пояснении. Содержание этой теоремы хорошо разъясняетсязадачей: группа, состоящая из nшкольников,обменивается фотографиями. В некоторый момент времени выясняется, что двоесовершили одинаковое число обменов. Доказать, что среди школьников есть либоодин еще не начинавший обмена, либо один уже завершивший его.
Теорема3.5. Если у графа все простые циклы четной длины, то он не содержит ниодного цикла четной длины.
Рисунок 3.1 поясняет условие теоремы. Наизображенном графе все 5 простых циклов четные.
(РИСУНОК3.1)
Суть теоремы втом, что на этом графе невозможно найти цикл (как простой, так и непростой)нечетной длины, то есть содержащий нечетное число ребер.
Теорема 3.6. Для того, чтобы граф был эйлеровым, необходимо и достаточно,чтобы он был связным и все его вершины имели четную степень.
Теорема 3.7. Для того чтобы на связном графе можно было бы проложитьцепь АВ, содержащую все его ребра в точности по одному разу, необходимои достаточно, чтобы А иВ были единственными нечетными вершинамиэтого графа.
Доказательство этой теоремы оченьинтересно и характерно для теории графов. Его также следует считатьконструктивным (обратите внимание на то, как •использована при этом теорема3.6). Для доказательства к исходному графу присоединяем ребро (А, В);после этого все вершины графа станут четными. Этот новый граф удовлетворяетвсем условиям теоремы 3.6, и поэтому в нем можно проложить эйлеров цикл Ψ.И если теперь в этом цикле удалить ребро (А, В), тоостанется искомая цепь АВ.
На этом любопытном приеме основано доказательствоследующей теоремы, которую следует считать обобщением теоремы 3.7.
Теорема 3.8. Если данный граф является связным и имеет 2kвершин нечетной степени, то в нем можно провести k различных цепей,содержащих все его ребра в совокупности ровно по одному разу.
Теорема 3.9. Различных деревьев с nперенумерованными вершинами можно построить nn-2.
По поводу доказательства этой теоремы сделаем однозамечание. Эта теорема известна, в основном, как вывод английского математикаА. Кэли (1821—1895). Графы-деревья издавна привлекали внимание ученых. Сегоднядвоичные деревья используются не только математиками, а и биологами, химиками,физиками и инженерами (подробнее об этом – в параграфе 6).
Теорема 3.10. Полныйграф с пятью вершинами не является плоским.
Доказательство.Воспользуемся формулой Эйлера: В-Р+Г=2, где В — числовершин плоского графа, Р — число его ребер, Г — число граней.Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольниковне лежит внутри другого. На рисунке 3.2, а изображен граф, к которому формулане применима — заштрихованный многоугольник находится внутри другого. Справаприведено изображение графа, к которому формула применима.
(РИСУНОК3.2)
Эту формулу можно доказать методом математическойиндукции. Это доказательство мы опускаем. Заметим только, что формуласправедлива и для пространственных многогранников. Пусть все пять вершин графасоединены друг с другом (рис. 3.2). Замечаем, что на графе нет ни одной грани,ограниченной только двумя ребрами. Если через φ1обозначитьчисло таких граней, то φ2=0. Далее рассуждаем отпротивного, а именно: предположим, что исследуемый граф плоский. Это значит,что для него верна формула Эйлера. Число вершин в данном графе В=5,число ребер Р=10, тогда число граней Г=2-В+Р=2-5+10=7.
Это число можно представить в виде суммы: Г=φ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+4φ4+ 5φ5+…)или 3ГР, но по условию, 2Р=20, а ЗГ=21;поэтому вывод, полученный при введенном нами предположении (граф плоский),противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами неявляется плоским.
Теорема 3.11. (ТеоремаПонтрягина-Куратовского) Графявляется плоским тогда и только тогда, когда он не имеет в качестве подграфаполного графа с пятью вершинами.
Взаключение этого параграфа, на наш взгляд, следует упомянуть то, что в немобъяснялись только основные теоремы теории графов. Их практическое применениебудет рассмотрено в следующих параграфах реферата.
§4. ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ.
В данном параграфе будут рассмотрены некоторыезадачи, при решении которых используется теория графов. Они считаютсяклассическими.
Задача 4.1. Необходимо составить фрагмент расписания для одногодня с учетом следующих обстоятельств:
1. учитель истории может дать либопервый, либо второй, либо третий уроки, но только один урок;
2. учитель литературы может датьодин, либо второй, либо третий урок;
3. математик готов дать либо толькопервый, либо только второй урок;
4. преподаватель физкультуры согласендать только последний урок.
Сколько и каких вариантов расписания, удовлетворяющеговсем вышеперечисленным условиям одновременно, может составить завуч школы?
Решение. Безсомнения, эту задачу можно решить путем обыкновенного перебора всех возможныхвариантов, но решение будет наиболее простым, если вычертить граф в видедерева. Требуемый граф изображен на рисунке 4.1. На нем выделены три возможныхварианта расписания уроков.
(РИСУНОК 4.1)
Данная задача является классическим примером удачногоиспользования теории графов. В настоящее время существует программа«Расписание 3.0» компьютерной фирмы ЛинTex, в которойона решена с использованием современных технологий.
Рассмотрим еще одну задачу, решением которой такжеявляется граф.
Задача 4.2. В составе экспедиции должно быть 6 специалистов:биолог, врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, изкоторых и нужно выбрать участников экспедиции; условные имена претендентов: A,B, C, D, E, F, Gи H.Обязанности биолога могут исполнять EиG, врача – AиD,синоптика – FиG, гидролога – B иF,радиста – С иD,механика – CиH. Предусмотрено, что в экспедиции каждый из них будетвыполнять только одну обязанность. Кого и в какой должности следует включить всостав экспедицию, если Fнеможет ехать без B,D– без HиC, Cне может ехать вместе с G, A– вместе с B?
Решение.Процесс решения задачи во всех подробностях мы рассматривать не будем. Заметимтолько, что задать возможный вариант решения, то есть описать точный составэкспедиции, можно с помощью четного графа, в котором вершины разделены на двегруппы, а ребра могут соединять лишь вершины разных групп.
Применительно к задаче об экспедиции одна группавершин есть группа из 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 мыприведем условия и решения задач школьного курса математики.
§5. ПРИМЕНЕНИЕ ТЕОРИИГРАФОВ В ШКОЛЬНОМ
КУРСЕ МАТЕМАТИКИ.
В соответствии с вышесказанным, в данном параграфебудут рассмотрены задачи, которые используются в школе на уроках математики.
Условно их можно классифицировать, подразделив нанесколько групп:
1. Задачи о мостах.
2. Логические задачи
3. Задачи о «правильном»раскрашивании карт
4. Задачи на построение уникурсальныхграфов
5.
Рассмотрим несколько типичных примеров решения задачкаждого вида.
Одной из наиболее известных задач о мостах являетсяэйлерова задача; все остальные сформулированы похожим образом и решаются потому же принципу. Поэтому в данном параграфе мы не будем подробно останавливатьсяразборе этого типа задач.
Основой применения графов для решения логических задачслужит выявление и последовательное исключение возможностей, заданных вусловии. Это выявление логических возможностей часто может быть истолковано спомощью построения и рассмотрения соответствующих графов.
Задача 5.1. Изтрех человек, стоящих рядом, один всегда говорит правду (правдолюб), другойвсегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду,либо ложь (дипломат). У стоящего слева спросили: «Кто стоит рядом с тобой?».Он ответил: «Правдолюб». Стоящему в центре задали вопрос: «Ктоты?», и он ответил: «Я дипломат». Когда у стоящего справаспросили: «Кто стоит рядом с тобой?», он сказал: «Лжец».Кто где стоял?
Решение:Если в данной задаче ребро графа будет соответствовать месту, занимаемому темили иным человеком, то нам могут представиться следующие возможности (рис 5.1).
(РИСУНОК 5.1)
Рассмотрим первую возможность. Если«правдолюб» стоит слева, то рядом с ним, судя по его ответу, такжестоит «правдолюб». У нас же стоит «лжец». Следовательно,эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом всеостальные возможности, мы придем к выводу, что позиция «дипломат»,«лжец», «правдолюб» удовлетворяет задаче. Действительно,если «правдолюб» стоит справа, то, по его ответу, рядом с ним стоит«лжец», что выполняется. Стоящий в центре заявляет, что он«дипломат», и, следовательно, лжет (что возможно из условия), астоящий справа также лжет. Таким образом, все условия задачи выполнены.
Задача 5.2.В обеденный перерыв члены строительной бригады разговорились о том, кто сколькогазет читает. Выяснилось, что каждый выписывает и читает две и только двегазеты, каждую газету читает пять человек, и любая комбинация читается однимчеловеком. Сколько различных газет выписывают члены бригады? Сколько человек вбригаде?
Решение:Решение этой задачи достигается построением следующего графа (рис 5.2), гдекаждая вершина обозначает соответствующую газету и соответственно 5подписчиков, а каждое ребро будет соответствовать одному подписчику.
(РИСУНОК 5.2)
Иными словами, суть метода решения этой и подобных ейзадач состоит в установлении связей между множеством вершин и множеством реберграфа.
Любая географическая карта является многоугольнымграфом, в котором страны будут гранями, границы – ребрами, а окружающий страныМировой океан – бесконечной гранью.
Для лучшего зрительного восприятия необходимо, чтобыстраны с общей границей были раскрашены в разные цвета. Такую карту называют«правильно» раскрашенной.
Широко известное предположение состоит в том, чтокаждая карта может быть раскрашена с соблюдением требуемых условий при помощичетырех красок. Этому вопросу уделяется большое внимание в популярнойлитературе, и здесь мы не будем останавливаться на его рассмотрении.
Задачи на проведение эйлеровых линий без повторений ибез отрыва карандаша от бумаги являются одним из математических развлечений.При решении подобных задач необходимо помнить следующее положение. Для того,чтобы на графе имелась цепь, соединяющая АА и ВВ, содержащая все его ребра вточности по одному разу, необходимо и достаточно, чтобы АА и ВВ былиединственными нечетными вершинами, т. е. вершинами с нечетной степенью.
§6. ПРИЛОЖЕНИЕ ТЕОРИИ ГРАФОВ В РАЗЛИЧНЫХ
ОБЛАСТЯХ НАУКИ И ТЕХНИКИ.
Графы и информация
Двоичные деревья играют весьма важную роль в теорииинформации. Предположим, что определенное число сообщений требуетсязакодировать в виде конечных последовательностей различной длины, состоящих изнулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считаетсякод, в котором средняя длина слов минимальна по сравнению с прочими распределениямивероятности. Задачу о построении такого оптимального кода позволяет решитьалгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию врамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответитьна который можно либо «да», либо «нет». Утвердительному иотрицательному ответу соответствуют два ребра, выходящие из вершины.«Опрос» завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервьюу различных людей, и ответ на очередной вопрос будет зависеть от заранеенеизвестного ответа на предыдущий вопрос, то план такого интервью можнопредставить в виде двоичного дерева.
Графы и химия
ЕщеА. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных)углеводородов, молекулы которых задаются формулой:
CnH2n+2
Все атомы углеводорода четырехвалентны, все атомыводорода одновалентны. Структурные формулы простейших углеводородов показаны нарисунке 6.1 (а – метан CH4, б –этанC2H6).
(РИСУНОК6.1)
Молекула каждого предельного углеводорода представляетсобой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводородатакже будут образовывать дерево, каждая вершина которого имеет степень не выше4. Следовательно, число возможных структур предельных углеводородов, т. е.число гомологов данного вещества, равно числу деревьев с вершинами степени небольше четырех.
Таким образом, подсчет числа гомологов предельныхуглеводородов также приводит к задаче о перечислении деревьев определенноготипа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
Графы и биология
Деревья играют большую роль в биологической теорииветвящихся процессов. Для простоты мы рассмотрим только одну разновидностьветвящихся процессов – размножение бактерий. Предположим, что черезопределенный промежуток времени каждая бактерия либо делится на две новые, либопогибает. Тогда для потомства одной бактерии мы получим двоичное дерево.
Нас будет интересовать лишь один вопрос: в сколькихслучаях n-е поколение одной бактерии насчитывает ровно kпотомков?Рекуррентное соотношение, обозначающее число необходимых случаев, известно вбиологии под названием процесса Гальтона-Ватсона. Его можно рассматривать какчастный случай многих общих формул.
Графы и физика
Еще недавно одной из наиболее сложных и утомительныхзадач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либодиэлектрика (изолирующего материала), на которой в виде металлических полосоквытравлены дорожки. Пересекаться дорожки могут только в определенных точках,куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие),их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертитьплоский граф, с вершинами в указанных точках.
Итак, из всего вышесказанного неопровержимо следуетпрактическая ценность теории графов, доказательство которой и являлось цельюданного параграфа.
СПИСОК ИСПОЛЬЗОВАННОЙ ИРЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ:
1. «Соросовский образовательныйжурнал» №11 1996 (ст. «Плоские графы»);
2. Касаткин В. Н. «Необычныезадачи математики», Киев, «Радяньска школа» 1987(часть 2);
3. Гарднер М. «Математическиедосуги», М. «Мир», 1972(глава 35);
4. «В помощь учителю математики»,Йошкар-Ола, 1972 (ст. «Изучение элементов теории графов»);
5. Олехник С. Н., Нестеренко Ю. В.,Потапов М. К. «Старинные занимательные задачи», М. «Наука»,1988(часть 2, раздел 8; приложение 4);
6. Гарднер М. «Математическиеголоволомки и развлечения», М. «Мир», 1971;
7. Оре О. «Графы и ихприменения», М. «Мир», 1965;
8. Зыков А. А. «Теория конечныхграфов», Новосибирск, «Наука», 1969;
9. Берж К. «Теория графов и ееприменение», М., ИЛ, 1962;
10. Реньи А., «Трилогия оматематике», М., «Мир», 1980.