Материал: Diskretnaya_matematika

Ориентирован­ное ребро называют дугой графа (рис. 3.2).

Рис. 3.2. Дуга ориентированного графа

Граф называется неориентиро­ванным или неорграфом, если каждое ребро его не ориентированно, иориентирован­ным или орграфом, если каждое ребро его ориенти­рованно. Если граф содержит ори­ентированные и неориентирован­ные ребра, он называетсясмешанным.

Полным неориентированным графомназывается графU(X), ребрами которого являются всевозможные пары (x_i,x_j) для всех возможных вершинx_i,x_jX,ij. В таком графе все вершины являются смежными (рис. 3.3).

Рис. 3.3. Полные неориентированный и

ориентированный графы

Полным ориентированным графом U₀(X) называ­ется граф, у которого любые две вершины соединены хотя бы в одном направле­нии.

Петлей называется ребро g = (x_i, x_i), у которого начальная и конечная вершины совпадают (рис. 3.4) Петля обычно считается неориентиро­ванной.

Рис. 3.4. Петля

Мультиграфомназывается граф, в котором пара вершин соединяется несколькими различными ребра­ми или дугами (рис.3.5).

Рис. 3.5. Неориентированный и ориентированный мультиграфы

Дополнением графа G(X) является такой граф G_d(X), ко­торый совместно с графом G(X) образуют полный граф: U(X) = G(X)  G_d(X).

3.1.3. Маршруты в графах

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

Для неориентированных графов справедливы следующие понятия.

Цепь– последовательность реберS= (g₁,g₂, ...,g_n), в которой у каждого ребраg_kодна из вершин явля­ется вершиной ребраg_k-1, а другая - вершиной ребраg_k+1. При этом одно и то же ребро или вершина может встречаться несколько раз. Пример цепи для графа (рис. 3.6):

S = (g₀, g_l, g₂, g₃, g₄, g₅, g₂, g_б) = ((x₀, х₁), (х₁, х₂), (х₂, х₃), (х₃, х₁), (х₁, х₄), (х₄, х₃), (х₃, х₂), (х₂, х₅)).

Рис. 3.6. Пример цепи

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

Цепь назы­вается элементарной, если в ней ни одна из вершин не повторяется.

Циклом называется конечная цепь, начинающаяся на некото­рой вершине х_i, и окачивающаяся на ней же. Простые, сложные и элементарные циклы определяются по аналогии с цепями.

Для ориентированных графоввведены следующие дополни­тельные понятия.

Путемв графеG(X) называется такая последовательность дуг (g_l,g₂, …), что конец каждой предыдущей дуги является началом следующей. Существуют простые, сложные и элементар­ные пути.

Х|

Длина пути есть число дуг L(s) в последовательности дуг пути s. В случае бесконечного пути L(s) = .

Граф называетсясимметрическим,еслиx_i,x_j из того, чтоx_iG(x_j)x_jG(x_i), то есть две смеж­ные вершиныx_i,x_jвсегда соединены противоположно ориентирован­ными дугами (рис.3.7).

Рис. 3.7. Симметрический граф

Граф называется антисимметрическим, еслиx_i,x_j x_iG(x_j)x_jG(x_i), то есть каждая пара смежных вершин соединена только в одном направлении.

Граф называется конечным, если число его вершин конечно ибесконечным,если число вершин бесконечно. ГрафG(X) называетсяG – конечным, если для каждой его верши­ны хXмножествоG(x) конечно.

3.1.4. Частичные графы и подграфы

Граф Н(х) называется частичным для графа G(X), если все ребра Н(Х) являются ребрами G(X) и множество вершин графа Н(Х) совпадает с множеством вершин графа G(X), то есть Н(х)  G(x)  х  X (рис.3.8).

Рис. 3.8. Граф G(X) и частичный для него граф Н(Х)

Частичный граф содержит часть ребер(дуг). Он также может быть ориентированным или неориентированным в зависимости от исходного графа.

Отметим, что ноль-граф графа G(X) считается его частичным гра­фом. Все частичные графы Н(Х) дляG(X) можно получить, выбирая в качестве ребер Н(Х) всевозможные подмноже­ства множества ребер графаG(X).

ПодграфомG_A(A) графаG(X), где АX, называется граф, вершинами которого являются элементы множества АX, а ребра­ми ­– все ребра изG, концевые вершины которых лежат в А (рис.3.9).

Хо

Рис. 3.9. ПодграфG_A(A) графа G(X)

Таким образом, под­граф содержит часть вершинвместе с ребрами, со­единяющими эти вершины. Иначе,G_A(A) – подграф графаG(X), если АXиG_A(x) =G(x)Ах Х.

Если А = X, тоG_A(A) =G(X). Для единственной вершины А = {а} подграфG_A(a) со­стоит из петель вокруг а. Под­графомG_A(A) графаG(X) будет ноль-граф, если АXесть подмножество изолированных вершин графа.

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

Рис. 3.10. Частичный подграф Н_А(А) графа G(X)

Частичным подграфом Н_А(А), А  X графа G(X) называется подграф (рис. 3.10), ребрами которого являются некоторые ребра из G(X), оба конца которых лежат в А. Иначе, Н_А(А) – частичный под­граф графа G(X), если А  X и Н_А(х)  G(x)  A  х  Х.

Дополнительным частичным графом Н(А) графа G(X) явля­ется единственный граф, состоящий из ребер графа G(X), не при­надлежащих некоторому частичному подграфу Н_А(А) графа G(X) (рис. 3.11).

3.1.5. Связность в графах

Рассмотрим вопрос о связности в графах. Пусть G(X) – неори­ентированный граф. Две вершины х_iиx_jназываютсясвязными, если существует цепьSс концами х_iиx_j. ЕслиSпроходит через некото­рую вершинуx_kболее одного раза, то можно удалить цикл в верши­неx_kиз цепиS. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.

Неориентированный граф называется связным, если любая па­ра его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности (x_i~x_j, х_j~ х_kx_i~ х_k).

Компонентой связ­ностинеориентирован­ного графаG(X) называ­ется подграф Н_А(А) графаG(X) с множеством вер­шин АXи множеством ребер вG(X), инцидент­ных только вершинам из А, причем ни одна вершинаx_i А не смежна с вершинами из множества Х \ А (рис. 3.12).

Рис. 3.12. Граф с двумя компонентами связности

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

Компонентой сильной связностиориентированного графаG(X) называется подграф Н_А(А) графаG(Х) (подчиняющийся опре­делению сильно связного графа) с множеством вершин АХ и мно­жеством дуг, имеющих начало и конец в А, причем ни одна из вер­шин х_iА и х_jX\ А не смежны между собой (рис. 3.13).

Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности

Очевидно, что ориентированный граф G(X) сильно связан то­гда и только тогда, когда он имеет одну компоненту связности.

На практике широко используются такие виды графов, как де­ревья и прадеревья.

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

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

Рис. 3.14. Дерево

Лесом называется несвязный граф, каждая компонента связно­сти которого является деревом.