Теория графов - раздел математики, используемый в информатике и программировании, экономике, логистике, химии.
Что такое граф
Часто для описания строения систем используют графические схемы. Элементы в них изображают кружками, точками, квадратами и т. п., а связи между элементами - линиями или стрелками. При этом ни то, как изображаются элементы, ни длина или форма линий не важны - имеет значение только, какие элементы соединены. Итак, граф - это пара вида (A, M), где A - конечное множество вершин, а M - множество ребер - линий, связывающих некоторые вершины.
Основные понятия теории графов
У ориентированного графа или орграфа (см. рисунок ниже) ребра ориентированы, называются дугами и изображаются стрелками. Дуга может быть обозначена упорядоченной парой вершин, которые она связывает, - начальной и конечной.
У неориентированного графа (см. рисунок ниже) ребра изображаются линиями без ориентации. Соответственно, пара вершин, которую связывает ребро, является неупорядоченной. Обе эти вершины есть концы ребра.
Если вершины a и b - концы ребра (или начало и конец дуги) графа, то говорят, что вершины a и b инцидентны этому ребру (дуге), также ребро (дуга) инцидентно вершинам a и b. Если вершины a и b - концы ребра, то они (a и b) называются смежными.
Чаще всего рассматривают графы, ребра которых имеют один тип - являются ориентированными или нет.
Если ребра имеет одинаковые начало и конец, то их называют кратными ребрами, а граф, в котором они присутствуют, называется мультиграфом.
Теория графов также использует понятие «петля» - ребро, выходящее и заходящее в одну и ту же вершину. Граф, в котором есть петли, называется псевдографом.
Чаще всего встречаются неориентированные графы, у которых нет кратных ребер и нет петель. Такие графы называются обыкновенными. Они не имеют кратных ребер, поэтому можно отождествить ребро и соответствующую пару вершин.
Каждая вершина орграфа характеризуется:
- Полустепенью исхода. Это количество дуг, выходящих из нее.
- Полустепенью захода. Это количество дуг, которые входят в данную вершину.
Сумма полустепеней захода орграфа, а также сумма полустепеней исхода равны общему количеству дуг графа.
У неориентированного графа каждая вершина характеризуется степенью вершины. Так называется количество ребер, которые инцидентны вершине. Общая сумма степеней вершин графа есть количество ребер, умноженное на два: каждое ребро будет давать вклад, который равен двум.
Вершина со степенью 0 называется изолированной.
Висячей вершиной является вершина со степенью 1.
Теория графов называет пустым графом такой, в котором нет ни одного ребра. Полный граф - это обыкновенный граф, в котором смежны любые 2 вершины.
Взвешенные графы - это графы, вершинам или ребрам (дугам) которых или и вершинам, и ребрам (дугам) сразу, приписываются некоторые числа. Они называются весами. На втором рисунке показан неориентированный граф, ребра которого взвешены.
Графы: изоморфизм
Понятие изоморфизма используется в математике. В частности, теория графов определяет его так: два графа U и V изоморфны, если в этих графах существует биекция между множествами их вершин: каждые 2 вершины в графе U соединены ребром в том и только том случае, если в графе V связаны ребром те же вершины (которые могут по-другому называться). На рисунке ниже показаны два изоморфных графа, в которых между вершинами, окрашенными в одинаковые цвета и в первом, и во втором графе, существует вышеописанная биекция.
Пути и циклы
Путем в неориентированном или ориентированном графе является последовательность ребер, где каждое следующее начинается в вершине, в которой заканчивается предыдущее. Простой путь - такой, в котором все вершины, исключая, может быть, начальную и конечную, и ребра различны. Циклом в орграфе называется путь, у которого совпадают начальная и конечная вершины и который включает не менее одного ребра. Циклом в неориентированном графе является путь, который содержит не менее трех различных ребер. На втором рисунке циклом является, например, путь (3, 1), (6, 3), (1, 6).
Теория графов в программировании используется для построения граф-схем алгоритмов.
Теория графов – это раздел дискретной математики, изучающий объекты, представимые в виде отдельных элементов (вершин) и связей между ними (дуг, рёбер).
Теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (1707-1783: родился в Швейцарии, жил и работал в России).
Задача о кенигсбергских мостах.
В прусском городке Кенигсберг на реке Прегал семь мостов. Можно ли найти маршрут прогулки, который проходит ровно 1 раз по каждому из мостов и начинается и заканчивается в одном месте?
Граф, в котором найдется маршрут, начинающийся и заканчивающийся в одной вершине, и проходящий по всем ребрам графа ровно один раз, называется Эйлеровым графом.
Последовательность вершин (может быть с повторением), через которые проходит искомый маршрут, как и сам маршрут, называется Эйлеровым циклом .
Задача о трех домах и трех колодцах.
Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) Куратовским (1896 – 1979) в 1930 году.
Задача о четырех красках. Разбиение плоскости на непересекающиеся области называется картой . Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. Гипотеза не доказана до сих пор.
Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера.
Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки…
Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно.
Определение 7.1. Графом G = G (V , E ) называется совокупность двух конечных множеств: V – называемого множеством вершин и множества E пар элементов из V, т.е. EÍV´V, называемого множеством рёбер , если пары неупорядочены, или множеством дуг , если пары упорядочены.
В первом случае граф G (V , E ) называется неориентированным , во втором – ориентированным.
ПРИМЕР. Граф с множеством вершин V = {а,b,с} и множеством ребер Е ={{а, b}, {b, с}}
ПРИМЕР. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},
Если e=(v 1 ,v 2), еÎЕ, то говорят, что ребро е соединяет вершины v 1 и v 2 .
Две вершины v 1 ,v 2 называются смежными , если существует соединяющее их ребро. В этой ситуации каждая из вершин называется инцидентной соответствующему ребру.
Два различных ребра смежны , если они имеют общую вершину. В этой ситуации каждое из ребер называется инцидентным соответствующей вершине.
Число вершин графа G обозначим v , а число ребер - e :
.
Геометрическое представление графов следующее:
1) вершина графа – точка в пространстве (на плоскости);
2) ребро неориентированного графа – отрезок;
3) дуга ориентированного графа – направленный отрезок.
Определение 7.2. Если в ребре e=(v 1 ,v 2) имеет место v 1 =v 2 , то ребро е называется петлёй . Если в графе допускается наличие петель, то он называется графом с петлями или псевдографом .
Если в графе допускается наличие более одного ребра между двумя вершинами, то он называется мультиграфом .
Если каждая вершина графа и (или) ребра помечена, то такой граф называется помеченным (или нагруженным ). В качестве пометок обычно используются буквы или целые числа.
Определение 7.3. Граф G (V , E ) называется подграфом (или частью ) графа G (V ,E ), если V V , E E . Если V = V , то G называется остовным подграфом G .
Пример 7 . 1 . Дан неориентированный граф.
Определение 7.4. Граф называется полным , если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через K n .
Графы К 2 , К 3, К 4 и К 5 .
Определение 7.5. Граф G =G (V , E ) называется двудольным , если V можно представить как объединение непересекающихся множеств, скажем V =A B , так что каждое ребро имеет вид (v i , v j ), где v i A и v j B .
Каждое ребро связывает вершину из А с вершиной из В, но никакие две вершины из А или две вершины из В не являются связанными.
Двудольный граф называется полным двудольным графом K m , n , если A содержит m вершин, B содержит n вершин и для каждого v i A , v j B имеем (v i , v j )E .
Таким образом, для каждого v i A , и v j B имеется связывающее их ребро.
K 12 K 23 K 22 K 33
Пример 7 . 2 . Построить полный двудольный граф K 2,4 и полный граф K 4 .
Граф единичного n -мерного куба В n .
Вершины графа - n-мерные двоичные наборы. Рёбра соединяют вершины, отличающиеся одной координатой.
Пример:
Назад
Вперёд
Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.
Цели урока:
Оборудование:
- компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
- компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
- оборудование доски (тема урока, новые термины). Раздаточный материал.
План урока.
II. Изложение нового материала. (10 мин.)
III. Закрепление материала. Практическая работа. (15-20 мин.)
IV. Подведение итога урока.(2 мин)
V. Домашнее задание.
I. Организационный момент. Актуализация знаний.
Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.
II Изложение нового материала.
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними. Это замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
Граф – это некоторая информационная модель
Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.
Примеры графов (Слайд 4, 5, 6)
Задание 1 (Слайд 7):
Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.
Можно ли долететь на рейсовых ракетах с Земли до Марса?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Две вершины, соединённые дугой или ребром называются смежными. Каждому ребру или дуге соотносится какое-нибудь число. Число может обозначать расстояние между населёнными пунктами, время перехода от одной вершины к другой и т. д.
Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?
Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?
Представление графов (Слайд 12)
Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.
| Списки дуг | Графическая форма | Табличная форма | ||||||||||||||||
| (АВ; 7), |  |
|
III. Закрепление материалы: учащимся предлагается разделить на группы и выполнить задания. Работая в малой группе, ученики обсуждают модели, основываясь на теоретических знаниях, полученных в начале урока. Тем самым достигается повторение и закрепление материала.
Задание 2 (Слайд 13)
IV. Итог урока
Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)
Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)
Что обозначают ребра графа (Пути, движения, направления)
Приведите пример, где в жизни мы можем с ними встретиться?
Как изображаются графы?
V. Домашнее задание. (Слайд 15)
Основные понятия теории графов.
Примеры использования теории графов.
История возникновения теории графов.
Мы частенько рисуем на листочках бумаги кружочки, квадратики, точки обозначая ими людей, населённые пункты, дела которые мы должны сделать и тому подобное, и соединяем их прямыми и ломаными линями, стрелочками которыми обозначаем связи между ними, отношения, последовательность действий и тому подобное.
Такие схемы встречаются всюду под разными названиями: социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т.д.
Д.Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства.
В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "analysis situs"; понятие "точки сочленения", с давних пор известное в социологии, впоследствии появилось в электронике; все примеры такого рода перечислить невозможно. Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной.
В действительности такие основные понятия, как "цепь", "путь", "центр", будучи определены абстрактно, остаются в то же время неразрывно связанными с графической реальностью и легко распознаются, когда схема начерчена.
Рассматривая теорию графов, мы не ставим целью дать в руки математическое средство, наша задача сформировать общее представление прежде всего о её прикладных возможностях в теории организации управления.
Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, кибернетика, общая теория систем, общая теория организаций, генетика, психология, социология, экономика, антропология и лингвистика и другие науки.
Эта теория тесно связана также со многими разделами математики, среди которых - теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ.
Теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем.
Теория графов «открывалась» независимо много раз: её с полным основанием можно считать разделом прикладной математики. В самом деле, наиболее раннее известное упоминание этой теории встречается в работах Эйлера, и хотя проблему, которой он занимался, можно рассматривать как обычную головоломку, псе же она возникла из практики.
Последующие переоткрытия теории графов Кирхгофом и Кэли также уходят своими корнями в реальную действительность. Изучение Кирхгофом электрических цепей привело к разработке им основных понятий и получению ряда теорем, касающихся деревьев в графах. В свою очередь Кэли подошел к исследованию деревьев, решая задачи перечисления органических изомеров.
Другой подход к графам, связанный с рассмотрением головоломок, был предложен Гамильтоном. После этого появилась знаменитая гипотеза четырёх красок, которая до сих пор пользуется широкой известностью.
В наше столетие также было чрезвычайно много переоткрытий теории графов. Упомянем кратко некоторые из них, придерживаясь хронологического порядка.
Задача о кёнигсбергских мостах
Отцом теории графов (так же как и топологии) является Эйлер (1707-1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов.
В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке.
Задача состояла в следующем: найти маршрут прохождении всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.
Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей.
Вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.
Рисунок 1. Парк в городе Кенигсберге, 1736 г.
Рисунок 2. Граф к задаче о кенигсбергских мостах
Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки.
Получился «граф». Этот граф показан на рисунке 2., где точки отмечены теми же буквами, что и четыре части суши.
Утверждение о несуществовании «положительного» решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рисунке.
Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и нашел критерий существования обхода (специального маршрута) у данного графа, а именно граф должен быть связным и каждая его вершина должна быть инцидентна (принадлежать) четному числу ребер.
Граф, показанный на рисунке, связный, но не каждая его вершина инцидентна (принадлежит) четному числу ребер.
Электрические цепи
В 1847 г. Кирхгоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике (дуге) и в каждом контуре рассматриваемой электрической цепи.
Будучи физиком по образованию, он подходил к решению задач как математик. Абстрагируясь от электрических схем и цепей, которые содержат сопротивления, конденсаторы, индуктивности и т. д., он рассматривал соответствующие комбинаторные структуры, содержащие только вершины и связи (ребра или дуги), причем для связей не нужно указывать, каким типам электрических элементов они соответствуют.
Таким образом, в действительности Кирхгоф заменил каждую электрическую цепь соответствующим ей графом и показал, что для решения системы уравнений необязательно рассматривать в отдельности каждый цикл графа электрической цепи.
Рисунок 3. Сеть N, соответствующий ей граф G .
Вместо этого он предложил простую, но эффективную методику (ставшую позднее стандартной процедурой), в соответствии с которой достаточно ограничиться только независимыми простыми циклами графа, определяемыми любым из его «остовных деревьев». На рисунке 3 дан пример электрической цепи N, соответствующего ей графа G.
Химические изомеры
Занимаясь чисто практическими задачами органической химии, Кэли в 1857 г. открыл важный класс графов, называемых деревьями.
Он стремился перечислить изомеры предельных (насыщенных) углеводородов С n Н 2 n + 2 с данным числом n атомов углерода; рисунок 4.
Рисунок 4. Изобутан
В социальной психологии.
В 1936 г. психолог Курт Леви н высказал предположение, что «жизненное пространство» индивидуума можно представить с помощью планарной карты 1).
На такой карте области представляют различные типы деятельности человека, например, то, что он делает на работе, дома, или же его хобби.
Рисунок 5. Карта и соответствующий ей граф.
Подчеркнем, что К.Леви н фактически имел дело с графами, как это видно из рисунка 5.
Эта точка зрения привела психологов Научно-исследовательского центра групповой динамики к другой психологической интерпретации графа, в которой люди представляются вершинами, а их отношения - ребрами. Такими отношениями являются, например, любовь, ненависть, общение, подчинение.
Предположение Левина относится только к планарным картам, поскольку он всегда рисовал свои рисунки на плоскости. В последствии идея К.Левина была развита в социометрических процедурах.
В теории организаций
Графы могут быть представлены не только в строгой классической форме. Так жизненный цикл компании И.Адизеса представлен следующим форме.
Рисунок 6. Жизненный цикл компании
Функциональная организационная структура построена по принципу распределения функций внутри организации и создания сквозных подструктур по управлению функциями.
Производственные подразделения
Рис. Функциональная организационная структура
Таким образом, необходимость специальной общей теории, применимой в любой сфере жизнедеятельности человека была обусловлена потребностями практики.
Такой теорией стала «Теория графов».
Основные понятия теории графов
Начнём с определения, однозначного определения теория графов не имеет, ниже представлены три определения, но существуют и другие.
Теория графов - раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами.
Теория графов - раздел математики, особенность которого - геометрический подход к изучению объектов
Теория графов - математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.
Теория графов - это один из подразделов математики, главным отличительным признаком которого является геометрический метод в изучении объектов. Основателем ее принято считать Л. Эйлера.
Применение теории графов до конца 19 века сводилось к решению занимательных задач и не привлекало значительного всеобщего внимания. Начиная с 20 века, когда теория графов сформировалась в самостоятельную математическую дисциплину, она нашла широкое применение в таких областях науки, как кибернетика, физика, логистика, программирование, биология, электроника, транспортные и коммуникационные системы.
Основные понятия теории графов
Базовым является граф. В терминологии можно встретить такое понятие, как сеть, идентичное графу. Последнее - это непустое количество точек, то есть вершин, и отрезков, то есть ребер, оба конца которых соответствуют заданному количеству точек. Теория графов не вкладывает определенного смысла в значения ребер и вершин. Например, города и соединяющие их дороги, где первые - это вершины графа, а вторые - ребра. Большее значение в теории уделяется дугам. Если у ребра есть направление, то оно имеет название дуги, если граф с ориентированными ребрами, он называется орграфом.
В терминологии теории так же выделяют следующие понятия:
Подграфом называется граф, все ребра и вершины которого находятся среди вершин и ребер.
Связный граф - тот, у которого для двух разных вершин существует соединяющая их цепь.
Взвешенный связный граф - тот, у которого задана весовая функция.
Дерево - связный граф, без циклов.
Остов - подграф, являющийся деревом.
При изображении графа на плоскости используется определенная система обозначений: выбранной вершине соответствует точка на простейшей поверхности, и если между вершинами находится ребро, то соответствующие точки объединяются отрезком. Если же граф ориентированный, эти отрезки заменяются стрелками.
Но не стоит сравнивать изображение графа с ним самим, т.е с абстрактной структурой, потому что одному графу можно придать не одно графическое представление. Рисунок на плоскости дан для того, чтобы увидеть, какие пары вершин объединяются ребрами, а какие нет.
Среди некоторых задач теории графов выделяют:
- Задача о кротчайшей цепи (замена оборудования, размещение мест скорой помощи и телефонных станций).
- Задача о максимальном потоке (упорядочение движения в динамической сети, распределение работ, организация пропускной способности).
- Задача о покрытиях и упаковках (размещение диспетчерских пунктов).
- Раскраска в графах (размещение памяти на электронно-вычислительных машинах).
- Связь сетей и графов (создание коммуникационной сети, анализ сетей связи).
В настоящее время невозможно программировать большинство задач без знания теории графов. Это облегчает и упрощает работу с ЭВМ.
Программирование использует множество структур и универсальных методов для решения задач, и одним из них является теория графов. Ее значение сложно переоценить. Теория графов в программировании позволяет упростить поиск информации, оптимизировать программы, преобразовать и распределить данные. Благодаря алгоритмам теории возникает возможность применения и их оценки в использовании для решения конкретных задач, осуществлять модификацию алгоритма, не уменьшая степени математической достоверности конечного варианта программы.
Важным свойством управляющей системы или модели является совокупность при наборе действий и единиц данных. Эти структуры являются единственными частями программ и преобразующейся ими информации. Поэтому графы являются основой конструкцией для программиста.