Курсовая работа: Графы и их представление на ЭВМ

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

G ( V , E ) = { V, E}, V ¹Æ, E Ì V´V, E = E^-

Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки. На рис. 1.1А и 1.1Б приведены примеры обычного и ориентированного графа.

Число вершин графа A обозначим р, а число ребер – q :

p: = p( A) : = |V|, q: = = q( A) : = |E|;

Более простое определение графа - совокупность точек и линий, в которой каждая линия соединяет две точки. Для ориентированного графа E  V_x - конечный набор ориентированных ребер. Ребром может быть прямая или кривая линия. Ребра не могут иметь общих точек кроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку из множества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V. Если V и E конечные множества, то и граф им соответствующий называется конечным . Граф называется вырожденным , если он не имеет ребер. Параллельными ребрами графа называются такие, которые имеют общие узлы начала и конца.

1.2 Смежность

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

Пусть v ₁ , v ₂ — вершины, е = (v ₁ , v ₂ ) — соединяющее их ребро. Множество вершин, смежных с вершиной v , называется множеством смежности вершины v и обозначается Г⁺ ( v ):

Г⁺ ( v ) : = {uÎV|(u , v ) ÎE}

Г( v ) : = Г^* ( v ) : = Г⁺ ( v ) È{v }

u ÎГ( v ) Ûv ÎГ( u )

Замечание. Если не оговорено противное, то подразумевается Г⁺ и обозначается просто Г.

Если А Ì V — множество вершин, то Г (А) — множество всех вершин, смежных с вершинами из А:

Г (А) : = {uÎV|$vÎAuÎГ ( v)};

1.3 Другие определения

Часто рассматриваются следующие родственные графам объекты.

1.Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.

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

3.Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом.

4.Если элементами множества Е являются не обязательно двухэлементные, алюбые подмножества множества V , то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.

5.Если задана функция Е: V ® М и/или F : Е ® М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

2. Способы задания графов

2.1 Изображение графа

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

Граф G называется плоским , если его можно отобразить в плоскости без пересечения его граней. Очертанием графа (face) считается любая топологически связанная область, ограниченная ребрами графа.

Неориентированный граф G = <V,E> называется связанным , если для любых двух узлов x,y О V существует последовательность ребер из набора E, соединяющий x и y. Граф G связан тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы обе граничные точки каждого ребра находились в одном и том же подмножестве. Граф G называется k-связным (k і 1), если не существует набора из k-1 или меньшего числа узлов V`Н V, такого, что удаление всех узлов V` и сопряженных с ними ребер, сделают граф G несвязанным.

Теорема Менгера : граф G является k-связанным тогда и только тогда, когда любые два различные узла x и y графа G соединены по крайне мере k путями, не содержащими общих узлов. k-связанные графы представляют особый интерес для сетевых приложений. Определенную проблему составляет автоматическое отображение графа на экране или бумаге. Кроме того, для многих приложений (например, CAD) все узлы графа должны совпадать с узлами технологической сетки. Возникают и другие ограничения, например необходимость размещения всех узлов на прямой линии. В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаные линии, состоящие из отрезков прямых.

2.2 Способы численного представления графа