Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов»




Скачать 179.92 Kb.
НазваниеРеферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов»
Дата публикации06.07.2013
Размер179.92 Kb.
ТипРеферат
uchebilka.ru > История > Реферат
Реферат скачан с сайта allreferat.wow.ua


Теория графов

ВЛАДИМИРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ РЕФЕРАТ «ТЕОРИЯ ГРАФОВ» Выполнила: Зудина Т.В. Владимир 2001 СОДЕРЖАНИЕ: 1. Введение 2. История возникновения теории графов 3. Основные определения теории графов 4. Основные теоремы теории графов 5. Задачи на применение теории графов 6. Применение теории графов в школьном курсе математики 7. Приложение теории графов в различных областях науки и техники 8. Последние достижения теории графов 9. Вывод §1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ. Родоначальником теории графов принято считать математика ЛеонардаЭйлера (1707-1783). Историю возникновения этой теории можно проследить попереписке великого ученого. Вот перевод латинского текста, который взят изписьма Эйлера к итальянскому математику и инженеру Маринони, отправленногоиз Петербурга 13 марта 1736 года [см. [5]стр. 41-42]: "Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто- нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором а обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".(РИСУНОК 1.1) По поводу обнаруженного им способа решать задачи подобного родаЭйлер писал [см. [5]стр. 102-104]: "Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими". Так можно ли обойти Кенигсбергские мосты, проходя только один разчерез каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера кМаринони: "Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку аведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать". Обоснование вышеприведенного правила можно найти в письме Л. Эйлера ксвоему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок изэтого письма. Математик писал, что переход возможен, если на участке разветвленияреки имеется не более двух областей, в которые ведет нечетное числомостов. Для того, чтобы проще представить себе это, будем стирать нарисунке уже пройденные мосты. Легко проверить, что если мы начнем двигатьсяв соответствии с правилами Эйлера, пересечем один мост и сотрем его, то нарисунке будет изображен участок, где опять имеется не более двух областей,в которые ведет нечетное число мостов, а при наличии областей с нечетнымчислом мостов мы будем располагаться в одной из них. Продолжая двигатьсятак далее, пройдем через все мосты по одному разу. История с мостами города Кенигсберга имеет современное продолжение.Откроем, например, школьный учебник по математике под редакцией Н.Я.Виленкина для шестого класса. В нем на странице 98 в рубрике развитиявнимательности и сообразительности мы найдем задачу, имеющуюнепосредственное отношение к той, которую когда-то решал Эйлер. Задача № 569. На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров и(РИСУНОК 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. Путем от а до X называется последовательностьребер, ведущая от ак 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. Две вершины а и B в графе называются связными(несвязными), если в нем существует (не существует) путь, ведущий из ав B. Определение 2.15. Граф называется связным, если каждые две еговершины связны; если же в графе найдется хотя бы одна пара несвязныхвершин, то граф называется несвязным. (РИСУНОК 2.10 и 2.11) На рисунке 2.10 изображен связный граф; на рисунке 2.11 – несвязный(т. к. существует минимум одна пара несвязных вершин – аи 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 — вершины данного графа, ap(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?3+4?4+ 5?5+…) или 3Г<2Р, но по условию,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, врача – аи D, синоптика – F и G, гидролога – B и F, радиста – С и D, механика – C и H. Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедицию, если F не может ехать без B, D – без H и C, C не может ехать вместе с G, а– вместе с B? Решение. Процесс решения задачи во всех подробностях мы рассматриватьне будем. Заметим только, что задать возможный вариант решения, то естьописать точный состав экспедиции, можно с помощью четного графа, в которомвершины разделены на две группы, а ребра могут соединять лишь вершиныразных групп. Применительно к задаче об экспедиции одна группа вершин есть группа из8 кандидатов, а вторая – из 6 должностей. Решение задачи изображено начетном графе (рис 4.2). (РИСУНОК 4.2) Задача 4.3. Планета имеет форму выпуклого многогранника, причем в его вершинах расположены города, а каждое ребро является дорогой. Две дороги закрыты на ремонт. Докажите, что из любого города можно проехать в любой другой по оставшимся дорогам. Решение. Пусть аи B – данные города. Докажем сначала, что из а в Bможно было проехать до закрытия на ремонт двух дорог. Рассмотрим для этогопроекцию многогранника на некоторую прямую, не перпендикулярную ни одномуиз его ребер (при такой проекции вершины многогранника не сливаются). Пусть A' и B' – проекции точек аи B, а M' и N' – крайние точкипроекции многогранника (в точки M' и N' проецируются вершины M и N). Еслиидти из вершины а так, что в проекции движение будет происходить понаправлению от M' к N' , то, в конце концов, мы обязательно попадем ввершину N. Аналогично из вершины B можно пройти в N. Таким образом, можнопроехать из ав B (через N). Если полученный путь из аи B проходит через закрытую дорогу, то естьеще два объезда по граням, для которых это ребро является общим. Втораязакрытая дорога не может находиться сразу на двух этих объездах. Значит, изгорода ав город 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.

Добавить документ в свой блог или на сайт

Похожие:

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua Теория Графов владимирский...

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua
Математическое моделирование высокочастотных радиоцепей на основе направленный графов

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua Отличия классической политэкономии...

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconТеория графов началась с задачи про семь кенигсбергских мостов. Вопрос...
Кенигсберга и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. Знаменитый петербургский математик...

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconПрограмма спецкурса «теория графов»
Автор программы: учитель информатики сош №33 Заводского района г. Запорожья Горовая Л. А

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua
Историки о происхождении Древнерусского государства. Теория норманистов и антинорманистов. Теория возникновения слова “Русь”

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua
...

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua Складывание антигитлеровской...

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua Вальдорфская школа Казанский...

Реферат скачан с сайта allreferat wow ua Теория графов владимирский государственный педагогический университет реферат «теория графов» iconРеферат скачан с сайта allreferat wow ua «Норманнская теория»
«Норманнская теория» происхождения русской государственности: ее апологеты и критики

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<