Проект по дисциплине: «Дискретная математика» на тему: «Применение графов для составления и решения задач планирования и управления»

Цели и задачи: Основными целями и задачами моего проекта является изучение применения графов для составления и решения задач планирования и управления Основными целями и задачами моего проекта является изучение применения графов для составления и решения задач планирования и управления

Содержание 1 Основные понятия 1.1 Граф 1.2 Ориентированный граф 1.3 Смешанный граф 1.4 Прочие связанные определения 1.5 Дополнительные характеристики графов 2. Способы представления графа в информатике 2.1 Матрица смежности 2.2 Матрица инцидентности 2.3 Список рёбер 3 Обобщение понятия графа

1 Основные понятия 1.1 Граф 1.2 Ориентированный граф 1.3 Смешанный граф 1.4 Прочие связанные определения 1.5 Дополнительные характеристики

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

Пример графа

Виды графов: 1. Неориентированный граф 2. Ориентированный граф

1.1 Неориентированный граф Неориентированный граф G это упорядоченная пара G: = (V,E), для которой выполнены следующие условия: V это множество вершин или узлов, E это множество пар (в случае неориентированного графа неупорядоченных) вершин, называемых рёбрами. V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств. Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину. Два ребра называются кратными, если множества их концевых вершин совпадают. Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды). Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

1.2 Ориентированный граф Ориентированный граф (сокращённо орграф) G это упорядоченная пара G: = (V,A), для которой выполнены следующие условия: Ориентированный граф (сокращённо орграф) G это упорядоченная пара G: = (V,A), для которой выполнены следующие условия: V это непустое множество вершин или узлов, V это непустое множество вершин или узлов, A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами. A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами. Дуга это упорядоченная пара вершин (v, w), где вершину v называют началом, а w концом дуги. Можно сказать, что дуга ведёт от вершины v к вершине w.

1.3 Смешанный граф Смешанный граф G это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше. Смешанный граф G это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного. Ориентированный и неориентированный графы являются частными случаями смешанного.

Смешанный граф

1.4 Прочие связанные определения Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром. Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром. Ориентированным путём в орграфе называют конечную последовательность вершин vi, для которой все пары (vi,vi + 1) являются (ориентированными) рёбрами. Ориентированным путём в орграфе называют конечную последовательность вершин vi, для которой все пары (vi,vi + 1) являются (ориентированными) рёбрами. Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия. Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

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

Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v», является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины. Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v», является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины. Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов Ребро графа называется мостом, если его удаление увеличивает число компонент. Ребро графа называется мостом, если его удаление увеличивает число компонент.

1.5 Дополнительные характеристики графов Граф называется: связным, если для любых вершин u,v есть путь из u в v. связным, если для любых вершин u,v есть путь из u в v. сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь. сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь. деревом, если он связный и не содержит простых циклов. деревом, если он связный и не содержит простых циклов. полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром. полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром. двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2. двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2. k-дольным, если его вершины можно разбить на k непересекающихся подмножества V1, V2, …, Vk так, что не будет рёбер, соединяющих вершины одного и того же подмножества. k-дольным, если его вершины можно разбить на k непересекающихся подмножества V1, V2, …, Vk так, что не будет рёбер, соединяющих вершины одного и того же подмножества. полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества. полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества. планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер. планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер. взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра. взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.

2. Способы представления графа в информатике 2.1 Матрица смежности 2.2 Матрица инцидентности 2.3 Список рёбер

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

2.2 Матрица инцидентности Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается: 1 в случае, если связь j «выходит» из вершины i, 1 в случае, если связь j «выходит» из вершины i, 1, если связь «входит» в вершину, 1, если связь «входит» в вершину, 0 во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине) 0 во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине) Данный способ является самым ёмким (размер пропорционален | E | | V | ) и неудобным? для хранения, но облегчает нахождение циклов в графе.

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

3 Обобщение понятия графа Под данное выше определение не подходят некоторые другие обобщения: гиперграф если ребро может соединять более двух вершин. гиперграф если ребро может соединять более двух вершин. ультраграф если между элементами xi и uj существуют бинарные отношения инцидентности. ультраграф если между элементами xi и uj существуют бинарные отношения инцидентности.

Под данное выше определение не подходят некоторые другие обобщения: гиперграф если ребро может соединять более двух вершин. гиперграф если ребро может соединять более двух вершин. ультраграф если между элементами xi и uj существуют бинарные отношения инцидентности. ультраграф если между элементами xi и uj существуют бинарные отношения инцидентности.

Простой граф является одномерным симплициальным комплексом. Более абстрактно, граф можно задать как тройку, где V и E некоторые множества (вершин и рёбер, соотв.), а функция инцидентности (или инцидентор), сопоставляющая каждому ребру (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются: ориентированные графы (орграфы) когда всегда является упорядоченной парой вершин; ориентированные графы (орграфы) когда всегда является упорядоченной парой вершин; неориентированные графы когда всегда является неупорядоченной парой вершин; неориентированные графы когда всегда является неупорядоченной парой вершин; смешанные графы в котором встречаются как ориентированные, так и неориентированные рёбра и петли; смешанные графы в котором встречаются как ориентированные, так и неориентированные рёбра и петли; Эйлеровы графы граф в котором существует циклический эйлеров путь (Эйлеров цикл). Эйлеровы графы граф в котором существует циклический эйлеров путь (Эйлеров цикл). мультиграфы графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин; мультиграфы графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин; псевдографы это мультиграфы, допускающие наличие петель; псевдографы это мультиграфы, допускающие наличие петель; простые графы не имеющие петель и кратных рёбер. простые графы не имеющие петель и кратных рёбер.

Кёнигсберга 4 История семи мостов Кёнигсберга Выводы Леонардо Эйлера «Решение» Кайзера 4.1 Выводы Леонардо Эйлера 4.2 «Решение» Кайзера

История семи мостов Кёнигсберга Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно. Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

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

На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин. Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. Граф кёнигсбергских мостов имел четыре нечётные вершины (т.е. все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

7 мостов Кёнигсберга Граф кёнигсбергских мостов Старинная карта Кёнигсберга.

«Решение» Кайзера На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и соединявший остров Ломзе с южной стороной. Своему появлению этот мост обязан самой задаче Эйлера-Канта. А произошло это вот как. Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали мост кайзера. А задачу с восемью мостами теперь мог решить даже ребёнок. На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и соединявший остров Ломзе с южной стороной. Своему появлению этот мост обязан самой задаче Эйлера-Канта. А произошло это вот как. Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали мост кайзера. А задачу с восемью мостами теперь мог решить даже ребёнок.

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