Главная » Дизайн кухни » Структура тех процессов и систем теория графов. История возникновения теории графов. Основные понятия теории графов

Структура тех процессов и систем теория графов. История возникновения теории графов. Основные понятия теории графов

Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.

Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями - пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо - граф.

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

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

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

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

Основные определения
Графы, как уже отмечалось в примерах, есть способ „визуализации" связей между определенными объектами. Связи эти могут быть „направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.
Способы представления
До сих пор мы задавали ориентированные и неориентированные графы, изображая их с помощью рисунков. Можно задать граф как пару множеств, следуя определению, однако этот способ довольно громоздкий и представляет, скорее, теоретический интерес. Развитие алгоритмических подходов к анализу свойств графов требует иных способов описания графов, более пригодных для практических вычислений, в том числе с использованием ЭВМ. Рассмотрим три наиболее распространенных способа представления графов.
Деревья
Определение 5.5. Неориентированным деревом называют связный и ациклический неориентированный граф. Определение 5.6. Ориентированным деревом называют бесконтурный ориентированный граф, у которого полустепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0.
Остовное дерево наименьшего веса
Следующая задача известна в теории графов под названием задачи Штейнера: на плоскости заданы п точек; нужно соединить их отрезками прямых таким образом, чтобы суммарная длина отрезков была наименьшей.
Методы систематического обхода вершин графа
Важными задачами теории графов являются задачи глобального анализа как неориентированных, так и ориентированных графов. К этим задачам относятся, например, задачи поиска циклов или контуров, вычисление длин путей между парами вершин, перечисление путей с теми или иными свойствами и т.п. Глобальный анализ графа следует отличать от локального, примером которого может служить задача определения множеств предшественников и преемников фиксированной вершины ориентированного графа.
Задача о путях во взвешенных ориентированных графах
Изоморфизм графов
Для ориентированного графа (V, Е) множество Е дуг можно рассматривать как график бинарного отношения непосредственной достижимости, заданного на множестве вершин. В неориентированном графе (V, Е) множество Е ребер является множеством неупорядоченных пар. Для каждой неупорядоченной пары {u, v} ∈ Е можно считать, что вершины u и v связаны симметричным бинарным отношением р, т.е. (u, v) ∈ р и (v, u) ∈ р.
Топологическая сортировка
Определение 5.17. Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф*. Поскольку сеть является бесконтурным графом, можно показать, что существуют вершины (узлы) сети с нулевой полустепенью исхода, а также вершины (узлы) с нулевой полустепенью захода. Первые называют стоками или выходами сети, а вторые - источниками или входами сети.
Элементы цикломатики
При обсуждении алгоритма поиска в глубину в неориентированном графе рассматривался вопрос о поиске так называемых фундаментальных циклов графа. При этом под фундаментальным понимался цикл, содержащий в точности одно обратное ребро, и между фундаментальными циклами и обратными ребрами устанавливалось взаимно однозначное соответствие, фундаментальные циклы возникают всякий раз, как только фиксировано произвольное разбиение всех ребер неориентированного графа на древесные (формирующие некоторый максимальный оспьовный лес исходного графа) и обратные, причем в общем случае это разбиение может быть задано совершенно независимо от алгоритма поиска в глубину. Поиск в глубину есть лишь один из способов реализации такого разбиения.

Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день.

О курсе

Этот курс служит введением в современную теорию графов. Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В нашем курсе мы, конечно же, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.

Формат

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

Информационные ресурсы

В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009.
А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969.
М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984.
M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
B. Bollobás. Modern Graph Theory. Springer, 1998.
J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.

Требования

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

Программа курса

Понятие графа и виды графов.
Различные применения графов: от Кенигсберских мостов до Интернета.
Связность графа, подграфы и степень вершины.
Эквивалентные определения деревьев.
Планарность и критерий Куратовского
Формула Эйлера.
Хроматическое число планарного графа.
Перечисление деревьев: код Прюфера и формула Кэли.
Формула для числа унициклических графов.
Эйлеровы циклы и критерий эйлеровости.
Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
Паросочетания. Теорема Холла и Кенига.
Экстремальная теория графов. Теорема Турана.
Аналог теоремы Турана для графов на плоскости.
Теория Рамсея. Знакомства среди шести человек.
Определение числа Рамсея.
Нижняя и верхняя оценки чисел Рамсея.

Результаты обучения

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

Теория графов - раздел математики, используемый в информатике и программировании, экономике, логистике, химии.

Что такое граф

Часто для описания строения систем используют графические схемы. Элементы в них изображают кружками, точками, квадратами и т. п., а связи между элементами - линиями или стрелками. При этом ни то, как изображаются элементы, ни длина или форма линий не важны - имеет значение только, какие элементы соединены. Итак, граф - это пара вида (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).

Теория графов в программировании используется для построения граф-схем алгоритмов.

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

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

История возникновения теории графов.

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

Такие схемы встречаются всюду под разными названиями: социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т.д.

Д.Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства.

В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "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. Жизненный цикл компании

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