Действия над графами ]

Сопоставим каждой вершине (V={ / і = 1,2, …, m} графа G = <V Ui, U₂> вес Wi из множества весов W = { Wi / i = 1.2.3 …} В результате получим множество взвешенных вершин {( ,W / i = 1.2. … n)}.. При этом не обязательно, чтобы все веса были различными.

Сопоставим каждому элементу множества U₂= {u_i / i = 1,2 …m} вес p_i из множества весов Р= {p_i / i =1,2,…} . В результате получим множество взвешенных дуг {(u_i , p_i) / i = 1.2…., m}. При этом не обязательно, чтобы все веса были различными.

Определенные выше множества взвешенных вершин и дуг определяют в совокупности взвешенный граф G = <( ,W),(U P)>, V = V U Ui, U = U₂ , который, строго говоря, является уже не графом, а функцией, опре­деленной на вершинах и дугах графа.

Совсем не обязательно, чтобы были взвешены одновременно вер­шины и дуги.

К ласс матриц инциденций. Если граф G содержит n вершин и m дуг, то матрица инциденций A(G) = определяется следующим образом:

Граф может содержать петли, т.е. дуги вида ( ). В этом случае некоторые элементы матрицы А одновременно равны и I, и -I, что приводит к неоднозначности элементов матрицы А.

В таких случаях матрицу А разбивают на две матрицы А⁺ и А":

.

Если граф без петель, то А = А⁺ - А^-. Матрицы А⁺ и А^- описывают граф без учета весов вершин и дуг.

Веса вершин графя G задаются в виде столбцевой матрицы

а веса дуг - в виде диагональной матрицы

Матрицы А⁺, А^-, w, Р полностью описывают взвешенный граф

К ласс матриц смежности. Матрица смежности S = невзвешенного графа определяется следующим образом:

Для взвешенного графа

Матрицы S, W, Р полностью описывают взвешенный граф. Пример I. Задать граф, изображенный на рис.2.1, матрицей инциденций и матрицей смежности.

□ Используя определения матриц инциденций и смежности, построим эти матрицы. Они имеют вид:

Пример 2. Задан неориентированный граф G < V, U> , у кото-рого Задать этот граф матрицей инциденций и матрицей смежности. □Заданный граф G показан на рис.2.2 Искомые матрицы имеют вид :

Пример 3. Задана логическая схема, реализующая сложение по модулю два f(х₁, х₂)=: х₁ х₂ в базисе Шеффера

(рис.2.3). Построить взвешенный граф G = <V, W), U> , в котором вершины взвешены переменными х₁, х₂, функциональной переменной элемента Шеффера и функциональной переменной f соответственно. Начало дуги соответствует переменной х₁, х₂ или выходу элемента Шеффера, конец дуги - входу элемента Шеффера или функциональной переменной

f . Задать построенный взвешенный граф матрицами инциденций, смежности и весов.

Используя определения матриц инциденций и смежности, построим искомые матрицы.

Матрица инциденций имеет вид:

Матрица смежности и матрица весов вершин имеют вид:

□ Используя условие задачи, построим взвешенный граф G (рис.2.4)

При задании графя G отсутствует матрица Р(G), т.к. дуги этого графа не взвешены.■ Объединением гряфов G_a=<V_а, U_a> и G_b = <V_b U_b> называется граф G = <V, U >, у которого и .

Пример 4. Заданы граф G_a=<V_а, U_a> , у которого V_а={ a, b}. U_а={a, b} и граф G_b = <V_b U_b> , у которого V_b = { a, d, c}, U_b = {(a ,d, (a, c), (d, c)}.. Найти объединение этих графов, т.е. G_a G_b. □ По определению

G_a G_b.= G = <V, U >, где и . Зная V и U, всегда можно построить граф G , который показан нарис.2.5.

Рис. 2. 4

В полном двудольном графе каждая вершина из подмножества V_К1 соединена с каждой вершиной из V_К2 , т.е. Граф K_1,2 показан на рис.2.6.

Рис .2.5

Суммой графов G_a=<V_а, U_a> и G_b = <V_b U_b> называется граф G = < V, U > , представляющий собой объединение графов G_a , G_b и полного двудольного графа K_m,n , построенного на носителях V_а \ V_а V_b и V_b \ V_а V_b .Другими словами, при построении суммы графов G_a и G_b определяется их объединение и каждая вершина V_a , не вошедшая в пересечение V_а V_b, соединяется со всеми вершинами V_b, не вошедшими в пересечение V_а V_b и наоборот.

Пример б. Найти сумму графов G_a и G_b, заданных в примере 4. □ По определению G_{a +} G_b = G = G_a G_b К_m,nи G = < V, U > Тогда V= V_a V_b V_К, U= U_a U_b U_К - это множество вершин и множество ребер полного двудольного графа К_{т п} соответственно. V_а, V_b, U_a, U_b известно, значит, требуется найти V_К и U_К, т.е. полный двудольный граф K_m,n . В двудольном графе множество вершин разбито на два непересекающихся подмножества V_К1 и V_К2, т.е. V_К= V_К1 V_К2, причем V_К1 = V_а \ V_а V_b V_К2= V_b \ V_а V_b. Это следует из определения суммы графов . V_а V_b = {a,b} {a,d,c}= {a}, V_К1={a,b} \ {a}= {b}, V_К2= {a,d,c} \ {a}= {d,c}, V_К={b} {d,c} = {b,d,c}.

Рис.2.6

Теперь можно определить V и U искомого графа G • V= V_a V_b V_К={a,b} {a,d,c} {b,d,c}= {a,b,d,c} U= U_a U_b U_К={(a,b)} {(a,d,(a,c),(d,c)} {(b,d), (d,c)}= {(a,b),(a,d),(a,c),(d,c),(b,d),(b,с)}.

На рис.2.7 показан искомый граф G.

Рис.2.7

Здесь тонкими линиями выделены ребра графа, который является объединением графов G_a и G_b (ср. с рис.2.5), жирными линиями - ребра двудольного графа К_1,2 . ■

Произведением (декартовым произведением) графов и называется граф G = <V, U >, у которого V = х = Г = Г . Пример 6. Найти декартово произведение графов и ,.если V_a={a,b}, U_a={(a,b)}, V_b ={1.2,3 , U_b = {(1,2),(1,3),(2,3)}.

□ Так как в определении произведения графов фигурируют окрестнос-ти и , а в условии задачи нет, то для нахождения Г_а и построим графы и (рис.2.8):

Рис.2.8

Искомым графом будет граф G = < V, Г > . Найдем V и Г . V = х = {а,b} х {1,2,3} = {(а,1),(а,2),(а,3),(b,1),(b,2),(b,3)}. Теперь найдем окрестность для каждой найденной вершины графа G:

Г(а,1)=Г_а х Г₁={b} х {2,3} = {(b,2),(b,3)} , Г(а,2)=Г_а х Г₂={b} х {1,3} = {(b,1),(b,3)}, Г(а,3)=Г_а х Г₃={b} х {1,2} = {(b,1),(b,2)} , Г(b,1)=Г_b х Г₁={a} х {2,3} = {(a,2),(a,3)} , Г(b,2)=Г_b х Г₂={a} х {1,3} = {(a,1),(a,3)} , Г(b,3)=Г_b х Г₃={a} х {1,2} = {(a,1),(a,2)} , Зная множество вершин V и множество окрестностей Г этих вершин, всегда можно построить граф. Искомый граф G показан на рис.2.8.1

Задачи для самостоятельного решения

1. Два автомобиля направляются в город f . Первый автомобиль едет из города а через города с,e, d в город f , а второй из города b через города с, d,e в f. Построить взвешенный граф, соответствующий маршрутам автомобилей, если между городами a и c, b и c расстояние 5 км, с и е - 7 км, с и d - 10 км, е и d - 15 км, d и f - 20 км, е и f - 9 км и городя а, b, c, d, e и f имеют соответственно 2,3,4,3,2 и 1 автозаправочные станции. Задать построенный взвешенный граф матрицами инциденций, смежности и матрицами весов.

2. Задать неориентированный граф G = <V, U >, у которого V={a ,b, c, d, e ,f, g}, U={(a,b),(a,c),(b,d),(a,e),(b,f),(c,d),(c,e),(d,f),(e,g),(f,g)}, матрицами инциденций и смежности.

3. Найти объединение графов G₁ = <V₁, U₁ > и G₂ = <V₂, U₂ >,если V₁={a ,b, c}, U₁={(a,b),(a,c),(b,c)}, V₂={a , e ,f, g}, U₂={(d,e), (d,f), (d,g),(e,f), (e,g), (f,g).,

4. Найти сумму графов G₁ и G₂, указанных в задаче 3.

5. Найти декартово произведение графов G₁ и G₂, указанных

в задаче 3

3. СВЯЗНОСТЬ И СИЛЬНАЯ СВЯЗНОСТЬ ГРАФА

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

Цепью называется последовательность ребер (ρ₁, ρ₂…, ρ_n) вида ρ_i= , i=1,2, …, n (рис.3.1а). Вершины цепи могут иметь степень, равную 1. Вершина со степенью, равной 1., называется концевой.

Число ребер цепи, соединяющей вершины и называется ее

длиной l( , ).

Цепь называется составной, если в ней повторяется хотя бы одно ребро (рис.3.16), сложной, если хотя бы одна вершина (рис.З.1в), и простой - в противном случае (рис.3.1а).

Рис.3.I

Из рис.3.1б видно, что при прохождении из вершины в вершину через все вершины цепи ребро ( , ) проходится дважды. На рис.З.1в показано, что при прохождении из вершины в .

через все вершины цепи вершина проходится дважды.

Циклом называется цепь, концевые вершины которой совпадают (рис.3.1г).

Циклы бывают составными, сложными, простыми. Поэтому все вер-шины цикла имеют степень s( )≥2.

Граф G = <V, U > называется связным, если любая пара его вершин соединена цепью (рис.3.2а).

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

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

Рис.3.2

Минимальная длина цепи, соединяющей вершины и , называется расстоянием r( , ) между вершинами и :

r( , )= ( , )

Пример I, На рис.3.3 показана цепь. Найти расстояние между вершинами и

Рис.3.3

□ Из вершины можно пройти в вершину по ребрам ρ₁, ρ₅, по ребрам ρ₁, ρ₂, ρ₆ , по ребрам ρ₁, ρ₂, ρ₃, ρ₄. Значит

l₁( , )=2, l₂( , )=3, l₃( , )=4

Согласно определению расстояния r( , ) между вершинами и r( , )= 2 _■ Максимальное расстояние между вершинами графя G называется диаметром графя d(G).

Пример 2. Найти диаметр графа G = < V, U > , если □Заданный граф изображен на рис.3.4

Рис.3.4 Рис.3.5

Определяем расстояния между вершинами: r( , )= 1 r( , )= 1 r( , )= 1 r( , )= 2 r( , )= 1 Максимальным расстоянием является расстояние между вершинами и . Значит d(G) = 2. ■

Цикл называется эйлеровым, если каждое ребро графа участвует в его образовании один раз; граф, содержащий такой цикл, называется эйлеровым.

Теорема. Граф G = < V, U > является эйлеровым тогда и голько тогда, когда он связен и степень каждой вершины V, s( ) - четное число. Пример 3. Является ли граф G = < V, U > , у которого эйлеровым ?

□ Заданный граф показан на рис.3.5.

Из рисунка видно, что граф связен (любая пара его вершин соединена цепью или граф состоит из одной компоненты связности) и вер-шины имеют следующие степени:

s( )=2, s( )=4, s( )=2, s( )=4, s( )=2 То есть степени всех вершин равны четному числу. Согласно теореме граф является эйлеровым. Заданный граф содержит эйлеровый цикл 3начит, граф эйлеровый. ■

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

Пример 4. Является ли граф G , указанный на рис.3.6, гамиль-тоновыым?

Рис.3.6

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

■

Разделяющим множеством связного графа G называется такое множество его ребер, удаление которых из G делает его несвязным,

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

Разрез (коцикл), состоящий из одного ребра, называется мостом.

Пример 5. Является ли множество ребер { ρ₃, ρ_5, ρ₉, ρ₇} графа G, указанного на рис.3.7, разрезом?

Рис.3.7

□ Граф G с удаленными ребрами ρ₃, ρ_5, ρ₉, ρ показан на рис.3.8а.

Из рисунка видно, что граф стал несвязным (имеет две компоненты связности). Значит, множество ребер {ρ₃, ρ_5, ρ₉, ρ₇} является разделяющим множеством. Но это разделяющее множество не является разрезом (коциклом), т.к. оно содержит собственное разде-ляющее подмножество { ρ_5, ρ₉, ρ₇}. Действительно, удаление ребер ρ_5, ρ₉, ρ₇ делает граф G несвязным. Множество ребер { ρ_5, ρ₉, ρ₇}. не содержит собственного разделяющего подмножества, поэтому это множество ребер является разрезом (рис.3.8б). ■

Рис. 3.8