Подграфы и изоморфизм.. Теоретическая справка

Подграфы и изоморфизм.

 

Цель работы: изучение основных понятий теории графов и приобретение практических навыков определения изоморфизма графов, построение подграфов, независимых множеств и клик.

 

Теоретическая справка

 

Пусть V – некоторое непустое множество (V ¹ Æ).

V⁽²⁾ – множество всех его дву элементных подмножеств (V⁽²⁾={(u,v)|u,vÎV, неупорядоченная пара}).

 

Неориентированный граф G – пара множеств (V,E), E Í V⁽²⁾ ,

где V – множество вершин графа G,

E – множество рёбер графа G.

Если |V|=p, а | E|=q, то обозначают граф G – (p, q)- граф или p -граф.

 

Смежные вершины графа G – вершины, соединенные ребром.

 

Смежные ребра графа G – ребра, имеющие общую вершину.

 

Инцидентные ребро и вершина – вершина является одним из концов ребра.

 

Конечный граф – множество вершин графа конечно.

 

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

 

1. Перечисление вершин V и ребер E.

 

2. Графически: прообраз вершины – точка, прообраз ребра – отрезок.

 

3. Матричные способы описания.

Матрица смежности.

A=||a _ij||, i, j = 1.. p, | V |= p, | E |= q.

1, если существует ребро (i,j);

a _ij =

0, иначе.

Матрица инцидентности.

B=||b _ij ||, i=1.. p, j=1.. q, |E|=q, |V|=p.

1, вершина i инцидентна ребру j;

b _ij =

0, иначе.

Например:

Задан граф G=(V, E), где

 

V={a, b, c, d},

E={ab, bc, ac, ad, dc}.

 

 

М атрица смежности

 

	a	b	c	d
B= A= a
b
c
d

 

 

Матрица инцидентности

	ab	bc	ac	ad	dc
a
b
c
d

 

Степени вершин графа

Степень вершины deg(v) графа G – число инцидентных ей ребер.

 

Максимальная степень всех вершин графа G – D(G):

D(G)=MAX deg(v).

vÎV

 

Минимальная степень всех вершин графа G – d(G):

d(G) = MIN deg(v).

vÎV

Лемма о рукопожатиях:

	Сумма степеней всех вершин графа G четна и равна удвоенному числу ребер.

 

Изолированная вершина графа G – вершина, степень которой равна 0.

 

Висячая вершинаграфа G – вершина, степень которой равна 1.

 

Доминирующая вершина графа G – вершина, степень которой равна p-1, где p – количество вершин графа G.

 

Например:

 

		доминирующей нет висячие - v3, v4 изолированная - v5

 

 

 

 

 

Экстремальные графы

Полный граф – любые две вершины смежны. Обозначается, K_n.

 

Например:

 

 

 

Пустой граф – не имеет ребер. Обозначается через O_n.

 

Мультиграф – граф, не содержащий петель, но с кратными ребрами.

 

Псевдограф – граф, содержащий петли и кратные ребра.

 

Например:

Нуль-граф – граф без вершин и без ребер.

 

Тривиальный граф – граф с одной вершиной (1,0 -граф).

 

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

 

 

Например:

 

Двудольный граф – множество вершин графа можно разбить на два непересекающиеся подмножества V₁ и V₂ таких, что каждое ребро имеет одну концевую вершину в V₁, а вторую – в V₂, причем V₁ÇV₂=Æ, а V₁ÈV₂=V.

Полный двудольный граф – двудольный, у которого любые две вершины, входящие в разные доли - смежны. Обозначается K_{p, q}.

Звезда – полный двудольный граф, у которого p=1. Обозначается K_1,q.

 

Биграф - двудольный граф.

 

Например:

 

Граф G(V,E) называют k -дольным, если множество его вершин V можно разбить на такие подмножества V_i, i= 1..n, что любое ребро графа имеет одну концевую вершину в V_i, а другую - V_j, причём V_i ÇV_j = Æ, i ¹ j, i,j=1..n, а V_i=V.

 

Например:

Изоморфизм графов.

Изоморфные графы – существует взаимно однозначное соответствие, т. е. биекция, между множествами их вершин, сохраняющая отношение смежности.

Изоморфизм графов G и H: G @ H.

 

 

Например:

 

Заданы два графа G₁, G₂. Определить изоморфизм G₁, G₂, построив биекцию их вершин.

 

Решение:

Граф G₁ изоморфен графу G₂, потому что существует биекция j: V₁ ® V₂, сохраняющая отношение смежности.

 

Биекция j: u Î V1	a	b	c	d
j (u) Î V2	c	d	b	a

 

 

Например:

1 2 3 6 1

4 5 6 4 3

Биекция j: u Î V1
j (u) Î V2

Изоморфно вложимый граф G1в G, если граф G1 изоморфен некоторому

порожденному подграфу графа G.

 

Например:

G1

 

Подграфы

Помеченный граф – граф, у которого каждой вершине поставлена в соответствие некоторая уникальная отметка (символ, цифра), иначе – абстрактный.

 

Дополнение графа G - граф G' = (V', E'), такой, что V=V', а E'= V⁽²⁾ \ E ( вершины смежные в G' не смежны в G и наоборот).

Подграф G₁ = (V₁, E₁) графа G = (V, E) – граф, у которого все вершины и ребра удовлетворяют следующим соотношениям V₁ Í V, E₁ Í E.

 

 

Остовный подграф графа G - подграф, содержащийвсе вершины графа G, множество ребер есть подмножество ребер графа G.

Порожденный подграф (порожденный подмножеством вершин V₁) – подграф, множество вершин которого V₁ Í V, а множество ребер Е₁ содержит все ребра графа G, инцидентные выбранным вершинам V₁.

 

ДополнениеG'

c

b

d

a

Например:

 

Независимые множества

 

Независимое множество вершин – множество вершин графа G: SÍV такое, что любые две вершины в нем несмежны, то есть никакая пара вершин не соединена ребром.

 

подграф, порожденный независимым множеством – пустой граф.

 

Максимальное независимое множество – не является собственным подмножеством другого независимого множества.

Наибольшее независимое множество – наибольшее по мощности среди всех независимых множеств.

Число независимости a(G) графа G – мощность наибольшего независимого множества.

 

Например:

Граф G:

Максимальные независимые множества:

S₁={X₁, X₄};

S₂={X₁, X₃, X₇};

S₃={X₁, X₅, X₇};

S₄={X₂, X₄ , X₈};

S₅={X₂, X₅, X₇, X₈};

S₆={X₃, X₇, X₈};

S₇={X₃, X₆};

S₈={X₄, X₆}.

Наибольшее независимое множество: S₅={X₂, X₅, X₇, X₈}.

Число независимости графа G: a(G) =4.

 

Клика

 

Клика – антипод независимого множества. Подмножество вершин графа G такое, что любая пара из этого множества является смежной.

подграф, порожденный кликой – полный граф.

Максимальная клика – не является собственным подмножеством никакой другой клики графа G.

 

Наибольшая клика – наибольшая по мощности среди всех остальных клик графа G.

Кликовое число или плотность j(G) графа G – мощность наибольшей клики.

Например:

Граф G

клики графа G:

	a

S₁={a,b,с};

S₂={b,d,e};

S₃={b,c,e};

S₄={b,d,c};

S₅={c,d,e};

S₆={b,c,d,e}.

 

Максимальные клики: S₁={a,b,с}, S₆={b,c,d,e}.

Наибольшая клика: S₆={b,c,d,e}.

Кликовое число: j(G) =4

 

 

Доминирующие множества

 

Доминирующее (внешне устойчивое) множество – подмножество V’ÌV вершин графа такое, что каждая вершина из V\V’ смежна с некоторой вершиной из V’. Иначе, каждая вершина графа находится на расстоянии не более одного ребра от данного множества.

 

Минимальное доминирующее множество – нет другого доминирующего множества, содержащегося в данном.

 

Наименьшее доминирующее множество – доминирующее множество с наименьшей мощностью.

Число доминирования b(G) – мощность наименьшего доминирующего множества.

 

Например:

Минимальные доминирующие множества:

 

S₁={X₁, X₄}

S₂={X₄, X₅}

S₃={X₂, X₃, X₆}

S₄={X₃, X₅, X₆}

 

 

наименьшее доминирующее множество: S₁={X₁, X₄}.

Число доминирования: b(G)=2.

Задание к лабораторной работе

 

1. Используя алгоритм генерации варианта GV (приложение А), построить неориентированный граф G: GV(7,{2,3}).

2. Описать граф матрицей смежности и матрицей инцидентности.

3. Изобразить графически граф G и его дополнение G.

4. Построить произвольный остовный подграф и подграф, порожденный вершинами {1,2,5,6,7};

5. Построить все помеченные 5-графы, изоморфно вложимые в граф G.

5.1. Определить классы изоморфных графов.

5.2. Построив биекцию их вершин.

5.3 Для каждого класса изоморфных графов привести рисунок абстрактного графа.

6. Построить все помеченные (5-7)-графы (до 20 штук), изоморфные некоторому подграфу G.

6.1. Определить классы изоморфных графов.

6.2. Построив биекцию их вершин.

6.3. Для каждого класса таких графов привести рисунок абстрактного графа.

7. Найти все максимальные и наибольшие независимые множества исходного графа, определить число независимости.

8. Найти все максимальные и наибольшие клики данного графа. Определить плотность графа G.

9. Найти все минимальные и наименьшие доминирующие множества, определить число доминирования.

10. Найти полный двудольный подграф K_p,q, изоморфно вложимый в G с максимальным количеством вершин p+q (p≠1).

11. Найти звезду K_1,n, изоморфно вложимую в G с максимальным n.

Контрольные вопросы

1. Что такое неорграф?

2. Определение подграфа, остовного и порожденного подграфа. Дополнение графа.

3. Изоморфизм графов.

4. Помеченные и абстрактные графы.

5. Клика. Максимальная и наибольшая клика. Кликовое число или плотность графа.

6. Независимое множество. Максимальное и наибольшее независимое множество. Число независимости.

7. Полный, пустой, двудольный графы.

8. Число ребер в полном графе.

9. Число различных помеченных р -графов.

10. Число различных помеченных (р,q) -графов.

 

ПРИЛОЖЕНИЕ №1

Алгоритм генерации варианта

 

GV (p,X): A[1:p,1:p], где

p - количество вершин в графе;

X - параметр генерации (множество целых);

А - матрица смежности неориентированного графа.

 

S = <фамилия>< имя>< отчество>

n (c) - функция - номер буквы в алфавите (1..32)

 

1. Вычеркнуть из S все повторные вхождения букв.

 

2. Построить Y = || y_ij ||, i,j =1..p, y_ij = | n (S_i) - n (S_j) |.

3. Построить А = || а_ij ||, i,j =1..p,

а_ij=

4. Для каждой изолированной (доминирующей) вершины добавить (удалить) одно ребро. Добавляемое (удаляемое) ребро связывает текущую вершину со следующей (по номеру). Для последней вершины следующая - первая.

 

Пример реализации GV (7, (2,3)).

1.Строка S = С И Д О Р О В И В А Н П Е Т Р О В И Ч.

После вычеркивания повторных вхождений букв

S = С И Д О Р В А Н П Е Т Ч.

 

Таблица для функции n (S)

 

A - 1	Д - 5	З- 9	Л -13	П -17	У -	Ч -25	Ь -29
Б - 2	Е - 6	И -10	М -14	Р -18	Ф -22	Ш -26	Э -30
В - 3	Ё - 7	Й -11	Н -15	С -19	Х -	Щ -27	Ю -31
Г - 4	Ж- 8	К -12	О -16	Т -20	Ц-	Ы-28	Я -32

 

S

С

И

Д

О

Р

В

А

Н

П

Е

Т

Ч Ч

N(si)

1 9

 

Y =

 

 

A =

 

G: