1158

Понятие граф в математике

Реферат

Математика и математический анализ

Примеры построения диаграммных графов. Степень вершины графов и их изолированность. Изображение одного и того же графа. Эйлеровы графы. Решение задачи о семи кенигсбергских мостах. Двудольные графы. Планарные и плоские графы. Графы с цветными ребрами.

Русский

2012-11-16

360 KB

145 чел.

Понятие "граф" в математике

Введение.

 Любой из нас, конечно, прав,

Найдя без проволочек,

Что он … обыкновенный граф

Из палочек и точек.

Понятие «граф» – одно из самых простых и самых употребительных понятий в математике и других науках, хотя теория графов зародилась чуть ли не 250 лет тому назад в ходе решения головоломки, и тогда же появились первые теоремы о графах, доказанные самим Леонардом Эйлером.

Долгие годы эта теория не находила широких приложений и была известна в основном как средство решения головоломок, логических или развлекательных задач, задач олимпиадного типа или на смекалку. При решении таких задач удобно составлять таблицы, изображать объекты точками, соединять их отрезками или стрелками, подмечать закономерности из полученных рисунков, выполнять над точками и отрезками операции, не похожие на алгебраические и геометрические.

И в обычной жизни очень часто мы рисуем на бумаге точки, изображающие химические вещества, населенные пункты, генеалогические деревья и соединяем эти точки линиями и стрелками, означающими некоторые отношения между рассматриваемыми объектами. Такие схемы встречаются всюду под различными названиями: электрические цепи (в физике), карты, лабиринты, диаграммы, генеалогические деревья, диаграммы организации (в экономике), социограммы (в психологии) и т.д. В 1936 году Д. Кёниг предложил называть такие схемы графами и систематически изучать их свойства.

Итак, как отдельная математическая дисциплина теория графов была представлена лишь в 30 – е годы ХХ столетия в связи с тем, что в обиход вошли так называемые «большие системы», т.е. системы с большим числом объектов, связанных между собой разнообразными соотношениями: сети железных дорог и авиалиний, телефонные узлы на много тысяч абонентов, системы заводов – потребителей и предприятий – поставщиков, радиосхемы, большие молекулы и т.д. и т. п. Стало ясно, что разобраться в функционировании таких систем невозможно без изучения их конструкции, их структуры. Здесь и пригодилась теория графов. В середине XX века задачи теории графов стали возникать также и в чистой математике (в алгебре, топологии, теории множеств). Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. Ныне она переживает эпоху бурного возрождения.

Графы используются: 1) в теории планирования и управления, 2) в теории расписаний, 3) в социологии, 4) в математической лингвистике, 5) экономике, 6) биологии, 7) химии, 8) медицине, 9) в областях прикладной математики таких, как теория автоматов, электроника, 10) в решении вероятностных и комбинаторных задач и т.д.

Наиболее близки к графам – топология и комбинаторика.

Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по        каждому мосту – только один раз.  Возможен ли вообще такой маршрут?

Для удобства решения составили схему или диаграмму. Части суши  (оба берега и острова) обозначили точками А, В, С, D, а пути их соединяющие и проходящие по мостам, изобразим линиями, соединяющими эти точки. (Рис. 2) Такая схема содержит всю необходимую информацию о рассматриваемой ситуации и не содержит ничего лишнего. Глядя на нее, можем заключить только, что четыре объекта – А, В, С, D – попарно как-то связаны между собой ( в данном случае мостами), причем А с В и В с С соединены двойной связью, а D с каждым из объектов А, В и С – одинарной. Точки А, В, С, D – вершины, соединяющие их линии – ребра диаграммы.

Задача будет решена в ходе работы над схемой рисунка 2. (показано позднее)

Очевидно, что подобными схемами можно описать самые различные объекты и ситуации. Например, вершинами могут быть атомы в молекуле, а ребрами – связи между ними. Точно так же можно рассмотреть множество людей и соединить их попарно на схеме линиями в том случае, если они знакомы, или если они родственники. Существуют схемы метрополитена, железных или шоссейных дорог, планы выставок и т.д., словом, схемы и планы без указания масштаба, показывающие лишь связи между принадлежащими объектами, состоящие из вершин и ребер, однако с ними трудно проделывать формальные операции, следовательно, диаграммы из точек и линий надо заменить какими-то более формализованными моделями. Так пришли к графам.

П. 1. Основные понятия.

Определение 1. Будем говорить, что задан граф G, если задано конечное множество  и некоторое множество W неупорядоченных пар различных элементов из V: . Таким образом, граф – это упорядоченная пара . Элементы множества V называют вершинами графа, а заданные пары этих элементов – ребрами. Множество ребер W, соединяющих элементы множества V, отображают это множество само в себя.

Замечание. Определение графа совпадает с определением отношения на множестве. Граф – бинарное отношение на множестве V , т.е. подмножество R множества  (множество всех упорядоченных пар вида , где ).

В соответствие каждому графу можно поставить некоторую схему на плоскости, если вершины графа изобразить точками, а ребра – линиями. Эту схему называют диаграммой графа, геометрическим графом или, для краткости, просто графом. Отсюда, определение 1 можно переписать в виде:

Определение 1. Граф представляет собой непустое множество точек и множество отрезков прямых или кривых линий, оба конца которых принадлежат заданному множеству.

Определение 2. Граф с p вершинами и q ребрами называется (p, q) – графом.

Обозначения:  графG или Г;  

вершины – заглавными различными буквами А, В, С …, или маленькими различными буквами, или одинаковыми буквами с индексами х1, х2,...  или числами 1, 2, 3…;

ребра – (А,В) или , или , или (х1, х2), или (1,2) (отрезки или дуги , соединяющие вершины) или просто u1, u2…(первое ребро, второе и т.д.)

Изображение. Точки – вершины –  выделяют кружочками или квадратиками. Ребра, соединяющие некоторые вершины,  изображают отрезками прямой или дугами. Существуют вершины, которые не соединены ребрами. Они называются изолированными.

 Задание графа (1 способ) Задать граф можно путем перечисления дуг (или ребер) графа с указанием концов и добавлением списка изолированных вершин, например, граф с множеством вершин  и списком дуг .  

Пример.  Построить графы: а) Г = ,  b) .

Построение.

Один и тот же граф можно изобразить по-разному.

Примеры

Замечание 1. Не всегда точка пересечения ребер принимается за вершину, например, на рис. точка А – не вершина.

Замечание 2. Диаграмма графа наглядно иллюстрирует его свойства. Но не надо отождествлять эти понятия прежде всего потому, что одному и тому же графу можно поставить в соответствие внешне различные диаграммы. Например, графу  , где , , можно поставить в соответствие диаграмму рис.3. Здесь по ошибке точку пересечения ребер (b,e) (c,d) можно принять за вершину, которой она не является. Этот же граф можно изобразить на рис. 4, 5, 6, на которых ребра пересекаются только в вершинах.

Определение 3. Два геометрических графа называются изоморфными, если они являются диаграммами одного и того же графа (каждой паре вершин а, b графа G, соединенных ребром соответствует пара вершин графа так же соединенных ребром).

Определение 4. Мультиграфами называются графы, у которых пара вершин  соединена двумя или несколькими ребрами.  (В дальнейшем будем называть просто графами)

Пример: мультиграф кенигсбергских мостов

Определение 5. Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром.

Замечание. В полном графе каждая его вершина принадлежит одному и тому же числу ребер.

Определение 6. Если ребро  соединяет вершины  и , то говорят, что оно инцидентно вершине а и вершине b. Эти вершины называются смежными и инцидентными ребру . Два ребра называются смежными, если они инцидентны одной вершине.

Определение 7. Матрицей смежности называется квадратная матрица , строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент равен числу дуг, идущих из вершины xi  в вершину  xj. Если исходящих дуг нет, то .

Пример. Составить матрицу смежности графа

Решение. Граф имеет 4  вершины, следовательно, матрица смежности имеет размерность .  Наличие ребер: 1 в 1 – нет ребра, 1 в 2 – есть ребро, 1 в 3 – есть ребро, 1 в 4 – нет ребра. Следовательно, первая строка имеет вид: 0 1 1 0.

Вершина 2 соединена только с вершиной 1, следовательно, вторая строка имеет вид: 1 0 0 0. Вершина три – изолированная, следовательно, третья строка – нулевая. Вершина 4 соединена ребром с вершиной 1 и дугой с самой собой, следовательно, четвертая строка: 1 0 0 1.

Тогда матрица смежности имеет вид:   .

Определение 8. Матрицей инцидентности или инциденций называется прямоугольная матрица , строки которой соответствуют вершинам графа, а столбцы – ребрам.     Если вершина xi и ребро uj инцидентны, то ,  и  в противном случае.

Пример. Составить матрицу инциденции для графа.

Решение. Обозначим ребра как u1, u2, u3, u4.

Матрица имеет вид:  .

  1.  Замечание. Граф может быть задан не только перечислением дуг (или ребер) графа с указанием концов и добавлением списка изолированных вершин, но и матрицей смежности и матрицей инцидентности (инциденций)

Определение 9. Граф Г называется подграфом графа G, если все вершины и ребра графа Г принадлежат графу G.

Определение 10. Дополнением графа  называется граф с теми же вершинами, что и у графа  и с теми и только с теми ребрами, которые необходимо добавить к  , чтобы получился полный граф.

Пример.

Определение 11 . Степенью вершины называется число ребер графа, которым принадлежит эта вершина.  Вершина называется нечетной, если ее степень – нечетное число.  Вершина называется четной, если ее степень число четное.

Пример.

Замечание. Степень каждой вершины полного графа на единицу меньше числа его вершин.

Пример.

Рассмотрим задачу: Как можно пройти по ребрам графа, изображенного на рисунке, из вершины А1 в вершину А5?

Решение.

Запишем, как можно пройти:

  1.  (А1А4), (А4А5).
  2.  (А1А2), (А2А4), (А4А5).
  3.  (А1А4), (А4А2), (А2А1), (А1А4), (А4А5).
  4.  (А1А2), (А2 А4), (А4 А3), (А3А1), (А1А4), (А4А5) и другие…

В одних ребра повторяются, в других – не повторяются. Но не всякую последовательность ребер, ведущих из А1 в А5 называют путем из А1 в А5.

Определение 12. Маршрутом от А1 до Аn в графе называется чередующаяся последовательность вершин и инцидентных им ребер, т.е. такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседние ребра имеют общую вершину.

Определение 13. Маршрут называется путем или цепью, если все его ребра различны, т.е.  никакое ребро не встречается более одного раза.

В примере все даны маршруты, при этом 1) и 2) – пути, а 3) и 4) – не пути.

Определение 14. Путь называется простой цепью или простым путем, если все его вершины (за исключением, может быть, первой и последней) различны. (Т.е. путь не проходит ни через одну из вершин графа более одного раза).

Определение 15. Цепь, в которой начальная и конечная вершины совпадают, называется циклом. Если при этом цепь – простая, то она называется простым циклом.

В примере acbdeba – цикл, но не простой; acdeba – простой цикл.

Задача.

Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

Решение.

Каждого из компании изобразим на рисунке кружком. Если двое знакомы, соединим соответствующие кружки отрезком.

Из рассматриваемой компании нельзя выделить ни четырехугольник, ни треугольник, поскольку тогда условие задачи будет нарушено, т.е. схема единственна.

Данный граф – цикл.

Определение 16. Если все вершины графа имеют одну и ту же степень r, то граф называется однородным графом степени r.

Например, простой цикл является однородным графом степени 2.

Теорема 1. ( Первая теорема теории графов. Доказана Эйлером.)

Сумма степеней вершин    (p, q) – графа равна удвоенному числу его ребер: .

Определение 17. Длиной маршрута называется число ребер в нем, при этом каждое ребро считается столько раз, сколько оно встречается в данном пути. Длиной пути называется число ребер пути.  Длиной цикла называется число ребер цикла.

Определение 18. Две вершины графа А и В называются связными, если существует путь с концами А и В.

Определение 19. Граф называется связным, если каждые две вершины его связные, иначе, если любая пара его вершин соединяется цепью. Граф называется несвязным, если хотя бы две вершины несвязные.

Если граф не связан, то его можно разбить на подграфы так, что все вершины в подграфе будут связаны, а вершины из различных подграфов не связаны. Такие подграфы называются компонентами связности графа.

Определение 20. Максимально возможный связный подграф графа G называется компонентой графа G.

Несвязный граф имеет по крайней мере две компоненты.

Определение 21. Ребро (А,В) называется мостом графа G, если в графе, полученном после удаления из графа G ребра (А,В) вершины А и В оказываются несвязными.

П. 2. Деревья.

Определение 22. Всякий связный граф, не имеющий циклов, называется деревом. Несвязный граф, каждая компонента которого является деревом, т.е. представляющий собой объединение деревьев, называется лесом.

Определение 23. Вершина называется изолированной, если степень ее равна нулю. Если степень вершины дерева равна единице, то она называется висячей вершиной.

В примере висячими являются вершины a, b, c, d, e, f, g.

Дерево с р вершинами содержит р –1 ребер.

Многие графы, употребляемые в приложениях, являются деревьями. Например, графы всевозможных сортировок и классификаций. Корреспонденцию, пришедшую в страну, сортируют сначала по городам. Затем, в каждом городе – по отделениям связи, там – по участкам и т.д.  Подобно этому живые организмы классифицируют сначала по типам, внутри типа – по классам, затем – по порядкам и т.д.  

Деревьями являются и всевозможные схемы идентификаций, например, в аналитической химии при качественном анализе пользуются деревом, вершинами которого являются некоторые стандартные тестовые реакции. Выбор ребра, по которому надо двигаться из данной вершины, определяется поведением исследуемого вещества в соответствующей реакции (выпадение в осадок, помутнение и т.п.).

В физиологии рассматривают трахеобронхиальное дерево, вершинами которого являются участки раздвоения дыхательных путей, а ребрами – сами эти пути.

Наконец, деревьями являются всевозможные схемы происхождения: дерево языков, дерево происхождения видов, фамильное дерево и т.д.

Задача.

Лист бумаги Плюшкин разрезает на три части.  Некоторые из полученных листов он так же разрезает на три части. Несколько новых листиков он вновь разрезает на три более мелкие части и т.д. Сколько Плюшкин получает листиков бумаги, если разрезает k листов?

Решение.

Листы бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, будут белыми крупными, остальные нарисуем маленькими черными.

Рисунок 7 помогает увидеть, что при разрезании одного листка на три части, число листков увеличивается на два.  Если же разрезано k листов, то образовалось (1+2 k) листов (рис. 8). На этом рисунке показано 5 разрезаний.

П. 3. Изображение одного и того же графа.

Один и тот же граф может выглядеть на рисунке по-разному.

Необходимое и достаточное условие соответствия двух рисунков одному и тому же графу: между вершинами на рисунках должно существовать взаимно однозначное соответствие, при котором две вершины графа на первом рисунке соединены ребром, если соединена ребром соответствующая пара вершин графа на втором рисунке и наоборот.

Примеры.

Один ли граф изображен на этих рисунках?

1. Вершины одинаково обозначены, имеют одинаковые степени, следовательно, на рисунке изображен один и тот же граф.

2. Для того, чтобы понять,  один ли граф изображен на этом рисунке, обозначим вершины на обоих графах буквами и посчитаем количество вершин и ребер.

Решение.

Для графа а): степень вершины А = 2,                 степень       Е = 2, степень В = 3, степень D = 3,         степень С = 2.

Граф имеет 5 вершин, 6 ребер.

Для графа b): степень вершины А = 2, степень            Е = 2, степень В = 3, степень D = 3, степень С = 2.

Граф имеет 5 вершин, 6 ребер.

Вершины на рис. b) обозначены в соответствии с рис. а).

Ответ: Это один и тот же граф.

3. На этом рисунке изображены два разные графа, так как у первого графа только две вершины А и В имеют степень равную 2. Во втором графе таких вершин больше.

П. 4. Эйлеровы графы.

Мы уже говорили, что исторически теория графов (как и топология) зародилась при решении Эйлером головоломок, в которых требуется вычертить на плоскости росчерком замкнутые кривые, обводя каждый участок в точности один раз.

Определение 24. Эйлеровым путем в графе называется путь, содержащий все ребра графа.

Определение 25. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.

Определение 26. Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Теорема 2. Если граф обладает эйлеровым циклом, то он связный.

                                                                                                                              

Примеры эйлеровых графов: 

1) план выставки, если экспонаты расположены по обеим сторонам залов, т.е. можно составить такой замкнутый маршрут, что по каждому залу посетитель сможет пройти в точности два раза – по одному с каждой стороны в разных направлениях.

2) Любой город можно обойти, пройдя по каждой улице ровно два раза – по одному в каждом направлении.

3) На рисунке изображена схема зоопарка. Вершины графа – вход, выход, перекрестки, повороты, тупики. Ребра – дорожки, вдоль которых расположены клетки. Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути.

Решение.

Замечание. Способ обходить все ребра графа можно использовать, например, для отыскания пути, позволяющего выбраться из лабиринта. Если известно, что у лабиринта все «стенки» связаны друг с другом, т.е. нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт всегда можно обойти весь, касаясь стенки одной рукой, например, правой.

Существует правило Тарри (французский математик) – правило обхода любого лабиринта – при обходе лабиринта следует, попадая в любой перекресток А впервые по некоторому пути а, при возвращении в этот перекресток А избегать пользоваться путем а до тех пор, пока это возможно; и лишь только в том случае идти по пути а в обратную сторону, когда все остальные пути из А будут пройдены дважды.

Теорема 3. Для того, чтобы связный граф (мультиграф) был эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными.

Замечание. Данная теорема позволяет решить задачу о семи кенигсбергских мостах.

Решение задачи о семи кенигсбергских мостах.

Вопрос задачи: возможно ли найти такой маршрут, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз?

В терминах теории графов эта задача может быть сформулирована так: является ли мультиграф семи кенигсбергских мостов эйлеровым графом?

Найдем степени вершин. Степень А = 3, ст. В =5, ст. D = 3, ст. С =3.

Из теоремы 3 следует, что данный мультиграф неэйлеров, так как его вершины имеют нечетную степень. Из этой же теоремы видно, как нужно дополнить граф, что бы он стал эйлеровым.

Ответ. Такой маршрут не существует.

П. 4. Двудольные графы.

Определение 27. Граф  называется двудольным, если множество его вершин V можно разбить на два таких непересекающихся подмножества V1 и V2 , что никакие две вершины из одного и того же подмножества не соединены между собой ребрами.

Замечание. Чтобы подчеркнуть, что данный граф – двудольный, его вершины на диаграмме располагают параллельными строками или столбцами:

Двудольные графы полезны, когда изучаемые объекты разделяются на две группы так, что внутри групп интересующие нас взаимодействия отсутствуют. В генетике, например, это могут быть признаки и гены, в демографии – особи разного пола, в экологии – хищники и жертвы, в экономике – производители и потребители и т. д.

Определение 28. Двудольный граф называется полным двудольным, если каждая вершина V1 соединена с каждой вершиной V2.

Обозначение: Un,m – полный двудольный граф, множество V1 которого содержит n вершин, а V2m вершин.  В таком графе имеется (nm) ребер.

По виду диаграммы графа не всегда просто определить, является ли данный граф двудольным. Ведь совсем не обязательно, чтобы вершины двудольного графа располагались двумя параллельными строками. Например, любая простая незамкнутая цепь – двудольный граф, как и любое дерево.

Например:

Теорема 4. Граф двудолен тогда и только тогда, когда все его простые циклы имеют четную длину. (Простые циклы – все вершины различны, начальная и конечная вершины совпадают)

С двудольными графами связана задача о назначениях. Пусть имеется несколько рабочих мест для строителей, несколько – для слесарей, какое-то число мест для маляров, монтажников и т. д. – всего m рабочих мест. С другой стороны, имеется n претендентов. Причем, некоторые из претендентов владеют несколькими профессиями. Можно ли всех претендентов обеспечить работой, и каждому из них предоставить должность в соответствии с его профессиональной подготовкой?

Понятно, что это можно сделать  далеко не всегда. Во-первых, д. б. m n. Но этого мало, пусть,  например, вакантными являются три места монтажника и одно место строителя. Тогда группу, состоящую из двух строителей и одного строителя – монтажника, нельзя обеспечить работой. Один из строителей окажется незанятым.

Сформулируем задачу в терминах графов. Пусть V1 – множество претендентов, V2 – множество вакантных рабочих мест. Вершину a из V1 соединим ребром с вершиной b из V2, если претендент a способен занять рабочее место b. Тогда получим двудольный граф G (рис. 9) Наша задача заключается в том, чтобы из этого графа выделить подграф G1 , состоящий из компонент, в каждой из которых только две вершины, и эти вершины соединены ребром (рис. 10 ). G1 – подграф назначений.

Теорема 5 (необходимое и достаточное условие существования подграфа назначения)

Пусть множество V1 двудольного графа G содержит n вершин. Для того, чтобы граф G содержал подграф назначений G1, необходимо и достаточно, чтобы для любого подмножества , содержащего k вершин, k = 1,2,…,n , нашлось k вершин из V2, каждая из которых соединена ребром хотя бы с одной вершиной из А.

                                                                                                                              

В терминах первоначальной задачи это означает, что какую бы группу из k претендентов мы бы ни взяли, найдется k должностей, каждую из которых способен занять хотя бы один человек из взятой группы.

Замечание 1. От ограничения m n можно отказаться и изучать вопрос о том, сколько и каких подграфов назначений с тем или иным числом компонент можно образовать из данного двудольного графа и т. д.

Замечание 2. Немецкий математик Герман Вейль называл задачу о назначениях задачей о деревенских свадьбах. В его трактовке V1 и V2 – это множества девушек и юношей, живущих в одной деревне, а ребра графа означают, что юноша и девушка знакомы (или симпатичны) друг с другом. Желая обеспечить каждую девушку женихом из множества знакомых (или симпатичных) парней, мы должны будем отыскать в этом двудольном графе подграф назначений.

Замечание 3. Подобно двудольным графам можно рассматривать трехдольные и k-дольные с любым k.

П. 5. Планарные и плоские графы.

Среди изоморфных диаграмм одного и того же графа могут быть диаграммы с ребрами, пересекающимися не только в вершинах. Некоторыми из таких диаграмм легко заменить изоморфными, лишенными этого недостатка.

Определение 29. Граф называется планарным, если его можно изобразить на плоскости диаграммой, ребра которой пересекаются только в вершинах.

Саму диаграмму называют плоским графом. 

Замечание. Одни графы можно нарисовать на плоскости так, чтобы их ребра не имели общих точек, кроме вершин им принадлежащим; другие так рисовать нельзя. В силу этого отдельные графы могут рассматриваться как географические карты, нанесенные на плоскость или сферу.

Определение 30. Если планарный граф односвязен, то его плоский граф называется картой.

Пример.

На рис. а) изображен не плоский граф.  На рис. b) изображен тот же граф, только плоский.

На рис. с) изображен не планарный граф, на рис. d) – изоморфный ему плоский граф – карта. В отличие от географических карт плоский односвязный граф может иметь висячие вершины.

Рассмотрим карту некоторого графа.

Определение 31. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

Пример.

     На рис. а) (1,2,4,1) – не грань, так как она содержит внутри себя (1,2,3,1). Всего в графе четыре грани: (1,7.4,1), (1,4,2,3,1), (1,2,3,1), (2.6,5,4,2).

      На рис.b) (1,2,3,4,1) – грань, так как ребро (4,5) не образует цикла.

Определение 32. Цикл, охватывающий все внутренние грани, называется внешней границей карты. Множество точек плоскости, лежащих вне этого цикла, называется границей внешней грани.

Замечание. Любому выпуклому трехмерному многограннику можно поставить в соответствие некоторую карту, ребра и грани которой, включая внешнюю, соответствуют ребрам и граням многогранника.

Теорема 6. Для любой карты число вершин (В), число ребер (Р) и число граней карты (Г), включая внешнюю, связаны равенством:  В + ГР = 2

Теорема 7. Полный двудольный граф U3,3 и полный граф U5 непланарны.

Теорема 8. Для того, чтобы граф G был планарным, необходимо и достаточно, чтобы он не содержал подграф, который можно было бы сузить до U3,3 или U5 .

Пример (задача о трех домах и трех колодцах)

В одной деревне недалеко от трех домов расположены три колодца. В разное время года доступным оказывается то один, то другой колодец (в жару один из колодцев пересыхает, в мороз какой-то из них замерзает и т. д.). Поэтому каждый дом должен быть соединен тропинкой с каждым колодцем, причем, тропинки пересекаются между собой. С этим хозяева домов легко мирились, пока жили в дружбе. Но вот они поссорились, и каждый захотел иметь свои собственные тропинки к колодцам, не пересекающиеся с тропинками соседей. Можно ли проложить такие тропинки?

Решение.

Решим данную задачу с помощью графов. Обозначим вершины графа как a1, a2, a3, b1, b2, b3, где a1, a2, a3 – дома, b1, b2, b3 – колодцы. Между группой вершин a1, a2, a3 и группой вершин b1, b2, b3 наблюдается соответствие. От каждой вершины отходит три ребра к соответствующим вершинам. По условию задачи, мы имеем полный двудольный граф U3,3 с пересекающимися ребрами. Можно ли построить плоский граф, изоморфный графу U3,3? Иными словами, является ли граф U3,3 планарным?

                              

 Двудольный граф U3,3 имеет вид. Из теоремы 7 следует, что данный граф не является планарным. Т.е. проложить непересекающиеся тропинки нельзя!

Замечание. Дорожки можно было бы устроить непересекающимися, если бы один из домов удалось приподнять над землей. Иными словами, если вершины этого графа размещать не в плоскости, а в трехмерном пространстве, его ребра пересекаться не будут. Это свойство присуще любому графу.

П. 6. Графы с цветными ребрами.

Рассмотрим ситуации, когда одна пара элементов множества находится между собой в одном отношении, другие пары этого же множества – в другом и т. д. Например, 1) среди команд-участников баскетбольного турнира к какому-то моменту могут быть такие, которые уже сыграли матчи друг с другом, и такие, которые не сыграли; 2) существуют страны, установившие между собой дипломатические связи, и страны, между которыми они не установлены.

Для удобства, на диаграммах графов ребра, соответствующие одному отношению, окрашивают в один цвет, а ребра, соответствующие другому отношению – в другой цвет. Чем больше отношений, тем больше приходится вводить цветов для окраски ребер.

Такие графы называют графами с цветными ребрами.

Пример.

Шесть школьников участвуют в шахматном турнире, который проводится в один круг, т. е. каждый шахматист встречается со всеми участниками по одному разу. Докажите, что среди них всегда найдутся три участника турнира, которые провели уже все встречи между собой или еще не сыграли друг с другом ни одной партии.

Решение.

Любые два участника находится в одном из двух отношений: они либо  уже сыграли друг с другом, либо нет. Каждому участнику поставим в соответствие вершину графа. Соединим вершины попарно ребрами двух цветов. Пусть ребро красного цвета означает, что двое уже сыграли друг с другом, а синего – что не сыграли. Получим полный граф с шестью вершинами и ребрами двух цветов. Теперь для решения задачи достаточно доказать, что в таком графе обязательно найдется «треугольник» с одноцветными сторонами.

Примеры других задач:

1. В трехмерном пространстве девять точек размещены так, что никакие три не лежат на одной прямой. Каждая точка соединена отрезками прямых в точности с четырьмя другими. Докажите, что всегда найдется хотя бы один треугольник с вершинами в этих точках.

2. Докажите, что во всякой группе из девяти человек, в которой не найдутся трое попарно незнакомых, найдутся четверо попарно знакомых.

П. 7. Ориентированные графы.

Вводя понятие графа, мы интерпретировали ребро (дугу) u как символ связи между двумя объектами. Но часто такая связь бывает неравнозначной. Например: 1. Два человека могут быть не просто знакомыми, а, допустим, один из них по службе подчиняется другому, или один из них является родителем другого. 2. Схема города – граф с вершинами на перекрестках и поворотах, а если ввести одностороннее движение транспорта, то на ребрах необходимо ставить указатели направления движения.

Чтобы отразить подчинение одной вершины другой, рассматривают упорядоченные пары вершин, а соответствующий граф называют ориентированным графом или орграфом.

Определение 33. Ориентированным графом называется упорядоченная пара , где  – множество вершин, – множество упорядоченных пар различных вершин из V.

Определение 34. Упорядоченная пара (a, b) называется ориентированным ребром или дугой , идущим из вершины а к вершине b.

На диаграммах ориентированных графов и мультиграфов ребра снабжают стрелкой, указывающей, в какую вершину идет данное ребро.

Иногда ориентированное ребро (или дугу) от А к В обозначают: , А – начальная вершина, В – конечная вершина.

Замечание. Ориентированный граф определяется как кортеж , где V  – набор вершин, а W – подмножество , обозначающее ребра.

Пример. Пусть Х – множество лиц некоторой военной организации. Бинарное отношение R на множестве Х введем следующим образом: xRy, если лицо у подчинено лицу х. Итак, (X, G) – граф. Связь любого начальника с подчиненным изобразиться в виде ребра графа (X, G).

Определение 33 можно переписать:  Граф, все ребра которого ориентированы, называется ориентированным графом.

Соответствующим образом можно определить и ориентированные мультиграфы.

Примеры.

1. Изобразить орграф , где , .

Решение.

2. Проводится круговой турнир по баскетболу между командами A, B, C, D, E. Каждая команда играет с каждой командой по одному разу. Требуется изобразить итоги турнира: В выиграла все встречи, С проиграла все, А выиграла у С и D и проиграла у В и D.

Решение.

Поставим командам в соответствие вершины, соответствующий условию задачи ориентированный граф имеет вид: : X выиграла у Y.

Определение 35. Степенью выхода вершины А ориентированного графа называется число выходящих из А ребер. Степенью входа вершины А называется число ребер, входящих в А.

Определение 36. Изолированной вершиной ориентированного графа называется вершина, у которой и степень входа и степень выхода равны нулю. Источником называется вершина, степень выхода которой положительна, а степень входа равна нулю. Стоком называется вершина, степень входа которой положительна, а степень выхода равна нулю.

Определение 37. Вершина А и ребро (дуга)  u называются инцидентными, если ребро заходит в эту вершину или исходит из нее.

Способы задания орграфов.

1. Перечислением дуг (или ребер) графа с указанием концов и добавлением списка изолированных вершин.

2. Заданием множества его вершин V и способа отображения Г множества V в V, таким образом, орграф G есть пара (V, Г), например, орграф, заданный следующим образом    Гх1 = х1,  Гх2 = , Гх3 = ,  Гх4 =  изображается в виде:

3. Заданием матрицы смежности вершин графа с m вершинами. Это квадратная матрица , строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент равен числу ребер, идущих из вершины xi  в вершину  xj. Если исходящих дуг нет, то .

4. Заданием матрицы инциденций (инцидентности) графа с m вершинами и n ребрами. Это прямоугольная матрица , строки которой соответствуют вершинам графа, а столбцы – ребрам. Если xi  является началом дуги uj, то ; если xj – конец дуги uj, то . Петле соответствует элемент, равный 2.

Пример.

Ориентированный граф определяется следующим образом: Гх1 = х1, Гх2 = , Гх3 = ,  Гх4 = , Гх5 = х4 ,  Гх6 = х7, Гх7 = .  Записать матрицу смежности и матрицу инциденций.

Решение.

Матрица смежности графа имеет вид:                   Матрица инциденций графа имеет вид:           

                                  

Определение 38. Маршрут – чередующаяся последовательность вершин и ребер (вершины могут повторяться). 

Определение 39. Путем в ориентированном графе от А1 до Аn называется последовательность ориентированных ребер ,…, , т.е. маршрут, такой, что конец каждого предыдущего ребра совпадает с началом следующего и ни одно ребро не встречается более одного раза.

Определение 40. Простым (элементарным) путем в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.

Определение 41. Цепь – последовательность вершин и ребер, образующих путь. Всякий путь – цепь (обратное верно лишь для неориентированных графов, в которых понятие пути и цепи совпадают).

Пример.

Найти число максимальных путей графа с матрицей смежности  А порядка 4:    .

Решение.

Граф состоит из 4-х вершин и 4-х дуг:  (х1, х2), (х2, х3), (х3, х4). Путь х1 u1 х2 u2 х3 u3 x4, длина которого равна 3, является максимальной, следовательно, число максимальных путей равно 1.

Определение 41. Замкнутый путь в ориентированном графе называется ориентированным циклом.

Замечание. Есть и другое определение: если начальная вершина совпадает с конечной, то такой путь называют контуром длины k.

Определение 42. Эйлеровым путем в ориентированном графе называется путь, содержащий все его ориентированные ребра.

Пример.

На рисунке А) изображен эйлеров орграф, так как имеется ориентированный цикл abcdeca, содержащий все его ориентированные ребра. Изменение ориентации в одном ребре, например (c,b) вместо (b,c), превращает этот орграф в неэйлеров (рис. В). В пункт b можно приехать по двум дорогам, но нельзя оттуда выехать.

Определение 43. Длиной пути в ориентированном графе называется число ребер в этом пути.

Замечание. Путь нулевой длины состоит из одной вершины. Путь может быть конечным и бесконечным.

Определение 44. Путь минимальной длины называют кратчайшим путем.

Определение 45. Расстоянием от А до В в ориентированном графе называется длина наикратчайшего пути от А до В.

Замечание. Среди огромного числа задач теории графов отметим следующие три задачи, относящиеся к задачам о кратчайшем пути и имеющие важное прикладное значение. Задача 1. Найти в графе (X, G) путь, ведущий от вершины А к вершине В. Задача 2. Найти путь наименьшей длины, ведущий от А к В. Задача 3. Каждой дуге графа (X, G) отнесем число, которое назовем длиной дуги. Требуется найти путь, ведущий из данной вершины А в данную вершину В такой, что его полная длина была наименьшей.

Определение 46. Полным ориентированным графом называется граф, каждая пара вершин которого соединена в плоскости одним ориентированным ребром.

Теорема  9. Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.

Иногда встречаются графы, часть ребер которых ориентирована, а другая – нет. Такие графы называют смешанными. Смешанный граф можно превратить в ориентированный мультграф, если каждое его неориентированное ребро  заменить двумя ориентированными и противоположно направленными: (а,b) и (b). Примером смешанного графа является сеть городских улиц, если на некоторых улицах установлено одностороннее движение, а на других – двустороннее.

П. 8. Сетевые графы или графики

Рассмотрим пример из повседневной жизни. Строится школа. Как организовать работу, как распределить рабочую силу, финансы, с какого участка взять людей для переделок и т. д. и т.п…., так, чтобы все обошлось максимально дешево? Это задача для специальных графов, с помощью которых можно построить сеть сложного комплекса работ, определить по сети самые ответственные работы, вычислить время завершения всего комплекса, найти резервы времени для отдельных событий и работ.

Определение 47. Всякий намеченный комплекс работ, необходимых для достижения цели, называют проектом.

Проект расчленяется на отдельные работы. Например, если проект – строительство школы, то отдельные работы: подвоз материалов, рытье котлована и т. д. При выполнении комплекса работ всегда можно выделить ряд событий, т. е. итогов какой-то деятельности, позволяющих приступить к выполнению следующих работ.

Если каждому событию поставить в соответствие вершину графа, а каждой работе – ориентированное ребро, то получится граф, отражающий последовательность выполнения работ. А если над ребрами поставить время, необходимое для завершения работы, то получится сеть.

Определение 48. Изображение сети называется сетевым графиком.

Основные правила построения сетевого графика.

  1.  Каждую стрелку на ребре рисуют так, чтобы ее конец находился правее начала, по возможности горизонтально.
  2.  Строят без лишних пересечений.
  3.  Во все вершины, кроме той, которая соответствует исходному событию, должна входить, по меньшей мере, одна стрелка (т. к. все события, кроме исходного, имеют предшествующую работу).
  4.  Из всех вершин, кроме завершающей, должны выходить стрелки.
  5.  Не должно образовываться циклов.
  6.  Если одно событие служит началом для двух и более работ, после завершения которых начинается выполнение следующей работы, то вводится штриховая стрелка и дополнительное событие со своим номером.

Примеры правильного и неправильного построения сетевых графиков.

Определение 49. Путь в сети от исходного события до завершающего называют полным путем (L).

Определение 50. Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на этом пути. (t(L)).

Пример.

Найти продолжительности путей L1, L2, L3 в сетевом графике.

Решение.

t(L1) = 3 + 4 +2 = 9,   t(L2) = 5 + 6 = 11,

t(L3) = 1 + 2 +2 + 3 = 8.

Определение 51. Путь, имеющий наибольшую продолжительность, называется критическим путем.

В примере выше, критический путь L2.

В сети м. б. несколько критических путей.

Определение 52. Работы, лежащие на критическом пути, называются критическими работами.

Обозримость сетевого графика или его частей значительно облегчает восприятие существа всей системы, взаимосвязей всех работ, упрощает весь последующий процесс по руководству системой при ее реализации.

 Замечания.

1. Для отыскания критического пути используются деревья. Например, в генетике они применяются для наглядного описания вероятностей независимых и равновозможных событий, составляющих полную группу.

2. Сети оказываются естественным и удобным средством для описания и анализа сложных проектов. Сетевые модели сложных комплексов работ были разработаны, и начали люди ими пользоваться лишь в 50-ых годах 20 века.

Сетевая модель была применена в США при создании баллистических ракет «Поларис». Сетевой график включал в себя более 10000 событий.

Первая и наиболее распространенная система планирования и управления в США носит название «ПСРТ».  Американские специалисты подсчитали, что сети позволяют на треть сократить продолжительность работ.


 

А также другие работы, которые могут Вас заинтересовать

37521. Наука 20.83 KB
  Проблема начала науки ее возникновения имеет важное методологическое значение для формирования теоретических подходов к определению природы науки ее статуса этапов развития. Античная наука Страна происхождения науки в европейском понимании Древняя Греция. Для этой науки характерна органичная связь с философией.
37522. Сравнительный анализ философских школ 119.35 KB
  Бытие первоначально имеет огонь и является равновесием двух потоков. Все появляется через отдельные промежутки времени. Отношение к рабовладению и роль рабов в государстве В государстве Платона рабство сохраняется в частности одной из задач сословия стражей является ведение завоевательных войн с целью добычи рабов. Если целью правящих является не благо государства а собственный корыстный интерес единолично правящего то монархия вырождается в тиранию.
37525. Основные концепции теории познания и истории философии (эмпиризм, рационализм, иррационализм) 17.74 KB
  Такая философия – это методологическая ориентация познания которая признает основным по источникам и критериям чувственный опыт интегрируемый в материалистический эмпиризм как результат воздействия связей и предметов внешнего мира на человеческие чувства в результате чего они выступают образами этого мира. Иррационализм – это направление философской мысли которое признает основой процесса познания и преобразования мира – внерациональные аспекты духовной жизни человека: интуиция вера воля ограничивая или отрицая возможности разума в этом...
37526. Экзаменационные вопросы по философии с ответами для поступающих в аспирантуру 654.18 KB
  Специфика философского рассмотрения человека. Религиозные учения о сотворении человека. Проблема смысла жизни человека в истории религиозных и философских учений. Свобода и ответственность человека в современном мире.
37527. Философия. Шпаргалки 52.56 KB
  Роль философии определяется прежде всего тем что она выступает в качестве теоретической основы мировоззрения а также тем что она решает проблему познаваемости мира наконец вопросы ориентации человека в мире культуры в мире духовных ценностей. Функции: 1 мировоззренческая с помощью философии у человека формируется мировоззрение. Структура философии: 1Онтология сердцевина онто бытие логосучение фил. Основной вопрос философии метафилософская и историкофилософская концепция согласно которой основной проблемой философии на...
37528. Сравнение человека и животного 23.32 KB
  Отличается ли сознание и мышление животных от сознания и мышления человека Человек обладает абстрактным мышлением у животных предметное мышлениездесь и сейчас У животных нет самозознания. Шеллер утверждал: человек может посмотреть на себя со стороны животное же не выделяет себя из окружающей среды они привязаны к природе Шеллер: точто делает человека человеком есть причины противоположные жизнидух У человека между системой рецепторов и системой эффекторов есть третье звено. Животное на внешний стимул дает прямой непосредственный...
37529. ФИЛОСОФИЯ БЕЛАРУСИ 42.57 KB
  ФИЛОСОФИЯ БЕЛАРУСИ комплекс философских идей и представлений включая социальную философию этику эстетику философское осмысление религиозных атеистических педагогических естественнонаучных и т. взглядов сложившихся в Беларуси с древнейших времен до настоящего времени. выступает как сложный многоэтапный и многовекторный процесс задаваемый спецификой развития Беларуси как страны белорусов как нации белорусской культуры включая ее философскую рефлексию как уникальной самодостаточной целостности в контексте эволюции европейского...