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

Пусть х — не пустое множество и Х — некоторый набор пар элементов из V вида (х, щ), х, щ Ђ V. Элементы множества V — вершины, множества X — ребра графа.

X = {(х1, х2), (х2, х3), (х1, х4), (х4, х4)}.

Ребро вида (х, х) называется петлей, одинаковые пары во множестве X называются кратными ребрами.

Количество одинаковых пар (х, щ) называется кратностью ребра х, щ.

Множество V и набор Х определяют псевдограф G (V, X), т. е. граф с кратными ребрами и петлями.

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

Если во множестве X нет кратных ребер, то G (V, X) называется графом.

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

Ребра орграфа называются дугами.

Если граф не ориентированный и х = (х, щ) — ребро, то вершины х и щ называются концами ребра х.

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

Вершина х и ребро х называются инцидентными.

Вершины х и щ называются смежными, если они имеют общую вершину.

Степенью вершины х называется число д (х) ребер графа инцидентных данной вершине.

Вершина, имеющая степень 0 называется изолированной, 1 — висячей.

Последовательность хi1xi1, хi2xi2, …, хikxik, хik+1, k? 1, хij € V, xij € X, в которой чередуются вершины и ребра (дуги) и ребро xij (хij, хij+1) называется маршрутом, соединяющим вершины хi1 и хik+1.

хi1 называется начальной вершиной. хik+1 называется конечной вершиной. Остальные — внутренние.

Одна и та же вершина может быть одновременно и начальной, и конечной, и внутренней.

Если нет кратных ребер, то маршрут однозначно восстанавливается по последовательности вершин.

Для орграфа маршрут называется путь.

Число ребер или дуг в маршруте (пути) называется его длинной.

Маршрут называется замкнутый, если начальная и конечная вершины совпадают.

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

Цепь, в которой все вершины попарно различны называется простой.

Замкнутый маршрут, в котором все ребра попарно различны называется циклом.

Цикл, в котором внутренние вершины попарно различны называется простым.

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

Пусть ?(х, x) — граф.

V = {х1, х2, …, хn}.

X = {x1, x2, …, xn}.

Матрицей смежости называется квадратная матрица, А n — ого порядка, элементы которой определяются формулой:

A = (aij) aij = 1, (хi, хj) Ђ X.

0, (хi, хj) не € X

Если дан псевдограф, то aij = 0, (хi, хj) € X.

k, k — кратность ребра Матрицей инцидентности называется матрица В размера M x N, элементы которой определяются по формуле:

B = (bij) bij = 0, хi не инцидентна xj.

• 1, хi есть конец дуги xj
• -1, хi есть начало дуги xj

Пусть D — ориентированный мультиграф с непустым множеством дуг, тогда:

• 1) сумма строк матрицы B (D) есть нулевая строка
• 2) любая строка B (D) есть линейная комбинация остальных
• 3) ранг матрицы B (D) не превосходит числа вершин — 1 (минус 1)
• 4) для любого контура в D сумма столбцов матрицы B (D) соответствующих дугов входящих в этот контур равна нулевому столбцу.

A (G) — матрица смежности.

Ak (G) = A * A * … * A.

Элемент qkij матрицы Ak (G) ориентированного псвдографа равен числу всех путей длины k из вершины хi в хj.

Теорема: для того, чтобы n — вершинный орграф D с матрицей смежности A (D) имел хотя бы один контур необходимо и достаточно, чтобы матрица k = A2 + + A3 + … + An имела не нулевые диагональные элементы.

Объединением графов G1(V1, X1) и G2(V2, X2) называется граф.

G = G1 U G2 (V1UV2, X1UX2).

Пересечением графов G1 и G2, где V1 — пересечение V2? Ш называется граф (V1?V2 = Ш) G1? G2 (V1?V2, X1? X2).

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G.

Подграф называется собственным, если он отличен от самого графа.

Вершина щ орграфа D (графа G) называется достижимой из вершины V, если существует путь (маршрут) из V в щ или V = щ.

Граф называется связным, если для любых двух его вершин существует маршрут, соединяющий их.

Компонентой связности графа G называется его связный подграф не являющийся собственным подграфом никакого другого связанного подграфа.

Пусть орграф D имеет множество вершин V = {V1, V2, …, Vn}.

Матрицей достижимости орграфа D называется квадратная матрица T (D) порядка n, у которой tij = 1, хj достижимо из хi.

0, хj не достижимо из хi.

Матрицей связности S (D) орграфа D называется квадратная матрица порядка n, у которой Sij = 1, хj достижимо из хi, хi достижимо из хj.

0, в противном случае.

Матрицей связности неориентированного графа G называется квадратная матрица S (G) порядка n у которой:

Sij = 1, если i = j или если существует маршрут, соединяющий Vi и Vj.

0, в противном случае.