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

Основные понятия теории графов. Связные графы Основные понятия теории графов. Оглавление | Назад | Далее | Глоссарий понятий Граф это множество точек или вершин и множество линий или ребер, соединяющих  между собой все или часть этих точек. Вершины, прилегающие к одному и тому же  ребру, называются смежными.  Если ребра ориентированны, что обычно показывают стрелками, то они  называются дугами, и граф с такими ребрами называется ориентированным графом.  Если ребра не имеют ориентации, граф называется неориентированным. Граф Графы обычно изображаются в виде геометрических фигур, так что вершины графа  изображаются точками, а ребра ­ линиями, соединяющими точки (рис. 2.15). Рис. 2.15 Петля это дуга, начальная и конечная вершина которой совпадают. Простой граф граф без кратных ребер и петель. Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс  количество остальных прилегающих к ней ребер. Пустым называется граф без ребер. Полным называется граф, в котором каждые две  вершины смежные. ПУТИ, МАРШРУТЫ, ЦЕПИ и ЦИКЛЫ.Путь в ориентированном графе — это последовательность дуг, в которой конечная  вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Вершины v0, vn называются связанными данным путем (или просто связанными).  Вершину v0 называют началом, vn ­ концом пути. Если v0 = vn, то путь  называют замкнутым. Число n называется длиной пути. Маршрут в графе путь, ориентацией дуг которого можно пренебречь.  Цепь маршрут, в котором все ребра попарно различны. Цикл замкнутый маршрут, являющийся цепью. Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны,  называются простым циклом. Граф отношения делимости Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе  число делится на первое (рис. 2.16). Рис. 2.16 ПОДГРАФЫ Подграф графа это граф, являющийся подмоделью исходного графа, т.е. подграф  содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца  которых входят в подграф).Подграф, порожденный множеством вершин U это подграф, множество вершин  которого ­ U, содержащий те и только те ребра, оба конца которых входят в U. Подграф называется остовным подграфом, если множество его вершин совпадает с  множеством вершин самого графа. Связность графа Граф называется связным, если любая пара его вершин связана.  Связными компонентами графа называются подграфы данного графа, вершины  которых связаны. Деревья Дерево — это связный граф без циклов. Деревья особенно часто возникают на практике при изображении различных иерархий.  Например, популярны генеалогические деревья. Генеалогическое дерево На рисунке 2.17 показано библейское генеалогическое дерево. Рис. 2.17 Граф без цикла называется лесом. Вершины степени 1 в дереве  называются листьями.  Деревья ­ очень удобный инструмент представления информации самого разного вида.  Деревья отличаются от простых графов тем, что при обходе дерева невозможны  циклы. Это делает графы очень удобной формой организации данных для различных  алгоритмов. Таким образом, понятия дерева активно используется в информатике и  программировании.Очевидно, что графический способ представления графов непригоден для ПК. Поэтому  существуют другие способы представления графов. В теории графов применяются 1. Матрица инцинденций. Это матрица А с n строками, соответствующими  вершинам, и m столбцами, соответствующнго рёбрам. Для ориентированного  графа столбец, соответствующий дуге (х,y) содержит ­ 1 в строке,  соответствующей вершине х и 1, в строке, соответствующей вершине у. Во всех  остальных 0. Петлю, т.е. дугу (х,х) можно представлять иным значением в  строке х, например, 2. Если граф неориентированный, то столбец,  соответствуюший ребру (х,у) содержит 1, соответствующие х и у и нули во всех  остальных строках. 2. Матрица смежности. Это матрица n×n где n ­ число вершин, где bij = 1, если  существует ребро, идещее из вершины х в вершину у и bij = 0 в противном случае. Составим матрицы инциндентности и смежности для следующего непрерывного графа  (рис. 2.18)   Матрица инцидентности Матрица смежности Рис. 2.18 Основные понятия и виды графов Перед тем как начать изучение непосредственно алгоритмов, необходимо обладать  базовыми знаниями касательно самих графов, понимать, как они представляются в  компьютере. Здесь не будут подробно описаны все аспекты теории графов (этого и не  требуется), но только те, незнание которых заметно усложнит усвоение данной области  программирования.Несколько примеров дадут немного поверхностного представления о графе. Так  типичным графом является схема метро или какой­либо другой маршрут. В частности  программисту знакома компьютерная сеть, также являющаяся графом. Общее здесь это  наличие точек, соединенных линиями. Так в компьютерной сети точки – это отдельные  серверы, а линии – различные виды электрических сигналов. В метрополитене первое –  станции, второе – туннели, проложенные между ними. В теории графов точки  именуется вершинами(узлами), а линии – ребрами (дугами). Таким образом, граф –  это совокупность вершин, соединённых ребрами. Математика оперирует не содержанием вещей, а их структурой, абстрагируя ее из всего  того, что дано как целое. Пользуясь именно этим приемом, мы можем заключать о  каких­либо объектах как о графах. А поскольку теория графов это часть математики, то для нее нет абсолютно никакого значения, что в принципе представляет собой объект;  важно лишь то, является ли он графом, т. е. обладает ли обязательными для графов  свойствами. Поэтому, прежде чем привести примеры, мы выделяем в рассматриваемом  объекте лишь то, что как нам кажется, позволит показать аналогию, отыскиваем общее. Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть  условно изображена в виде некоторого числа компьютеров и путей их соединяющих. На  рисунке ниже в качестве примера показана полносвязная топология.     Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим  математический объект – граф, который имеет 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. Способы представления графов Граф, как и большинство других математических объектов, может быть представлен на  компьютере (сохранен в его памяти). Существуют несколько способов его  интерпретации, вот наиболее известные из них:  матрица смежности;  матрица инцидентности;  список смежности;  список ребер. Использование двух первых методов предполагает хранение графа в виде двумерного  массива (матрицы). Причем размеры этих массивов, зависят от количества вершин и/или  ребер в конкретном графе. Так размер матрицы смежности n×n, где n – число вершин, а  матрицы инцидентности n×m, n – число вершин, m – число ребер в графе. Смотрите Также: 1. Список ребер2. Матрица смежности 3. Список смежности 4. Матрица инцидентности 5. Алгоритм Беллмана — Форда Теория графов: основные понятия и определения Неформально граф можно рассматривать как множество точек и соединяющих эти  точки линий со стрелками или без них. Первой работой теории графов как математической дисциплины считают статью Эйлера  (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал,  что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по  каждому мосту ровно один раз. Следующий импульс теория графов получила спустя  почти 100 лет с развитием исследований по электрическим сетям, кристаллографии,  органической химии и другим наукам. С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом  является схема линий метрополитена. Точками на ней представлены станции, а линиями  — пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо — граф. Графы служат удобным средством описания связей между объектами. Ранее мы уже  использовали графы как способ наглядного представления конечных бинарных  отношений. Но граф используют отнюдь не только как иллюстрацию. Например,  рассматривая граф, изображающий сеть дорог между населенными пунктами, можно  определить маршрут проезда от пункта А до пункта Б. Если таких маршрутов окажется  несколько, хотелось бы выбрать в определенном смысле оптимальный, например самыйкороткий или самый безопасный. Для решения задачи выбора требуется проводить  определенные вычисления над графами. При решении подобных задач удобно  использовать алгебраическую технику, да и само понятие графа необходимо  формализовать. Методы теории графов широко применяются в дискретной математике. Без них  невозможно обойтись при анализе и синтезе различных дискретных преобразователей:  функциональных блоков компьютеров, комплексов программ и т.д. В настоящее время теория графов охватывает большой материал и активно развивается.  При ее изложении ограничимся только частью результатов и основной акцент сделаем на описании и обосновании некоторых широко распространенных алгоритмов анализа  графов, которые применяются в теории формальных языков. Графы, как уже отмечалось в примерах, есть способ "визуализации" связей между  определенными объектами. Связи эти могут быть "направленными", как, например, в  генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов:  ориентированные (или направленные) и неориентированные. Построение математического определения графа осуществляется путем формализации и "объектов", и "связей" как элементов некоторых (как правило, конечных) множеств. Неориентированные графызадается двумя множествами  Неориентированный граф  , где  конечное множество, элементы которого называют вершинами или узлами;  множество неупорядоченных пар на  подмножеств  считаем, что  , элементы которого называют ребрами. Для каждого ребра   и   — различные вершины. , т.е. подмножество множества двухэлементных     —   —  Если ребро  это мы  , то говорят, что ребро   соединяет вершины  . ; если необходимо, указывают имя графа   и  , и обозначают  Вершины  ребра  непосредственной достижимости.  и  , соединенные ребром  . Если  , называют смежными, а также концами  , говорят, что вершины   и  связаны отношением  Ребро   называют инцидентным вершине  , если она является одним из его концов. Степенью вершины   называют число   всех инцидентных ей ребер. Для вершины   множество  вершин. Справедливо равенство  .  называют множеством смежных с    Цепь в неориентированном графе  бесконечная)  (Под конечной последовательностью понимается кортеж вершин.)  — это последовательность вершин (конечная или   существует.   для любого  , если  , такая, чтоДля конечной цепи  длина цепи есть число ее ребер, т.е. всех ребер, соединяющих вершины  . Цепь длины 0 — это произвольная вершина графа. и   число     называют длиной цепи. Таким образом,  Говорят, что вершина   неориентированного графа  , если существует цепь  графа и обозначают и   достижима из вершины   этого   такая, что     и  , которые   (при этом говорят также, что данная цепь соединяет вершины  называют концами цепи). Таким образом, задано отношение достижимости  неориентированном графе. Оно является рефлексивно­транзитивным замыканием  отношения  непосредственной достижимости.  в  Отношение достижимости в неориентированном графе рефлексивно, симметрично и  транзитивно, т.е. является отношением эквивалентности Если существует цепь ненулевой длины, соединяющая  необходимо явно указать длину цепи, то пишут  длины  , соединяющая   и  .  и  , то пишут  . Если   и говорят, что существует цепь  Простая цепь — это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра попарно различны. Простую цепь ненулевой длины с совпадающими концами называют циклом. Произвольную цепь ненулевой длины с совпадающими концами, все ребра которой  попарно различны, будем называть замкнутой цепью. Неориентированный граф, не содержащий циклов, называют ациклическим графом.Ориентированные графы  задается двумя множествами  Ориентированный граф  множество, элементы которого называют вершинами или узлами;  упорядоченных пар на  называют дугами. , т.е. подмножество множества  , где   — конечное   — множество  , элементы которого  Если дуга  это  , то говорят, что дуга   ведет из вершины  ; если необходимо, указывают имя графа   в вершину  , и обозначают .  и  , такие, что из вершины  Вершины  сиежнылси, причем м называют началом, а   — концом дуги  которой есть одна и та же вершина, называют петлей. Если  вершины и и v связаны отношением непосредственной достижимости.  в вершину   ведет дуга  , называют  . Дугу, начало и конец  , то говорят, что  Дугу  инцидентной вершине  , если она заходит в   или исходит из  .  называют заходящей в вершину   и исходящей из вершины  . Дугу называют  Полустепенью захода вершины   называют число  полустепенью исхода вершины   — число  вершины  , обозначаемая   заходящих в нее дуг, а   исходящих из нее дуг. Степень  , — это сумма полустепеней захода и исхода.Для вершины   множество  вершины  , а множество  вершины  . Справедливы равенства  называют множеством преемников   — множеством предшественников  Путь в ориентированном графе  бесконечная)   — это последовательность вершин (конечная или  , такая, что   для любого  , если   существует. Для конечного пути  длина пути есть число его дуг, т.е. всех дуг, которые ведут из вершины  вершину  . Путь длины 0 — это произвольная вершина графа.  называют длиной пути   число  . Тем самым   в  , если существует путь  Говорят, что вершина   ориентированного графа  и обозначают  этом говорят, что данный путь ведет из вершины  началом, а вторую — концом данного пути). Таким образом, задано отношение  достижимости  замыканием отношения   этого графа  (при   в вершину  , называя первую вершину  в ориентированном графе. Оно является рефлексивно­транзитивным   непосредственной достижимости.  достижима из вершины  . такой, что  Отношение достижимости в ориентированном графе рефлексивно и транзитивно, но в  общем случае не антисимметрично: если две вершины ориентированного графа  достижимы одна из другой, то из этого вовсе не следует, что они совпадают. Таким  образом, отношение достижимости в ориентированном графе есть отношение  предпорядка.Если существует путь ненулевой длины, ведущий из  необходимо явно указать длину пути, то пишут  длины  , ведущий из   в  .  в  , то пишут   и говорят, что существует путь  . Если  Простой путь — это путь, все вершины которого, кроме, быть может, первой и  последней, попарно различны. Простой путь ненулевой длины, начало и конец которого совпадают, называют контуром. Произвольный путь ненулевой 1 длины, начало и конец которого совпадают, будем  называть замкнутым путем. Ориентированный граф, не содержащий контуров, называют бесконтурным графом. Замечание 5.1. Требование, чтобы все ребра простой цепи неориентированного графа  были попарно различными, существенно. Если его снять, то цепь вида  будет циклом, в котором одно и то же ребро  противоположных направлениях, хотя такую цепь естественно циклом не считать. Не  будет эта цепь в соответствии с принятой терминологией и замкнутой цепью.  проходится дважды в  , где  ,  В неориентированном графе на рис. 5.1 цепь  является примером замкнутой цепи. Замечание 5.2. В общем случае в ориентированном графе пересечение множества  преемников  если есть петля   вершины   и множества   ее предшественников будет не пусто,  .Пример 5.1. Рассмотрим неориентированный граф, изображенный на рис. 5.2. Он  задается множеством вершин и множеством неупорядоченных пар  .  есть простая цепь, а   — цепь, не являющаяся простои, поскольку в ней  В этом графе последовательность вершин  последовательность  есть совпадающие ребра. Последовательность вершин  поскольку в графе нет ребра  последовательность  поскольку эта цепь не является простой. Эта цепь не будет и замкнутой, так как в ней  есть повторяющееся ребро  — цепь с совпадающими концами, но не цикл,  . Последовательность  .  не является цепью,   есть цикл, а  Степени вершин графа следующие:  попарно достижимы  Вершины  эквивалентности по отношению достижимости. Для вершин  и они также образуют класс эквивалентности. Заметим, что вершина V7, по  определению, образует цепь длины 0 и эквивалентна по отношению достижимости  только самой себе.  имеет место   и   и образуют класс  ,Пример 5.2. Обратимся к ориентированному графу, изображенному на рис. 5.3. Он  задается множеством вершин   и множеством дуг В этом ориентированном графе последовательность вершин  путь, а последовательность вершин  поскольку в нем, например, два раза встречается вершина, не служащая началом и  концом пути.  — путь, не являющийся простым,   есть простой  Последовательность вершин  последовательность  вершина  вершин  нет дуги  .  есть контур, а   — замкнутый путь, но не контур, поскольку  , не являющаяся началом пути, встречается два раза. Последовательность   не задает путь, так как в рассматриваемом ориентированном графе  Полустепени захода, полустепени исхода и степени у вершин следующие: Свойства отношения достижимости в графахОтношение достижимости в неориентированных и ориентированных графах обладает  следующим важным свойством. Теорема 5.1. Для любой цепи, соединяющей две вершины неориентированного графа,  существует простая цепь, соединяющая те же вершины. Для любого пути, ведущего из вершины  ведущий из   в вершину   ориентированного графа, существует простой путь,   в  . Проведем доказательство для неориентированного графа (для ориентированного графа  доказательство проводится аналогично). . Если эти вершины  . Если цепь   простая, то   и   неориентированного графа таковы, что  , т.е. существует цепь ненулевой длины, соединяющая   в  . Рассмотрим  , которая повторяется в этой цепи, т.е. . Это значит, что вершина  Пусть вершины  являются концами цепи нулевой длины, то утверждение теоремы тривиально.  Пусть  какую­либо из таких цепей (рис. 5.4). Обозначим ее  доказывать нечего. Пусть существует внутренняя (не совпадающая ни с одним из концов) вершина  содержится в некоторой цепи  концами (рис. 5.5). Удалим все вершины и ребра цепи  началом и концом одновременно). После этого получим новую цепь  вершины  на единицу меньше, чем в цепи  противном случае поступаем с ней так же, как и с цепью  множества вершин и ребер графа после конечного числа шагов получим простую цепь,  соединяющую вершины   и   (рис. 5.6), в которой число повторений вершины    ) с совпадающими  . Если цепь   простая, то утверждение доказано. В   ненулевой длины (подцепи цепи  , кроме вершины   (служащей ее , соединяющую   будет по крайней мере  . В силу конечности   цепи   и  .Следствие 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,б имеет  две компоненты связности. Базовые понятия теории графов История возникновения теории графов Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Терминология теории графов Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано: “В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Мы выбрали термин "сеть", так как он, по­видимому, чаще встречается в прикладных областях”.  Аналогичная ситуация для “вершина /точка” Теория графов ­ (англ. theory, graph; нем. Graphentheorie) в узком смысле ­ раздел  дискретной математики, одна из ветвей дискретной топологии, в широком смысле ­  теория сетей, наука о топологических формах, сетевых моделях представления любого  процесса или системы.. Основным объектом исследования этой теории являются графы.  Графом называют геометрическую схему, представляющую собой систему линий,  связывающих какие то заданные точки. Точкиназываемые вершинами, а связывающие их  линии – ребрами (или дугами). Теория графов обосновывает способы построения  графов, выражающих зависимости или связи в форме геометрических схем междуразличными единицами той или иной совокупности. Фактически теория графов есть  совокупность способов топологических представлений каких­либо процессов или  структур. Многие структуры, представляющие практический интерес в логике, информатике,  математике и других науках, могут быть представлены графами. Например, строение  любого Интернет ресурса можно смоделировать при помощи ориентированного графа  (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) —  гиперссылки. Вся сеть Интернет ­ тоже граф. Теория графов не обладает устоявшейся  терминологией. В различных статьях под одними и теми же терминами понимаются  разные вещи. Ниже приведены наиболее часто встречаемые определения. Теория графов находит применение, например, в геоинформационных системах (ГИС).  Существующие или вновь проектируемые дома, сооружения, кварталы и т. п.  рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии  электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший  продуктовый магазин, спланировать оптимальный маршрут. Теория графов содержит большое количество нерешённых проблем и пока не  доказанных гипотез. Граф в математической теории графов и информатике ­ это совокупность непустого  множества объектов ­ вершин и связей между ними. Объекты представляются как  вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей  применения виды графов могут различаться направленностью, ограничениями на  количество связей и дополнительными данными о вершинах или рёбрах. Неориентированный граф, или граф G — это упорядоченная пара G := (V, E), для  которой выполнены следующие условия: V — это непустое множество вершин, или узлов, E — это множество пар (в случае неориентированного графа — неупорядоченных)  вершин, называемых рёбрами. V (а значит и, E, иначе оно было бы мультимножеством) обычно считаются конечными  множествами. Многие хорошие результаты, полученные для конечных графов, неверны  (или каким­либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств. Вершины и рёбра графа называются также элементами графа.Порядок графа ­ это число вершин в графе |V|. Размер графа ­ это число его рёбер |E| Концевые вершины ­ это вершины, соединяющие данное множество ребер. Две концевые  вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину. Два ребра называются кратными, если множества их концевых вершин совпадают. Ребро называется петлёй, если его концы совпадают, то есть e=\{v,v\}. Степенью вершины V называют количество инцидентных ей рёбер (при этом петли  считают дважды). Вершина называется изолированной, если она не является концом ни для одного ребра;  висячей (или листом), если она является концом ровно одного ребра. Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G := (V, A),  для которой выполнены следующие условия: V — это непустое множество вершин или узлов, A — это множество (упорядоченных) пар различных вершин, называемых дугами или  ориентированными рёбрами. Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w —  концом дуги. Можно сказать, что дуга v \to w ведёт от вершины v к вершине w. Смешанный граф G — это граф, в котором некоторые рёбра могут быть  ориентированными, а некоторые — неориентированными. Записывается упорядоченной  тройкой G := (V, E, A), где V, E и A определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями  смешанного. Изоморфный граф ­ это некоторый граф G, для которого существует биекция f из  множества вершин графа G в множество вершин другого графа H, которому он  изоморфен, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и  наоборот — если в графе H есть ребро из вершины A в вершину B, то в графе G должно  быть ребро из вершины f^{­1}(A) в вершину f^{­1}(B). В случае ориентированного графаэта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа  биекция также должна сохранять вес ребра. Путь графа, цепь графа ­ это конечная последовательность вершин, в которой каждая  вершина (кроме последней) соединена со следующей в последовательности вершин  ребром. Ориентированный путь в орграфе ­ это конечная последовательность вершин v_i (i=1,  …,k), для которой все пары (v_i, v_{i+1}) (i=1,… k­1) являются (ориентированными)  рёбрами. Цикл ­ это путь, в котором первая и последняя вершины совпадают. При этом длиной  пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u  и v являются концами некоторого ребра, то согласно данному определению,  последовательность (u,v,u) является циклом. Чтобы избежать таких “вырожденных”  случаев, вводят следующие понятия. Простой путь (простой цикл) ­ это такой путь, в котором ребра не повторяются. Элементарный путь ­ это простой путь, вершины в котором не повторяются. Несложно видеть, что: Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те  же две вершины. Всякий простой неэлементарный путь содержит элементарный цикл. Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит  элементарный (под­)цикл, проходящий через ту же вершину (или ребро). Петля ­ это элементарный цикл. Бинарное отношение на множестве вершин графа, заданное как “существует путь из u в  v”, является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа  ровно одна компонента связности, то граф связный. На компоненте связности можно  ввести понятие расстояния между вершинами как минимальную длину пути,  соединяющего эти вершины. Компонента графа, связная компонента графа ­ это всякий максимальный связный  подграф графа G. Слово “максимальный” означает максимальный относительно  включения, то есть не содержащийся в связном подграфе с большим числом элементовМост ­ это ребро графа, если удаление этого ребра увеличивает число компонент графа. Связный граф ­ это граф, в котором для любых вершин u,v есть путь из u в v. Сильно связный или ориентированно связный граф ­ это ориентированный граф, в  котором из любой вершины в любую другую имеется ориентированный путь. Дерево ­ это связный граф, не содержащий простых циклов. Полный граф ­ это граф, в котором любые его две (различные, если не допускаются  петли) вершины соединены ребром. Двудольный граф ­ это граф, в котором вершины можно разбить на два  непересекающихся подмножества V_1 и V_2 так, что всякое ребро соединяет вершину  из V_1 с вершиной из V_2. k­дольный граф ­ это граф, в котором вершины можно разбить на k непересекающихся  подмножества V_1, V_2, …, V_k так, что не будет рёбер, соединяющих вершины одного  и того же подмножества. Полный двудольный граф ­ это граф, в котором каждая вершина одного подмножества  соединена ребром с каждой вершиной другого подмножества. Планарный граф ­ это граф, который можно изобразить диаграммой на плоскости без  пересечений рёбер. Взвешенный граф ­ это граф, в котором каждому ребру поставлено в соответствие  некоторое число, называемое весом ребра. Существуют также k­раскрашиваемые и k­хроматические графы. Простой граф является одномерным симплициальным комплексом. Более абстрактно, граф можно задать как тройку (V, E, Ф), где V и E — некоторые  множества (вершин и рёбер, соответственно), а Ф — функция инцидентности (или  инцидентор), сопоставляющая каждому ребру e < E (упорядоченную или  неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого  понятия являются:  ориентированные графы (орграфы) — когда \varphi(e) всегда является  упорядоченной парой вершин;  неориентированные графы — когда \varphi(e) всегда является неупорядоченной  парой вершин; смешанные графы — в котором встречаются как ориентированные, так и  неориентированные рёбра и петли;  Эйлеровы графы — граф в котором существует циклический эйлеров путь  (Эйлеров цикл).  мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;  псевдографы — это мультиграфы, допускающие наличие петель;  простые графы — не имеющие петель и кратных рёбер. Под данное выше определение не подходят некоторые другие обобщения:  гиперграф — если ребро может соединять более двух вершин.  ультраграф — если между элементами xi и uj существуют бинарные отношения  инцидентности. Объектный граф ­ совокупность узлов и ребер, соединяющих эти узлы. Объектные графы обеспечивают простой способ учета взаимных связей в системе, множестве объектов, и  не обязательно, чтобы эти связи в точности проецировались в классические связки  объектно­ориентированного программирования (такие как отношения старшинства и  подчиненности), хотя они моделируют эту парадигму достаточно хорошо. Каждому  объекту в объектном графе назначается уникальное числовое значение. Следует иметь в  виду, что эти числовые значения, приписываемые членам в объектном графе,  произвольны и не имеют никакого смысла вне графа. После назначения всем объектам  числового значения объектный граф может начать запись множества зависимостей  каждого объекта. Матрица смежности ­ это таблица, где как столбцы, так и строки соответствуют  вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее  наличие связи от вершины­строки к вершине­столбцу (либо наоборот). Ее недостатком  являются требования к памяти, прямо пропорциональные квадрату количества вершин. Список рёбер — это тип представления графа, подразумевающий, что каждое ребро  представляется двумя числами — номерами вершин этого ребра. Изображение графов на плоскости При изображении графов чаще всего используется следующая система обозначений:  каждой вершине сопоставляется точка на плоскости, и если между вершинамисуществует ребро, то соответствующие точки соединяются отрезком. В случае  ориентированного графа отрезки заменяют стрелками. Не следует путать изображение графа с собственно графом (абстрактной структурой),  поскольку одному графу можно сопоставить не одно графическое представление.  Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения  моделями одного и того же графа или нет. В зависимости от задачи, одни изображения  могут давать более наглядную картину, чем другие. Языки описания и программы построения графов Для описания графов в целях, пригодных для машинной обработки и одновременно  удобном для человеческого восприятия используется несколько стандартизированных  языков, среди которых:  DOT (язык графов)  GraphML  Trivial Graph Format  GML  GXL  XGMML  DGML Отметим специализированные программы для построения графов. К наиболее удачным  относятся коммерческие:  ILOG  GoView  Lassalle AddFlow  LEDA (есть бесплатная редакция). Из бесплатных можно отметить Boost Graph Library ­ Библиотека для работы с графами  на языке C++ Для визуализации графов можно использовать: Graphviz (по мнению экспертов, она хорошо работает для орграфов)  LION Graph Visualizer.  Графоанализатор – это русскоязычная программа, с весьма простым  пользовательским интерфейсом. Некоторые задачи теории графов Проблема семи мостов Кёнигсберга — один из первых результатов в теории графов,  опубликован Эйлером в 1736. Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое  доказательство получено лишь в 1976 году (достаточно 4­х красок для карты на сфере  (плоскости). Задача коммивояжёра — одна из наиболее известных NP­полных задач. Задача о клике — ещё одна NP­полная задача. Нахождение минимального стягивающего (остовного) дерева. Изоморфизм графов — можно ли путем перенумерации вершин одного графа получить  другой. Планарность графа — можно ли изобразить граф на плоскости без пересечений ребер  (или с минимальным числом слоев, что находит применение при трассировке  межсоединений элементов печатных плат или микросхем). К теории графов также относится целый ряд математических проблем, не решенных на  сегодняшний день. Применение теории графов В химии (для описания структур, путей сложных реакций, правило фаз также может  быть интерпретировано как задача теории графов); компьютерная химия —  сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов  позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений. В информатике и программировании (граф­схема алгоритма)В коммуникационных и транспортных системах. В частности, для маршрутизации  данных в Интернете. В схемотехнике (топология межсоединений элементов на печатной плате или  микросхеме представляет собой граф или гиперграф). Литература 1. Харари Ф. Теория графов.. — Москва: Мир, 1973. 2. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c. 3. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. — М.: Высш. школа,  1976. — С. 392. 4. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c. 5. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по  теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.) 6. Зыков А. А. Основы теории графов. — М.: “Вузовская книга”, 2004. — С. 664. —  ISBN 5­9502­0057­8(М.: Наука, 1987. 383c.) 7. Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с  англ. М.: Мир, 1987. 8. Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. 168 c.  http://vuz.exponenta.ru/PDF/book/GrMaple.pdf  http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf 9. Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c. 10.Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы:  построение и анализ = Introduction to Algorithms. — 2­е изд.. — М.: Вильямс, 2006.  — С. 1296. — ISBN 0­07­013151­1 11.Оре О. Теория графов. — 2­е изд.. — М.: Наука, 1980. — С. 336. 12.Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем.  — М.: Физико­математическая литература, 1997. — ISBN 5­02­015033­9 13.Свами М., Тхулалираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с. 14.Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.15.Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с. 16.Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296  с.) 17.Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977. 18.Diestel R. Graph Theory, Electronic Edition. — NY: Springer­Verlag, 2005. — С. 422. 19.Оре О. Теория графов. М.: Наука, 1968.  336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu 20.Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977.  208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu 21.Харари Ф. Теория графов. М.: Мир,  1973. http://eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu 22.Кормен Т. М.и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы:  построение и анализ = INTRODUCTION TO ALGORITHMS. — 2­е изд. — М.:  “Вильямс”, 2006. — С. 1296. — ISBN 0­07­013151­1 23.Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем.  — М.: Физико­математическая литература, 1997. — ISBN 5­02­015033­9 24.Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по  теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.) 25.Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. — 168 c.  http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/boo ks/Kirsanov2007ru.pdf к библиотеке   Устройства ввода информации   к экономической информатике   к  дискретной математике Знаете ли Вы, что "тёмная материя" ­ такая же фикция, как черная кошка в темной  комнате. Это не физическая реальность, но фокус, подмена. Реально идет речь о том, что релятивистские формулы не соответствуют  астрономическим наблюдениям, давая на порядок и более меньшую массу и меньшую  энергию. Отсюда сделан фокуснический вывод, что есть "темная материя" и "темная  энергия", но не вывод, что релятивистские формулы не соответствуют реалиям.  Подробнее читайте в FAQ по эфирной физике.