Алгоритмы на графах

 

ВВЕДЕНИЕ

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1 ОСНОВЫ ТЕОРИИ ГРАФОВ

 

 

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

 

Графом G=(X, U) будем называть совокупность двух конечных множеств: множества вершин X={x₁,…, x_n} и множества ребер (дуг)

U = {u₁…..u_m}, состоящего из некоторых пар элементов (x_i, x_j) множества X.

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

Если пары вершин (x_i, x_j) в множестве U являются неупорядоченными (т.е., порядок соединения вершин несущественен), то граф называется неориентированным (неорграфом), а пары (x_i, x_j) – ребрами этого графа (рис. 1, а). При этом вершины x_i, x_j называют концами (концевыми вершинами) ребра. В данном случае также говорят, что ребро (х_i, x_j,) соединяет вершины x_i и x_j. Если пары вершин (x_i, x_j) в множестве U являются упорядоченными (т.е., порядок соединения вершин существенен), то граф называется ориентированным (орграфом), а пары (x_i, x_j) – дугами. Дуги орграфа, в отличие от ребер неорграфа, будем обозначать < x_i, x_j >. При этом x_i – начало (начальная вершина) дуги, x_j – конец (конечная вершина) дуги. Говорят также, что дуга < x_i, x_j > исходит из вершины x_i и заходит в вершину x_j. Заметим, что < x_i, x_j > и < x_i, x_j > – это различные дуги в графе. При изображении орграфа дуги обозначают стрелками, указывающими их ориентацию (направление). Графы, в которых имеются и неориентированные ребра, и дуги, называются смешанными. Заметим, что любой неориентированный граф может быть представлен в виде орграфа путем замены каждого его ребра двумя противоположно направленными дугами.

В дальнейшем вершины графа  будем обозначать символами х₁, х₂,…, ребра – символами u₁, u₂,… (или парами (x_i, x_j)), дуги – символами u₁, u₂,… (или упорядоченными парами < x_i, x_j >). Число вершин графа обозначим через n, число ребер (дуг) – через m.

Пара вершин x_i, x_j может соединяться двумя или более ребрами (дугами одного направления). Такие ребра (дуги) называют кратными. Количество одинаковых ребер (x_i, x_j) (дуг < x_i, x_j >) называется кратностью соответствующего ребра (дуги). Петлей называется дуга (ребро) с совпадающими начальной и конечной вершинами.

Граф с петлями и  кратными ребрами (дугами) называется псевдографом. Граф с кратными ребрами (дугами) и без петель называется мультиграфом.

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

Так, граф, представленный на рис. 1, а является псевдографом, так как содержит петлю (x_i, x_j) и кратное ребро (х₂, x₃); граф на рис. 1, б является мультиграфом, граф на рис. 1, в-простым графом.

Две вершины графа x_i и х_j называются смежными, если существует соединяющее их ребро (дуга). Два ребра (дуги) смежные, если они имеют общую вершину. Вели ребро (дута) U_k соединяет вершины x_i и x_j. то говорят, что ребро (дуга) инциндентно вершинам x_i и x_j, а вершины x_i и x_j инциндентны ребру (дуге) U_k. Так, на рисунке 1 а вершина x₅ инциндетна ребрам U₆, U₉, U₅, ребра U₁₀ и U₆ являются смежными; смежными являются вершины х₁ и х₆, x₅ и х₆

 

Рисунок 1.1 – Изображения графов

 

Часто граф задают парой (Х, Г), где X – множество вершин графа, а Г – отображение, ставящее в соответствие каждой вершине графа подмножество множества X. При этом для орграфа Г(х_i) – множество вершин x_j є X, для которых в графе существует дуга <х_i, х_j>; Г^-1(х_i) – множество вершин х_k є Х, для которых в графе существует дуга <x_k, x_i>. Для неорграфа Г (х,)= Г^-1(х_i) и означает количество вершин, смежных с вершиной x_i.

Подграфом графа G=(X, U) называется граф G’=(X’.U’), для которого X’є X, U’ є U. Остовным подграфом графа G=(X, U) называется граф G₀= (X, U₀), содержащий все вершины графа G. Порожденным подграфом графа G=(X.H) на множестве вершин Х_р называется граф G_p=(X_p, U_p), где Х_p є Х, а U_p - множество ребер (дуг) графа G, оба конца которых принадлежат множеству Х_р. Так. на рис. 2, а представлен граф G, на рис. 2, б – его произвольный подграф, на рис. 2, в-порожденный подграф графа G на множестве вершин Х {x₁, x₂, x₃, x₄} на рисунке 2, г – один из остовных подграфов графа G.

 

 

Рисунок 1.2 – Изображение остовного подграфа

 

Граф G =(X, U) называется дополнением простого графа G=(X, U), если множества вершин G и G совпадают, а две вершины смежны в G тогда и только тогда, когда они не смежны в G. На рисунке 3 представлен граф G и его дополнение.

 

Рисунок 1.3 – Изображение графа и его дополнения

 

Число дуг, исходящих из вершины  х_i, ориентирован но го графа, называется полустепенью исхода вершины х_i, и обозначается р^-(х,). Число дуг, заходящих в вершин x_i, напивается полустепенью захода вершины x_i и обозначается р⁺(х,). В случае ориентированного псевдографа вклад каждой петли, инциндентной некоторой вершине х_i, равен 1 как в р^-(x_i), так и в р⁺(x_i). Так. для орграфа, представленного на рис. 3, 6 p^-(x₁)=l; p⁺(x₁)=2; р^-(x₂)=3; р⁺(х₂)=2. Для любого орграфа выполняется равенство:

 

 (1.1)

 

В неориентированном графе  число ребер, инциндентных данной вершине  x_i, называется степенью (валентностью) вершины х_i и обозначается р(х_i). Вершина графа, имеющая степень 0, называется изолированной, а вершина, имеющая степень I – висячей. Для неориентированного псевдографа вклад каждой петли, инциндентной вершине x_i, в р(х_i) равен 2. Для неорграфа на рис. 3, а р(х₄)=4; p(x₁)=5. Число вершин нечетной степени в любом графе четно. Для любого неорграфа справедливо следующее равенство

 

(1.2)

 

1.2 Матричный способ задания графов. Изоморфизм и геоморфизм

 

Матрицей смежности неориентированного графа G=(X, U) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:

Для ориентированного графа:

                             (1.3)

 

                                                     (1.4)

 

В псевдографе a_ij =k, где k – кратность ребра (x_i, x_j) (дуги < x_i, x_j >). Петлям в матрице смежности соответствуют элементы, расположенные на главной диагонали. Сумма – элементов матрицы А неорграфа G пo i – и строке (или по i – му столбцу) равна р(х_i). Для орграфа сумма элементов матрицы А по i – й строке равна р^-(х_i). по i – му столбцу р⁺(х_i). Очевидно, что матрица смежности неорграфа является симметричной относительно главной диагонали, Матрицей инциндентности неориентированного графа G=(X, U) с n вершинами и m ребрами называется матрица В размера n x m, элементы которой определяются следующим образом:

 

                     (1.5)

 

Для ориентированного графа:

 

              (1.6)

 

Изоморфизм и геоморфизм.

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

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

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

 

1.3 Маршруты, цепи, циклы в графах

 

Последовательность ребер  неорграфа (x₁, x₂), …, (x_r-1, x_r), в которой конец каждого предыдущего ребра совпадает с началом следующего, называется маршрутом, соединяющим вершины x₁ и x_г. Аналогом маршрута для орграфа является ориентированный маршрут из х₁ в х_г. представляющий собой последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей. При этом x₁ и x_r называются начальной и конечной вершинами маршрута. Если любые две вершины графа соединены маршрутом, то граф называется связным.

          Маршрут является замкнутым, если начальная вершина совпадает с конечной, и незамкнутым в противном случае. Незамкнутый маршрут, в котором все ребра различны, называют цепью. Незамкнутый ориентированный маршрут, содержащий попарно различные дуги называется путем. Цепь (путь), в которой (в котором) все вершины попарно различны, называется простой (простым). Замкнутая цепь называется циклом, замкнутая простая цепь – простым циклом. Замкнутый путь называется контурам, замкнутый простой путь – простым контурам. Граф, не содержащий циклов, называют ациклическим.

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

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

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

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

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

          Граф, у которого все вершины имеют одинаковую степень k, называется регулярным (однородным) графом степени k. Число ребер m такого графа определяется следующим образом:

 

  (1.7)

 

Граф, не имеющий ребер, называется пустым, а его вершины – изолированными. Пустой граф, имеющий n вершин, обозначается О_n.

Граф называется полным, если все его вершины смежны. Полный граф порядка n обозначается К_n. Число ребер полною графа К_n определяется следующим образом:

 

  (1.8)

 

Граф G=(X, U) называется двудольным, если существует такое разбиение множества его вершин X на два непересекающихся подмножества X₁ и X₂, что каждое ребро имеет одну концевую вершину в подмножестве X₁, а другую – в надмножестве X₂. Подмножества X₁ и X₂ в данном случае называются долями. Если две вершины графа, входящие в разные доли, смежны, то граф называется полным двудольным и обозначается К_n1,n2, где n₁=|X₁|, n₂=|X₂|. Аналогично определяются k-дольный и полный k-дольный графы (k>2). Граф является двудольным тогда и только тогда, когда он не имеет простых циклон нечетной длины.

Реберным (смежностным) графом простого графа G=(X, U) называется граф L(G)=(U, V), вершинам которою соответствуют ребра графа G, причем все вершины u_i и u_j графа L(G) смежны тогда и только тогда, когда смежны соответствующие им ребра u_i и u_j графа G.

Достижимость и связность.

Вершина x_j неорграфа (орграфа) достижима из вершины x_j, если существуем маршрут, соединяющий х_i и х_j (путь из х_i в х_j). Если в орграфе существуют пути из х_i в х_j и обратно, то говорят, что вершины х_i и х_j взаимно достижимы.

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