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

1. Граф - это система некоторых объектов вместе с некоторыми парами этих объектов, изображающая отношения связи между ними. Неориентированный граф (соответственно ориентированный граф, или орграф) G - система G = (V, E, Г), состоящая из множества элементов V= {v}, называемых вершинами графа, множества элементов Е = {е}, называемых ребрами, и отображения , ставящего в соответствие каждому элементу неупорядоченную (соответственно упорядоченную) пару элементов называемых концами ребра е.

Для неориентированного графа значение V₁ и V₂ может быть произвольным. Для ориентированного – V₁ - начало пути, V₂ - конец.

образует множество элементов графа; при этом предполагается, что

Отображение Г определяет отношение инцидентности ребра с каждым из своих концов. Для графа G = (V, Е, Г) употребляется также более короткое обозначение G = (V, Е) без указания инцидентностей, которые определяются контекстом.

Если - упорядоченная пара при v₁ - v₂), то ребро е называется ориентированной дугой, исходящей из вершины v₁ и входящей в вершину ; называется началом, а концом дуги е. Если – неупорядоченная пара, то ребро е называется неориентированным.

Всякому графу G можно поставить в соответствие соотнесенный неориентированный граф с теми же множествами V и Е и инцидентностями, но все пары неупорядоченные.

Вершина, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми, или висячими.

Ребро с совпадающими концами называется петлей.

Две вершины, инцидентные одному и тому же ребру, называются соседними (или смежными). Два ребра, инцидентные одной и той же вершине, называются смежными.

Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными, или параллельными.

2. Графы могут различаться и не различаться. Обычно это связывают с понятием изоморфизма графов.

Два графа называются изоморфными, если существуют взаимно однозначные отображения сохраняющие инцидентность, т.е. е Є E₁

3. Существует несколько способов задания графов:

1) Перечисление (список) ребер графа с указанием их концов и добавлением списка изолированных вершин.

2) Матрица инциденций графа с b вершинами и p ребрами - прямоугольная матрица с b строками и p столбцами, строки которой соответствуют вершинам графа, а столбцы - ребрам, причем j для неориентированного графа элемент матрицы равен 1, если вершина и ребро инцидентны, и равен 0 в противном случае. Для ориентированного графа если является началом дуги = +1, если v. - конец дуги Вкаждом столбце матрицы инциденций -два ненулевых элемента, если ребро - не петля. Петле соответствует элемент, равный 2.

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

4) Для наглядности граф часто представляют в виде геометрического объекта: вершинам соответствуют различные выделенные точки в пространстве (на плоскости), ребрам - отрезки кривых, связывающие соответствующие точки и не проходящие через выделенные точки, отличные от их концов.

5. Граф называется подграфом графа обозначение: если и для множеств сохраняются инциденции графа G. При этом, очевидно, каждое ребро из Е' входит в подграф Н вместе со своими концами.

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