Графы и их применение в решении задач

  Графы и их применение в  решении задач

Введение 
 
     В этой работе мы рассмотрели понятие графа. В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем .это проблемы проектирования интегральных схем и схем управления, исследования автоматов, логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной оптимизации. 
     Цель работы: применить графы в решение задач в математике. 
     Задачи работы: рассмотрены основное понятия, виды графов, основные теоремы графов, применение графов к решению задач математики, краткий обзор применению графов в других науках. 
     Так как, данная работа выходит за рамки школьной программы, поэтому использовалась научная литература для ВУЗов, научно-практическая литература. 
 
ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ 
 
     Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). 
     Через город протекает река Преголя. Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано на рис. 1.1. 
     Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка.  
     Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. 
     Разрешить проблему удалось известному математику Леонарду Эйлеру. 
     Причем, он не только решил эту конкретную задачу, но придумал общий метод решения подобных задач. Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. В результате получилась фигу ра, изображенная на рис. 1.2. 
     Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки Д В, С, О называют вершинами графа, а линии, которые соединяют вершины - ребрами графа. На рис. 1.2 из вершин В, С, О выходят по 3 ребра, а из вершины А -5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными. 
     Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа: 
o Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.      Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.      Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком. 
     В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить путь там, где он был начат. 
     Задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков - К. Берж, О. Оре, А. Зыков.  
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ 
     Теория графов, как было сказано выше, - дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.  
     Определение 2.01. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.  
     Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек (см. рис. 2.1).  
     В дальнейшем вершины графа мы будем обозначать латинскими буквами A, B, C, D. Иногда граф в целом будем обозначать одной заглавной буквой.  
     Определение 2.02. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.  
     Определение 2.03. Граф, состоящий только из изолированных вершин, называется нуль-графом.  
     Обозначение: Q - граф с вершинами, не имеющий ребер (рис. 2.2).  
     Определение 2.04. Граф, в котором каждая пара вершин соединена ребром, называется полным.  
     Обозначение: U' - граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n-угольник, в котором проведены все диагонали (рис. 2.3).  
     Определение 2.05. Степенью вершины называется число ребер, которым принадлежит вершина. Вершина называется нечетной, если ее степень - число нечетное. Вершина называется четной, если ее степень - число четное. 
     Обозначение: p (A) - степень вершины A. Например, на рисунке 2.1: p(A)=2, p(B)=2, p(C)=2, p(D)=2, p(E)=2.  
     Определение 2.06. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k.  
     На рисунке 2.4 изображены графы нулевой (в), второй (а, б) и третьей (г) степени.  
     Определение 2.07. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.  
     На рисунке 2.5 (а) изображен исходный граф G, состоящий из четырех вершин и трех отрезков, а на рисунке 2.5 (б) - дополнение данного графа - граф G', а на рисунке 2.5(в) дополнение.  
     На рисунке 2.5 ребра AC и BD пересекаются в точке, не являющейся вершиной графа. Но бывают случаи, когда данный граф необходимо представить на плоскости в таком виде, чтобы его ребра пересекались только в вершинах  
     Определение 2.08. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским (рис.2.6).  
     Например, на рисунке 2.7 показан плоский граф, изоморфный (равный) графу. Однако, заметим, что не каждый граф является плоским, хотя обратное утверждение верно, т. е. любой плоский граф можно представить в обычном виде.  
     Определение 2.09. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.  
     Понятия плоского графа и грани графа применяется при решении задач на "правильное" раскрашивание различных карт. 
     Определение 2.10 (Правильная раскраска). Раскраска называется правильной, если образы любых двух смежных вершин различны. Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа. (Рис. 2.8) 
 
     Определение 2.11 (Двойственный граф). Граф, вершинами которого являются грани графа G, изображенного на поверхности, рёбрами - рёбра графа G, гранями - вершины графа G, отношение инцидентности - отношением ограниченности графа G, а отношение ограниченности - отношением инцидентности графа G, называется двойственным графом к графу G.  
     Для многогранников опять-таки существует очень наглядный способ получения двойственных графов. Он состоит в следующем. В центре каждой грани ставится точка - такие точки будут вершинами двойственного графа. Рёбрами надо соединить те вершины, грани которых разделены рёбрами в исходном графе. В результате получается многогранник, вписанный в исходный. Причём, если исходный граф правильный (полуправильный) многогранник, то и двойственный тоже будет правильным (полуправильным).  
     На рисунке 2.9 изображёны двойственные графы куба и октаэдра.  
     Определение 2.12. Путем от A до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.  
     Например, на рисунке 2.10 дан граф G', на котором проложен путь от C до H: (C, F); (F, B); (B, A); (A, H) или (C, D); (D, E); (E, A); (A, H).  
     Определение 2.13. Циклом называется путь, в котором совпадают начальная и конечная точка.  
     Вот пример цикла, проложенного на графе G (рис. 2.10): (A, B); (B, F); (F, C); (C, D); (D, E); (E, A).  
     Определение 2.14. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.  
     Определение 2.15. Длиной пути, проложенного на цикле, называется число ребер этого пути.  
     Пример: на графе G (рис. 2.10) проложен простой цикл (A, B); (B, F); (F, C); (C, D); (D, E); (E, A) длина пути этого цикла равна 6.  
     Определение 2.16. Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.  
     Определение 2.17. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.  
     На рисунке 2.11 изображен связный граф; на рисунке 2.12 - несвязный  
     Определение 2.18. (Цикломатическое число). Цикломатическим числом графа называется число связных компонент графа плюс число рёбер минус число вершин.  
     Определение 2.19. (Эйлеров цикл). Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем называть эйлеровым .Эйлеров цикл: Это h, {h,l}, l, {l,i}, i, {i,m}, m, {m,j}, j, {j,n}, n, {n,k}, k, {k,h}, h, {h,i}, i, {i,j}, j, {j,k}, k, {k,l}, l, {l,m}, m, {m,n}, n, {n,h}, h. (Рис. 2.13) 
     Кроме понятия эйлерова цикла в задачах часто возникает необходимость нахождения цепи, проходящей по каждому ребру ровно один раз (снимается требование замкнутости. Такие цепи будем называть эйлеровыми цепями.  
     Определение 2. 20. (Гамильтонов цикл). Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.  
     Содержит гамильтонов цикл граф ромбического додекаэдра (рис. 2.14)  
     Определение 2.21. Деревом называется связный граф, не содержащий циклов. 
     Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское - на поверхности земли (рис.2.15).  
     Определение 2.22. Несвязный граф, состоящий исключительно из деревьев, называется лесом.  
     Пример: на рисунке 2.16 изображен лес, состоящий из деревьев.  
     Определение 2.23. Дерево, все n вершин которого имеют номера от 1 до n, называют деревом с перенумерованными вершинами.  
     Деревья - очень удобный инструмент представления информации самого разного вида. Деревья отличаются общего случая от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятие дерева активно используется в информатике и программировании. 
     Без основные определения теории графов невозможно доказательство теорем, и решение задач  
 
ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ. 
 
     Приведем формулировки и доказательства теорем, которые затем найдут свои приложения при решении задач.  
     Теорема 3.1. Удвоенная сумма степеней вершин любого графа равна числу его ребер.  
     Теорема 3.2. Число нечетных вершин любого графа четно.  
     Эта теорема имеет немало любопытных следствий.  
     Следствие 1. Нечетное число знакомых в любой компании всегда четно.  
     Следствие 2. Число вершин многогранника, в которых сходится нечетное число ребер, четно.  
     Следствие 3. Число всех людей, когда-либо пожавших руку другим людям, нечетное число раз, является четным.  
     Теорема 3.3. Во всяком графе с n вершинами, где n больше или равно 2, всегда найдутся две или более вершины с одинаковыми степенями.  
     Теорема 3.4. Если в графе с n вершинами (n больше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.  
     Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из n школьников, обменивается фотографиями. В некоторый момент времени выясняется, что двое совершили одинаковое число обменов. Доказать, что среди школьников есть либо один еще не начинавший обмена, либо один уже завершивший его.  
     Теорема 3.5. Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.  
     Суть теоремы в том, что на этом графе невозможно найти цикл (как простой, так и непростой) нечетной длины, то есть содержащий нечетное число ребер.  
     Теорема 3.6. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.  
     Теорема 3.7. Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа.  
     Теорема 3.8. Если данный граф является связным и имеет 2k вершин нечетной степени, то в нем можно провести k различных цепей, содержащих все его ребра в совокупности ровно по одному разу.  
     Теорема 3.9. Различных деревьев с n перенумерованными вершинами можно построить n-2.  
     По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли (1821-1895). Графы-деревья издавна привлекали внимание ученых. Сегодня двоичные деревья используются не только математиками, а и биологами, химиками, физиками и инженерами.  
     Теорема 3.10. Полный граф с пятью вершинами не является плоским.  
     Теорема 3.11. (Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами.  
     Практическое применение основные теоремы теории графов будет рассмотрено в следующих главах работы. 
 
ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ. 
 
     Рассмотрим некоторые задачи, при решении которых используется теория графов. Они считаются классическими.  
     Задача 4.1. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств:  
     1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок;  
     2. учитель литературы может дать один, либо второй, либо третий урок;  
     3. математик готов дать либо только первый, либо только второй урок;  
     4. преподаватель физкультуры согласен дать только последний урок.  
     Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?  
     Решение. Без сомнения, эту задачу можно решить путем обыкновенного перебора всех возможных вариантов, но решение будет наиболее простым, если вычертить граф. Требуемый граф изображен на рисунке 4.1.  
     Рассмотрим еще одну задачу, решением которой также является граф.  
     Задача 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.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 можно проехать, по крайней мере, одним путем.  
 
ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ШКОЛЬНОМ КУРСЕ МАТЕМАТИКИ. 
 
     Рассмотренные задачи, которые используются в школе на уроках математики. Условно их можно классифицировать, подразделив на несколько групп:  
     1. Задачи о мостах.  
     2. Логические задачи  
     3. Задачи о "правильном" раскрашивании карт  
     4. Задачи на построение уникурсальных графов  
     Рассмотрим несколько типичных примеров решения задач каждого вида. Одной из наиболее известных задач о мостах является эйлерова задача; все остальные сформулированы похожим образом и решаются по тому же принципу. Основой применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Это выявление логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов.  
     Задача 5.1. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?  
     Решение: Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности. Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.  
     Задача 5.2. Какие буквы русского алфавита можно нарисовать одним росчерком? 
     Ответ: Б, В, Г, 3, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я. 
     Задача 5.3. В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде? Решение: Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.  
     Иными словами, суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа.  
     Задача 5.4. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе - каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис - с Андреем, Галиной; Виктор - с Галиной, Дмитрием, Еленой; Галина - с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось? 
     Решение: Построим граф (рис. 5.1). Сыграно 7 игр. На рис. 5.2. граф имеет 8 ребер, следовательно, осталось провести 8 игр. 
     Ответ: проведено 7 игр, осталось провести 8 игр. 
     Задача 5.4. В школьном драматическом кружке решили ставить гоголевского "Ревизора". И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина. 
     - Ляпкиным-Тяпкиным буду я! - решительно заявил Дима. - 
     С раннего детства я мечтал воплотить этот образ на сцене. 
     - Ну хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена. 
     - ...А мне ~ Осипа, - не уступил ему в великодушии Дима. 
     - Хочу быть Земляникой или Городничим, - сказал Вова. 
     - Нет, Городничим буду я, - хором закричали Алик и Боря. - 
     Или Хлестаковым, - добавили они одновременно. 
     Удастся ли распределить роли так, чтобы исполнители были довольны? 
     Решение: Построим граф для ситуации, описанной в задаче (рис. 5.3.). 
     Граф с 10 вершинами и 10 ребрами. Надо выбрать из десяти пять ребер, не имеющих общих вершин: Дима - Осип, Вова - Земляника, Гена - Ляпкин-Тяпкин. Остается два случая: Алик - Хлестаков, Боря - Городничий или Алик - Городничий, Боря - Хлестаков. Как показывает граф, других решений нет. 
     Любая географическая карта является многоугольным графом, в котором страны будут гранями, границы - ребрами, а окружающий страны Мировой океан - бесконечной гранью.  
     Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют "правильно" раскрашенной.  
     Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому вопросу уделяется большое внимание в популярной литературе, и здесь мы не будем останавливаться на его рассмотрении.  
     Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от бумаги являются одним из математических развлечений. При решении подобных задач необходимо помнить следующее положение. Для того, чтобы на графе имелась цепь, соединяющая АА и ВВ, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы АА и ВВ были единственными нечетными вершинами, т. е. вершинами с нечетной степенью.  
 
ПРИЛОЖЕНИЕ ТЕОРИИ ГРАФОВ В РАЗЛИЧНЫХ ОБЛАСТЯХ НАУКИ И ТЕХНИКИ. 
 
Графы и информация 
     Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.  
     Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.  
     Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.  
Графы и химия 
     Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:  
CnH2n+2  
     Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.  
     Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.  
Графы и биология 
     Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов - размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.  
     Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.  
Графы и физика 
     Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.  
     Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.  
     В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.  
     Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов, доказательство которой и являлось целью данного параграфа.  
 
ЗАКЛЮЧЕНИЕ 
 
     В работе рассмотрены основное понятие графа - совокупность конечного числа точек (вершины) и попарно соединяющих некоторые из этих вершин линий (ребра или дуги графа). А так же рассмотрены основные виды графов (маршруты, цепи, циклы, раскраски, плоские графы, дерево, лес, и т.д.), основные теоремы графов, их применение в решение задач. Кратко рассмотрена история возникновения графов при переписке родоначальника теории графов итальянского математика Леонардо Эйлера (1707-1783) с итальянским математиком-инженером Мариони.  
     Были решены задачи с использованием графов, приведены примеры различных задач из других областей науки и техники. 
     С помощью графов решать задачи очень удобно, интересно, увлекательно, можно рассмотреть несколько вариантов решения одной и той же задачи и выбрать наиболее легкое, удобное, красивое, интересное решение задачи.  
     В работу не вошли некоторые материалы, т.к. ограничен обьем работы и время выступления. Существует еще несколько групп и подгрупп графов, теорем и следствий из них, а так же преобразований над графами.  
     Графы не входят в школьный курс математики и не факультативных занятиях их было бы интересно, познавательно рассмотреть многим учащимся и даже учителям  
 
СПИСОК ЛИТЕРАТУРЫ: 
 
1. "Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");  
2. Касаткин В. Н. "Необычные задачи математики", Киев, "Радяньска школа" 1987(часть 2);  
3. Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);  
4. "В помощь учителю математики", Йошкар-Ола, 1972 (ст. "Изучение элементов теории графов");  
5. Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);  
6. Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;  
7. Оре О. "Графы и их применения", М. "Мир", 1985;  
8. Зыков А. А. "Теория конечных графов", Новосибирск, "Наука", 1969;  
9. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988.  
10. Кук Д., Бейз Г. Компьютерная математика. - М.: Наука, 1990.  
11. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992.  
12. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.  
13. Оре О. Теория графов. - М.: Наука, 1980.  
14. Ж.-Л. Лорьер. Системы искусственного интеллекта. - М.: Мир, 1991.  
15. Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1978.  
16. Березина Л.Ю.Графы и их применение. -М.: "Просвещение", 1979