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

Теория Графов. Часть 1 Введение и классификация графов

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

Введение

Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.

Схема Московского метро

Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.

Отмечу, что число вершин обозначается буквой n:

Число рёбер обозначается буквой m:

Таким образом граф задается и обозначается парой V,E:

Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)

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

Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.

Нулевой граф

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

Множество E задается парой неупорядоченных вершин множества V.

Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =

Граф будет выглядеть следующим образом:

Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.

Степень записывают, как:

Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:

Формула суммы степеней для G = V,E выглядит так:

То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!

А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:

Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?

Классификации графов

Первым признаком классификации является отсутствие или наличие ориентации у ребер.

Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.

Неориентированный граф

Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.

Ориентированный граф

Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.

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

Вторым признаком является отсутствие или наличие кратных ребер.

Мультиграф

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

Заключение

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

Источник

Планарный граф

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

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

Содержание

Два примера непланарных графов

Здесь мы пользуемся интуитивным понятием слова «линия», подробнее см. в соответствующей статье.

Полный граф с пятью вершинами

Лемма. Полный граф с пятью вершинами (К₅) нельзя уложить на плоскость.

«Домики и колодцы»

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

Лемма. Полный двудольный граф с тремя вершинами в каждой из долей (К_3,3) нельзя уложить на плоскость.

Теорема Понтрягина-Куратовского

Очевидно утверждение: если граф G содержит подграф, гомеоморфный K₅ или K_3,3, его невозможно разложить на плоскости. Оказывается, верно и обратное.

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу из пяти вершин (K₅) или графу «домики и колодцы» (K_3,3).

Теорему также можно сформулировать в следующем варианте (иногда его называют «теорема Вагнера»).

Граф планарен тогда и только тогда, когда не содержит подграфов, стягивающихся в K₅ или K_3,3.

Признаки непланарных графов

Формула Эйлера

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

Оно было найдено Эйлером в 1736 г. [1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум. Формула имеет множество полезных следствий. Если каждая грань ограничена не менее чем тремя ребрами (при условии, что в графе больше двух ребер), а каждое ребро разделяет две грани, то

то есть, при большем числе ребер такой граф заведомо непланарен. Обратное утверждение не верно, например, граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

Планарные графы в задачах

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

Спрямление графа. Любой плоский граф можно перерисовать так, чтобы он остался плоским, а рёбра стали прямолинейными.

См. также

Примечания

Ссылки

Полезное

Смотреть что такое «Планарный граф» в других словарях:

планарный граф — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN planar graph … Справочник технического переводчика

ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия

Граф Петерсена — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей … Википедия

Плоский граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

плоский граф — планарный граф — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы планарный граф EN flat graph … Справочник технического переводчика

Двудольный граф — Биграф Двудольный граф или биграф это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что ка … Википедия

Планарность — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия

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

Гамма-алгоритм — Гамма алгоритм алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация … Википедия

Источник

СОДЕРЖАНИЕ

Теоремы Куратовского и Вагнера

Вместо того, чтобы рассматривать подразделения, теорема Вагнера имеет дело с несовершеннолетними :

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

Другие критерии планарности

На практике трудно использовать критерий Куратовского, чтобы быстро решить, является ли данный граф плоским. Однако существуют быстрые алгоритмы решения этой проблемы: для графа с n вершинами можно определить за время O ( n ) (линейное время), может ли граф быть плоским или нет (см. Проверка планарности ).

Для простого связного плоского графа с v вершинами, e ребрами и f гранями для v ≥ 3 выполняются следующие простые условия :

Формула Эйлера

Средняя степень

Графики монет

Плотность планарного графика

Связанные семейства графов

Максимальные плоские графы

Внешнепланарные графы

Графики Халина

Другие родственные семьи

Перечисление планарных графов

Почти все плоские графы имеют экспоненциальное число автоморфизмов.

Другие факты и определения

Теорема о четырех цветах утверждает, что каждый планарный граф можно раскрашивать в четыре цвета (т. Е. С четырьмя частями).

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

Хотя дуальный, построенный для конкретного вложения, уникален (с точностью до изоморфизма ), графы могут иметь разные (т. Е. Неизоморфные) дуальные, полученные из разных (т. Е. Негомеоморфных ) вложений.

Теорема о плоском разделителе утверждает, что любой планарный граф с n вершинами можно разбить на два подграфа размером не более 2 n / 3 путем удаления O ( √ n ) вершин. Как следствие, планарные графы также имеют ширину дерева и ширину ветвления O ( √ n ).

Для двух плоских графов с v вершинами можно определить за время O ( v ), изоморфны они или нет (см. Также проблему изоморфизма графов ).

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

Источник

Простейшие понятие о графах. Представления графов в памяти, классические алгоритмы.

Введение

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

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

Леонард Эйлер и задача о Кёнигсберских мостах

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

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

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

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

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

Проблема четырёх красок

Проблема четырёх красок — математическая задача, предложенная Гутри в 1852 году.

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

Иначе говоря, показать что хроматическое число плоского графа не превосходит 4.

О доказательстве

К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Определения теории графов

Граф — конечное множество вершин, природа которых не важна, и конечно множество рёбер, соединяющих между собой какие-либо вершины.

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

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

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

Граф, в котором каждая пара вершин соединена ребром, называется полным. Обозначение: K_n – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали.

Ниже приведены полные графы с числом вершин от 1 до 8 и количества их рёбер.

K1 : 0	K2 : 1	K3 : 3	K4 : 6
K5 : 10	K6 : 15	K7 : 21	K8 : 28

Степенью вершины называется число ребер, которым принадлежит вершина (число рёбер с концом в данной вершине).

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

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

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

Понятия плоского графа и грани графа применяется при решении задач на «правильное» раскрашивание различных карт.

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

Циклом называется путь, в котором совпадают начальная и конечная точка (т.е. можно «ходить по циклу» — «ходить по кругу»).

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

Длиной пути, проложенного на цикле, называется число ребер этого пути.

Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

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

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

Если не выделять особым образом корень, то дерево — это просто любой связный граф, не имеющий циклов

Представление графов в памяти

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

Матрица смежности

Самый простой способ сохранить граф в памяти — матрица смежности. Нарисуем таблицу, которая чем-то напоминает таблицу умножения: в первой строчке и в первом столбце будут стоять номера (или любые названия) вершин, а на пересечении столбца и строки будем ставить, например, 1 если между этими вершинами есть ребро и 0 если нет. Кроме 1 и 0 можно ставить, например, вес ребра, а для обозначения отсутствия ребра — просто очень большое число. Какой именно вариант использовать, зависит от каждой конкретной задачи. Также задача определяет, что ставить на диагонали получившейся матрицы.

Граф и его матрица смежности.

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

Напишем функцию, считывающую граф как матрицу смежности:

Список смежности

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

Посмотрим, как это пишется на Python с тем же форматом входных данных:

Другие способы

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

Основные задачи теории графов

Обходы графа

Часто требуется обойти все вершины графа в определённом порядке, например, для проверки его на связность или упорядочения задач при планировании (топологическая сортировка графа). Существует два стандартных метода обхода графа — обход в глубину и обход в ширину.

Обход в глубину (DFS)

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

Напишем функцию dfs на языке Python с использованием списков смежности:

Обход в ширину (BFS)

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

Этот обход, как и обход DFS, можно применять для поиска путей в графах. Основное его отличие в том, что поиск не уходит сразу далеко от начала, а продвигается вглубь графа постепенно, неким «фронтом».

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

Поиск кратчайших путей

Рассмотрим самый простой алгоритм поиска пути — алгоритм Флойда. Его преимущества состоят в том, что он реализуется очень легко, может работать с рёбрами отрицательного веса и одновременно находит кратчайшие пути между всеми парами вершин. Алгоритм Флойда — один из немногих алгоритмов, которые лучше работают с матрицей смежности, чем со списками рёбер. Алгоритм последовательно изменяет матрицу смежности, превращая её в матрицу кратчайших путей — в каждой клетке матрицы остаётся длина (сумма весов) кратчайшего пути между соответствующей парой вершин. Условие работы алгоритма — если между какой-то парой вершинам нет ребра, в исходной матрице смежности в этой клетке должна стоять «бесконечность», обычно это число, заведомо больше весов всех рёбер в данной задаче.

Посмотрим, как реализовать этот алгоритм на Python:

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

Алгоритм Дейкстры будет рассматриваться на зимней очной сессии.

Другие задачи

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

Источник