Графы дискретная математика кратко
Обновлено: 03.07.2024
Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.
Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.
С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями — пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо — граф.
Графы служат удобным средством описания связей между объектами. Ранее мы уже использовали графы как способ наглядного представления конечных бинарных отношений. Но граф используют отнюдь не только как иллюстрацию. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда от пункта А до пункта Б. Если таких маршрутов окажется несколько, хотелось бы выбрать в определенном смысле оптимальный, например самый короткий или самый безопасный. Для решения задачи выбора требуется проводить определенные вычисления над графами. При решении подобных задач удобно использовать алгебраическую технику, да и само понятие графа необходимо формализовать.
Методы теории графов широко применяются в дискретной математике. Без них невозможно обойтись при анализе и синтезе различных дискретных преобразователей: функциональных блоков компьютеров, комплексов программ и т.д.
В настоящее время теория графов охватывает большой материал и активно развивается. При ее изложении ограничимся только частью результатов и основной акцент сделаем на описании и обосновании некоторых широко распространенных алгоритмов анализа графов, которые применяются в теории формальных языков.
Графы, как уже отмечалось в примерах, есть способ "визуализации" связей между определенными объектами. Связи эти могут быть "направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.
Построение математического определения графа осуществляется путем формализации и "объектов", и "связей" как элементов некоторых (как правило, конечных) множеств.
Неориентированные графы
Неориентированный граф , где считаем, что , то говорят, что ребро .
Вершины , называют смежными, а также концами ребра . Если всех инцидентных ей ребер.
Для вершины называют множеством смежных с .
Цепь в неориентированном графе , такая, что для любого существует. (Под конечной последовательностью понимается кортеж вершин.)
Для конечной цепи число называют длиной цепи. Таким образом, длина цепи есть число ее ребер, т.е. всех ребер, соединяющих вершины и . Цепь длины 0 — это произвольная вершина графа.
Говорят, что вершина такая, что (при этом говорят также, что данная цепь соединяет вершины , соединяющая Простая цепь — это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра попарно различны.
Простую цепь ненулевой длины с совпадающими концами называют циклом.
Произвольную цепь ненулевой длины с совпадающими концами, все ребра которой попарно различны, будем называть замкнутой цепью.
Неориентированный граф, не содержащий циклов, называют ациклическим графом .
Ориентированные графы
Ориентированный граф , где , элементы которого называют дугами.
Если дуга , то говорят, что дуга .
Вершины в вершину , называют сиежнылси, причем м называют началом, а . Дугу, начало и конец которой есть одна и та же вершина, называют петлей. Если называют заходящей в вершину заходящих в нее дуг, а полустепенью исхода вершины исходящих из нее дуг. Степень вершины , — это сумма полустепеней захода и исхода.
Для вершины называют множеством преемников вершины — множеством предшественников вершины
Путь в ориентированном графе , такая, что для любого существует.
Для конечного пути число называют длиной пути . Тем самым длина пути есть число его дуг, т.е. всех дуг, которые ведут из вершины в вершину . Путь длины 0 — это произвольная вершина графа.
Говорят, что вершина . такой, что (при этом говорят, что данный путь ведет из вершины в ориентированном графе. Оно является рефлексивно-транзитивным замыканием отношения непосредственной достижимости.
Отношение достижимости в ориентированном графе рефлексивно и транзитивно, но в общем случае не антисимметрично: если две вершины ориентированного графа достижимы одна из другой, то из этого вовсе не следует, что они совпадают. Таким образом, отношение достижимости в ориентированном графе есть отношение предпорядка.
Если существует путь ненулевой длины, ведущий из , ведущий из Простой путь — это путь, все вершины которого, кроме, быть может, первой и последней, попарно различны.
Простой путь ненулевой длины, начало и конец которого совпадают, называют контуром.
Произвольный путь ненулевой 1 длины, начало и конец которого совпадают, будем называть замкнутым путем.
Ориентированный граф, не содержащий контуров, называют бесконтурным графом .
Замечание 5.1. Требование, чтобы все ребра простой цепи неориентированного графа были попарно различными, существенно. Если его снять, то цепь вида , где проходится дважды в противоположных направлениях, хотя такую цепь естественно циклом не считать. Не будет эта цепь в соответствии с принятой терминологией и замкнутой цепью.
В неориентированном графе на рис. 5.1 цепь Замечание 5.2. В общем случае в ориентированном графе пересечение множества преемников вершины ее предшественников будет не пусто, если есть петля .
Пример 5.1. Рассмотрим неориентированный граф, изображенный на рис. 5.2. Он задается множеством вершин
и множеством неупорядоченных пар .
В этом графе последовательность вершин есть простая цепь, а последовательность — цепь, не являющаяся простои, поскольку в ней есть совпадающие ребра. Последовательность вершин не является цепью, поскольку в графе нет ребра . Последовательность есть цикл, а последовательность — цепь с совпадающими концами, но не цикл, поскольку эта цепь не является простой. Эта цепь не будет и замкнутой, так как в ней есть повторяющееся ребро .
Степени вершин графа следующие:
Вершины попарно достижимы и образуют класс эквивалентности по отношению достижимости. Для вершин и имеет место , и они также образуют класс эквивалентности. Заметим, что вершина V7, по определению, образует цепь длины 0 и эквивалентна по отношению достижимости только самой себе.
Пример 5.2. Обратимся к ориентированному графу, изображенному на рис. 5.3. Он задается множеством вершин и множеством дуг
В этом ориентированном графе последовательность вершин есть простой путь, а последовательность вершин — путь, не являющийся простым, поскольку в нем, например, два раза встречается вершина, не служащая началом и концом пути.
Последовательность вершин есть контур, а последовательность — замкнутый путь, но не контур, поскольку вершина , не являющаяся началом пути, встречается два раза. Последовательность вершин не задает путь, так как в рассматриваемом ориентированном графе нет дуги .
Полустепени захода, полустепени исхода и степени у вершин следующие:
Свойства отношения достижимости в графах
Отношение достижимости в неориентированных и ориентированных графах обладает следующим важным свойством.
Теорема 5.1. Для любой цепи, соединяющей две вершины неориентированного графа, существует простая цепь, соединяющая те же вершины. Для любого пути, ведущего из вершины
Пусть вершины . Если цепь простая, то доказывать нечего. Пусть существует внутренняя (не совпадающая ни с одним из концов) вершина , которая повторяется в этой цепи, т.е. . Это значит, что вершина ) с совпадающими концами (рис. 5.5). Удалим все вершины и ребра цепи , соединяющую вершины . Если цепь простая, то утверждение доказано. В противном случае поступаем с ней так же, как и с цепью . В силу конечности множества вершин и ребер графа после конечного числа шагов получим простую цепь, соединяющую вершины Следствие 5.1. Если вершина неориентированного графа содержится в некоторой замкнутой цепи, то она содержится и в некотором цикле. Если вершина ориентированного графа содержится в некотором замкнутом пути, то она содержится и в некотором контуре.
Замечание 5.3. Следствие 5.1 перестает быть верным для произвольной цепи с совпадающими концами. Например, для неориентированного графа, состоящего из двух вершин и единственного ребра цепь с совпадающими концами не содержит цикла.
Подграфы неориентированных и ориентированных графов
Перейдем теперь к понятию подграфа. Формулируется это понятие одновременно для неориентированных и ориентированных графов (с учетом различий в терминологии).
Определение 5.1. Неориентированный (ориентированный) граф называют подграфом неориентированного (ориентированного) графа , если и .
Будем использовать обозначение , аналогичное обозначению включения для множеств.
Замечание 5.4. Так как в определении 5.1 пара есть неориентированный (ориентированный) граф, то для любого ребра (дуги ) предполагается, конечно, что , поскольку иначе пару нельзя будет считать неориентированным (ориентированным) графом.
Если хотя бы одно из указанных двух включений в определении 5.1 строгое, то называют собственным подграфом графа , то называют остовным подграфом графа неориентированного (ориентированного) графа , если каждое ребро (дуга) тогда и только тогда принадлежит , когда его (ее) концы принадлежат . Часто в случае, если множество вершин подразумевается, говорят просто о порожденном подграфе.
Отметим, что подграф графа , в отличие от произвольного подграфа графа , должен включать все ребра (дуги), концы которых принадлежат множеству .
Подграф называют максимальным подграфом, обладающим данным свойством , если он не является собственным подграфом никакого другого подграфа графа .
Например, на рис. 5.7 подграфы являются максимальными ациклическими подграфами графа
Связность и компонента связности графов
Следующее важное понятие снова введем параллельно для рассматриваемых двух видов графов.
Неориентированный граф называют связным, если любые две его вершины .
Компонента связности (или просто компонента) неориентированного графа — это его максимальный связный подграф.
Ориентированный граф называют связным, если для любых двух его вершин вершина
Пример 5.3. Граф, изображенный на рис. 5.2, не является связным. Он состоит из трех компонент. Эти компоненты порождены тремя классами эквивалентности по отношению достижимости, указанными в примере 5.1.
Связными являются все графы, изображенные на рис. 5.7.
Ориентированный граф на рис. 5.8 связный, а ориентированные графы на рис. 5.3 и 5.9 не являются связными. В ориентированном графе на рис. 5.3 вершины и не достижимы одна из другой, а в ориентированном графе на рис. 5.9 взаимно не достижимы, например, вершины и . В ориентированном графе, изображенном на рис. 5.9, имеются две компоненты связности: и , которые пересекаются.
Сильная и слабая связности графов
Для ориентированного графа можно определить также понятия сильной и слабой связности.
Определение 5.2. Ориентированный граф называют сильно связным, если для любых двух его вершин Пример 5.4. а. В ориентированном графе, изображенном на рис. 5.3, бикомпонентой является подграф , порожденный множеством вершин . Действительно, эти вершины взаимно достижимы, поэтому ориентированный граф сильно связный. Так как из вершин ни одна из вершин не достижима, то выделенный сильно связный подграф является максимальным.
б. В ориентированном графе, представленном на рис. 5.9, имеются четыре бикомпоненты и . Это подграфы, порожденные соответственно множествами вершин и . Отметим, что подграф, порожденный множеством , не содержит ни одной дуги. Тем не менее этот подграф — бикомпонента, поскольку каждая вершина достижима сама из себя (по пути длины 0).
Определение 5.3. Неориентированный граф называют ассоциированным с ориентированном графом , если его множество вершин совпадает с множеством вершин ориентированного графа образует ребро тогда и только тогда, когда и из и
Таким образом, переход от ориентированного графа к ассоциированному с ним неориентированному графу состоит в "стирании" ориентации дуг ориентированного графа с учетом того, что все петли исчезают, а дуги и при переходят в одно и то же ребро .
Для ориентированного графа, изображенного на рис. 5.10, а, ассоциированный с ним неориентированный граф приведен на рис. 5.10, б. Отметим, что дуги и переходят в ребро , а петля исчезает.
Определение 5.4. Ориентированный граф называют слабо связным, если ассоциированный с ним неориентированный граф связный. Компонентой слабой связности (слабой компонентой) ориентированного графа называют его максимальный слабо связный подграф.
Ориентированные графы, представленные на рис. 5.3, 5.9 и 5.8, являются слабо связными. Ориентированный граф, изображенный на рис. 5.10, не является слабо связным, поскольку не является связным ассоциированный с ним неориентированный граф. Ориентированный граф на рис. 5.10,а имеет две компоненты слабой связности. Соответственно ассоциированный с ним неориентированный граф на рис. 5.10,б имеет две компоненты связности.
В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.
Граф - это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.
Например, граф на рисунке состоит из 8 вершин и 8 рёбер.
Очень многие задачи могут быть решены используя богатую библиотеку алгоритмов теории графов. Для этого достаточно лишь принять объекты за вершины, а связь между ними - за рёбра, после чего весь арсенал алгоритмов теории графов к вашим услугам: нахождение маршрута от одного объекта к другому, поиск связанных компонент, вычисление кратчайших путей, поиск сети максимального потока и многое другое.
В этой статье мы познакомимся с основными терминами и определениями теории графов. На курсе “Алгоритмы и Структуры данных” в компании Отус “Теория графов” изучается в самом объёмном модуле из 6 вебинаров, где мы изучаем десяток самых популярных алгоритмов.
Вершина - точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер; однако при решении некоторых задачах вершины могут раскрашиваться в разные цвета или сохранять числовые значения.
Ребро - неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге - не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.
Инцидентность - вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру.
Смежность вершин - две вершины называются смежными, если они инцидентны одному ребру.
Смежность рёбер - два ребра называются смежными, если они инцедентны одной вершине.
Говоря проще - две вершины смежные, если они соединены ребром, два ребра смежные - если они соединены вершиной.
Петля - ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.
Псевдограф - граф с петлями. С такими графами не очень удобно работать, потому что переходя по петле мы остаёмся в той же самой вершине, поэтому у него есть своё название.
Кратные рёбра - рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.
Мультиграф - граф с кратными рёбрами.
Псевдомультиграф - граф с петлями и кратными рёбрами.
Степень вершины - это количество рёбер, инцидентных указанной вершине. По-другому - количество рёбер, исходящих из вершины. Петля увеливает степень вершины на 2.
Изолированная вершина - вершина с нулевой степенью.
Висячая вершина - вершина со степенью 1.
Подграф. Если в исходном графе выделить несколько вершин и несколько рёбер (между выбранными вершинами), то мы получим подграф исходного графа.
Идея подграфов используется во многих алгоритмах, например, сначала создаётся подграф их всех вершин без рёбер, а потом дополняется выбранными рёбрами.
Полный граф - это граф, в котором каждые две вершины соединены одним ребром.
Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N - каждый новый участник должен пожать руку всем присутствующим. Сумму нужно разделить на два, так как в этом случае каждое рукопожатие посчитается дважды: N * (N - 1) / 2.
Регулярный граф - граф, в котором степени всех вершин одинаковые.
Двудольный граф - если все вершины графа можно разделить на два множества таким образом, что каждое ребро соединяет вершины из разных множеств, то такой граф называется двудольным. Например, клиент-серверное приложение содержит множество запросов (рёбер) между клиентом и сервером, но нет запросов внутри клиента или внутри сервера.
Планарный граф. Если граф можно разместить на плоскости таким образом, чтобы рёбра не пересекались, то он называется “планарным графом” или “плоским графом”.
Если это невозможно сделать, то граф называется “непланарным”.
Минимальные непланарные графы - это полный граф К5 из 5 вершин и полный двудольный граф К3,3 из 3+3 вершин (известная задача о 3 соседях и 3 колодцах). Если какой-либо граф в качестве подграфа содержит К5 или К3,3, то он является непланарным.
Путь или Маршрут - это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.
Длина пути - количество рёбер в пути.
Цепь - маршрут без повторяющихся рёбер.
Простая цепь - цепь без повторяющихся вершин.
Цикл или Контур - цепь, в котором последняя вершина совпадает с первой.
Длина цикла - количество рёбер в цикле.
Самый короткий цикл - это петля.
Цикл Эйлера - цикл, проходящий по каждому ребру ровно один раз. Эйлер доказал, что такой цикл существует тогда, и только тогда, когда все вершины в связанном графе имеют чётную степень.
Цикл Гамильтона - цикл, проходящий через все вершины графа по одному разу. Другими словами - это простой цикл, в который входят все вершины графа.
Взвешенный граф - граф, в котором у каждого ребра и/или каждой вершины есть “вес” - некоторое число, которое может обозначать длину пути, его стоимость и т. п. Для взвешенного графа составляются различные алгоритмы оптимизации, например поиск кратчайшего пути.
Пока ещё не придуман алгоритм, который за полиномиальное время нашёл бы кратчайший цикл Гамильтона в полном нагруженном графе, однако есть несколько приближённых алгоритмов, которые за приемлимое время находят если не кратчайший, то очень короткий цикл, эти алгоритмы мы также рассматриваем на курсе Отуса - “Алгоритмы и структуры данных”.
Связный граф - граф, в котором существует путь между любыми двумия вершинами.
Дерево - связный граф без циклов.
Между любыми двумя вершинами дерева существует единственный путь.
Деревья часто используются для организации иерархической структуры данных, например, при создании двоичных деревьев поиска или кучи, в этом случае одну вершину дерева называют корнем.
Лес - граф, в котором несколько деревьев.
Ориентированный граф или Орграф - граф, котором рёбра имеют направления.
Дуга - направленные рёбра в ориентированном графе.
Полустепень захода вершины - количество дуг, заходящих в эту вершину.
Исток - вершина с нулевой полустепенью захода.
Полустепень исхода вершины - количество дуг, исходящих из этой вершины
Сток - вершина с нулевой полустепенью исхода.
Компонента связности - множество таких вершин графа, что между любыми двумя вершинами существует маршрут.
Компонента сильной связности - максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам.
Компонента слабой связности - максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам без учёта направления (по дугам можно двигаться в любом направлении).
Мост - ребро, при удалении которого, количество связанных компонент графа увеличивается.
Это только основные термины и определения теории графов, которые мы рассматриваем на первом вебинаре модуля “Теория графов”. Цель статьи - дать наглядное и понятное представление об этих терминах, для чего и были нарисованы эти картинки.
Свидетельство и скидка на обучение каждому участнику
Зарегистрироваться 15–17 марта 2022 г.
Основные понятия и виды графов
Перед тем как начать изучение непосредственно алгоритмов, необходимо обладать базовыми знаниями касательно самих графов, понимать, как они представляются в компьютере. Здесь не будут подробно описаны все аспекты теории графов (этого и не требуется), но только те, незнание которых заметно усложнит усвоение данной области программирования.
Несколько примеров дадут немного поверхностного представления о графе. Так типичным графом является схема метро или какой-либо другой маршрут. В частности программисту знакома компьютерная сеть, также являющаяся графом. Общее здесь это наличие точек, соединенных линиями. Так в компьютерной сети точки – это отдельные серверы, а линии – различные виды электрических сигналов. В метрополитене первое – станции, второе – туннели, проложенные между ними. В теории графов точки именуется вершинами ( узлами ), а линии – ребрами ( дугами ). Таким образом, граф – это совокупность вершин, соединённых ребрами.
Математика оперирует не содержанием вещей, а их структурой, абстрагируя ее из всего того, что дано как целое. Пользуясь именно этим приемом, мы можем заключать о каких-либо объектах как о графах. А поскольку теория графов это часть математики, то для нее нет абсолютно никакого значения, что в принципе представляет собой объект; важно лишь то, является ли он графом, т. е. обладает ли обязательными для графов свойствами. Поэтому, прежде чем привести примеры, мы выделяем в рассматриваемом объекте лишь то, что как нам кажется, позволит показать аналогию, отыскиваем общее.
Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть условно изображена в виде некоторого числа компьютеров и путей их соединяющих. На рисунке ниже в качестве примера показана полносвязная топология.
Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.
Вот некоторые важные обозначения, используемые в теории графов:
G=(V, E), здесь G – граф, V – его вершины, а E – ребра;
|V| – порядок (число вершин);
|E| – размер графа (число рёбер).
В нашем случае (рис. 1) |V|=5, |E|=10;
Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 2).
В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины – это количество ребер, соединяющих ее с другими вершинами. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.
В орграфе, в отличие от неориентированного графа, имеется возможность двигаться из вершины h в вершину s без промежуточных вершин, лишь тогда когда ребро выходит из h и входит в s, но не наоборот.
Ориентированные графы имеют следующую форму записи:
G=(V, A), где V – вершины, A – направленные ребра.
Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.
В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие – ненаправленные [(e, d), (e, b), (d, c)…].
Два или более графов на первый взгляд могут показаться разными по своей структуре, что возникает вследствие различного их изображения. Но это не всегда так. Возьмем два графа (рис. 4).
Они эквивалентны друг другу, ведь не изменяя структуру одного графа можно построить другой. Такие графы называются изоморфными , т. е. обладающими тем свойством, что какая-либо вершина с определенным числом ребер в одном графе имеет тождественную вершину в другом. На рисунке 4 изображены два изоморфных графа.
Когда каждому ребру графа поставлено в соответствие некоторое значение, называемое весом ребра, тогда такой граф взвешенный . В разных задачах в качестве веса могут выступать различные виды измерений, например длины, цены маршруты и т. п. В графическом представлении графа весовые значения указываются, как правило, рядом с ребрами.
В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.
СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. Прежде чем отобразить граф через матрицу смежности, рассмотрим простой пример такой матрицы (рис. 1).
Это двоичная квадратная матрица, т. к. число строк в ней равно числу столбцов, и любой из ее элементов имеет значение либо 1, либо 0. Первая строка и первый столбец (не входят в состав матрицы, а показаны здесь для легкости ее восприятия) содержат номера, на пересечении которых находится каждый из элементов, и они определяют индексное значение последних. Имея в наличии лишь матрицу такого типа, несложно построить соответствующий ей граф.
Слева на рисунке изображена все та же матрица смежности, имеющая размерность 4×4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа – того, представлением которого является матрица.
Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе – 0. Немного формализовав только что сказанное, получим: если из i в j существует ребро, то A[i][j]:=1, в противном случае A[i][j]:=0. Как видно, все элементы на главной диагонали равны нулю, это следствие отсутствия у графа петель. Но ни что не мешает, чтобы некоторые или все элементы главной диагонали были единицами.
Говорить о том, что ребро g и каждая из вершин u и y инцидентна g , стоит лишь в том случае, если g соединяет u и y . Уяснив это, перейдем к рассмотрению данного метода. Матрица инцидентности строиться по похожему, но не по тому же принципу, что и матрица смежности. Так если последняя имеет размер n×n, где n – число вершин, то матрица инцидентности – n×m , здесь n – число вершин графа, m – число ребер. То есть теперь чтобы задать значение какой-либо ячейки, нужно сопоставить не вершину с вершиной, а вершину с ребром.
В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа , вносятся 1, 0 или -1. То же самое, но наиболее структурировано:
1 – вершина инцидентна ребру
0 – вершина не инцидентна ребру
1 – вершина инцидентна ребру, и является его началом
0 – вершина не инцидентна ребру
-1 – вершина инцидентна ребру, и является его концом
Построим матрицу инцидентности сначала для неориентированного графа, а затем для орграфа.
Ребра обозначены буквами от a до e , вершины – цифрами. Все ребра графа не направленны, поэтому матрица инцидентности заполнена положительными значениями.
Каждый столбец отвечает за какое-либо одно ребро, поэтому граф, описанный при помощи матрицы инцидентности, всегда будет иметь следующий признак: любой из столбцов матрицы инцидентности содержит две единицы, либо 1 и -1 когда это ориентированное ребро, все остальное в нем – нули.
По отношению к памяти списки смежности менее требовательны, чем матрицы смежности, для их хранения нужно O(|V|+|E|) памяти. Такой список графически можно изобразить в виде таблицы, столбцов в которой – два, а строк не больше чем вершин в графе. В качестве примера возьмем смешанный граф:
В нем 6 вершин ( |V| ) и 5 ребер ( |E| ). Из последних 2 ребра направленные и 3 ненаправленные, и, причем из каждой вершины выходит, как минимум одно ребро в другую вершину, из чего следует, что в списке смежности этого графа будет |V| строк.
В i строке и 1 столбце указана вершина выхода, а в i строке и 2 столбце – вершина входа. Так, к примеру, из вершины 5 выходят два ребра, входящие в вершины 1 и 4.
Список, в каждой строке которого записаны две смежные вершины и вес, соединяющего их ребра, называется списком ребер графа. Возьмем связный граф G=(V, E) , и множество ребер E разделим на два класса d и k , где d – подмножество, включающее только неориентированные ребра графа G , а k – ориентированные. Предположим, что некоторая величина p соответствует количеству всех ребер, входящих в подмножество d , а s – тоже относительно k . Тогда для графа G высота списка ребер будет равна s+p*2. Иными словами, количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных ребер с неориентированными, увеличенными вдвое. Это утверждение следует из сказанного ранее, а именно, что данный способ представления графа предусматривает хранение в каждой строке двух смежных вершин, а неориентированное ребро, соединяющее вершины v и u , идет как из v в u , так и из u в v .
Рассмотрим смешанный граф, в котором 5 вершин, 4 ребра и каждому ребру поставлено в соответствие некоторое целое значение (для наглядности оно составлено из номеров вершин):
В нем 3 направленных ребра и 1 ненаправленное. Подставив значения в формулу, получим высоту списка ребер: 3+1*2=5.
Так выглядит список ребер для приведенного графа. Это таблица размером n×3 , где n= s+p*2=3+1*2=5. Элементы первого столбца располагаются в порядке возрастания, в то время как порядок элементов второго столбца зависит от первого, а третьего от двух предыдущих.
Основные определения
Граф состоит из множества вершин V : ( V1 , V2 . Vn ) Î V и множества ребер Е , каждое из которых соединяет любые две вершины. Элементами Е являются пары ( Vi , Vj ), показывающие, какие вершины соединяются ребрами. При этом Vi и Vj принадлежат V . Иными словами, любая пара вершин ( Vi , Vj ) есть элемент произведения V ´ V . Поэтому можно сказать, что граф G c данными ребрами есть некоторое подмножество произведения V ´ V .
Это определение графа необходимо дополнить в одном важном отношении. В определении ребра можно принимать или не принимать во внимание порядок расположения его концов. Если порядок несущественен, т. е. ЕK = ( Vi , Vj ) = ( Vj , Vi ), то говорят о Неориентированном Ребре, в противном случае ребро ЕK является Ориентированным И для него ( Vi , Vj ) ¹ ( Vj , Vi ). В этом случае Vi Называется Начальной вершиной , а Vj – Конечной. Для неориентированного ребра вершина является одновременно и начальной, и конечной.
Ориентированные ребра обозначаются стрелками, выходящими из начальной вершины и входящими в конечную.
Если все ребра графа неориентированы, то и граф является неориентированным. Если все ребра графа ориентированы, то и граф является ориентированным.
Наконец, если часть ребер неориентированы, а другая часть имеет ориентацию, то тогда говорят о Смешанном графе. Например, план города можно рассматривать как граф, в котором ребра представляют улицы, а вершины – перекрестки. Если по улице допускается лишь одностороннее движение – ребро ориентировано.
При фактическом изображении графа имеется большая свобода в размещении вершин и в выборе формы соединяющих их ребер. Поэтому может оказаться, что один и тот же граф представляется совершенно различными чертежами. Будем говорить, что два графа G = ( V,E ) и G1 = ( V1 , E1 ) изоморфны, если существует такое взаимно-однозначное соответствие между множествами вершин V , V1 , когда две вершины в графе G1 Соединены ребрами в том и только в том случае, если две соответствующие им вершины соединены ребром в графе G . Если ребра ориентированы, то их направления также должны совпадать. Поэтому несущественно, каким изображением графа пользоваться, так как все изоморфные графы имеют одни и те же свойства. Пример изоморфных графов представлен на рис. 4.3.
Рис. 4.3 – Изоморфные графы
В графе могут существовать вершины, не связанные ребрами с другими вершинами. Такие вершины, не инцидентные никакому ребру, называются Изолированными . Граф, состоящий только из изолированных вершин, называется Нуль-графом И обозначается Æ.
Другим важным случаем является Полный граф U ( V ), в котором каждая вершина соединена ребрами со всеми остальными вершинами. Такой граф является неориентированным (рис. 4.4).
Рис. 4.4 – Неориентированные полные графы
В ориентированном полном графе две любые вершины соединены двумя ориентированными в противоположные стороны ребрами (рис. 4.5).
Рис. 4.5 – Ориентированный полный граф
Сформулированное нами определение графа вполне достаточно для многих практических задач. Однако для некоторых целей желательно понятие графа расширить.
Во-первых, можно допустить ребра, у которых обе концевые точки совпадают:
L = ( А , А ).
Такое ребро будем называть петлей. При изображении графа петля представляется замкнутой дугой, выходящей из вершины А , возвращающейся в нее же и не проходящей через другие вершины.
Петля обычно считается неориентированной. Если добавить петлю к каждой вершине полного неориентированного графа U , то мы получим полный неориентированный граф с петлями UО .
Во-вторых, можно допустить, что пара вершин соединяется несколькими различными ребрами: EI = ( A , B ) I.
Для ориентированного графа две вершины A и B могут соединяться несколькими ребрами в каждом из направлений : EI = ( A , B ) I ; EJ = ( B , A ,) J .
Примером такого графа является, например, запись результатов какого-либо турнирного соревнования, в котором участвуют N команд. Если победит А , то ребро E1 = ( A , B ), если победит B , то E1 = ( B , A ,), если ничья, – то ребро не ориентировано.
Для любого ориентированного графа G существует обратный граф G *, который получается изменением ориентации каждого ребра графа G на противоположную.
Для любого ориентированного графа G существует так называемый соотнесенный неориентированный граф GЦ , ребрами которого являются ребра G , но уже без ориентации.
Иногда удобно превратить неориентированный граф в ориентированный путем удвоения ребер и приписывания им противоположных направлений (рис.4.6).
Рис. 4.6 – Пример преобразования неориентированного графа в ориентированный
Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения его ребер являются вершинами (рис.4.7).
Читайте также: