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

1.1.2 Матричный способ задания графов

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

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

В псевдогр

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

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

1.1.3 Изоморфизм и гомеоморфизм графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Числом вершинной связности δ(G) графа называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. Числом реберной связности δ(G) называется наименьшее число ребер, при удалении которых граф становится несвязным. δ*(G) < δ*(G) < p*(G), где p*(G) – минимальная степень вершин графа.

 Скачать реферат