Примеры выполнения лабораторных работ

S=<юфаеленаяковлевна>;

S=< ю,ф,а,е,л,н,я,к,о,в>;

n(S_i)={32,22,1,6,13,15,33}.

Построим неориентированный граф G1, используя способ перечисления. G=(V,E):

V={1,2,3,4,5,6,7} – множество вершин графа;

E={(1,2),(1,4),(2,3),(2,4),(2,5),(3,5),(3,6),(3,7),(4,6),(4,7),(5,6), (5,7),(6,7)} -

множество ребер графа.

2. Описать граф матрицей смежности, матрицей инцидентности. Изобразить графически граф G и его дополнение G̅. Построить произвольный остовный подграф и подграф, порожденный вершинами {1,2,5,6,7}.

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

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

Остовный подграф G1=(V,E1), где Подграф G2, порожденный вершинами

E1={(1,2),(1,4),(2,5),(3,5),(5,6),(5,7),(6,7)}: {1,2,5,6,7}:

3. Построить все помеченные 5-графы, изоморфно вложимые в граф G. Среди них определить классы изоморфных графов, построив биекцию их вершин. Для каждого класса изоморфных графов привести рисунок абстрактного графа.

5-графы, изоморфно вложимые в граф G:

 

 

 

 

 

Классы изоморфных графов:

1) Графы с пятью ребрами: G₅, G₁₀, G₁₂, G₁₆.

 

2) Графы с шестью ребрами: G₁, G₂,G₃, G4, G7, G8, G9, G13, G14, G17, G19.

 

3) Графы с семью ребрами: G₆, G₁₁, G₁₅, G₂₀.

4) Графы с восемью ребрами:

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

Выпишем все независимые множества данного графа G:

S1={1,3}; S2={1,5}; S3={1,6}; S4={1,7};

S5={2,6}; S6={2,7}; S7={3,4}; S8={4,5}.

Для данного графа максимальными независимыми множествами являются S1, S2, S3, S4, S5, S6,S7, S8.

Для данного графа наибольшими независимыми являются множества S1, S2, S3, S4, S5, S6,S7, S8.

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

 

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

Выпишем все клики данного графа:

K1={1,2};	K8={3,7};	K15={2,3,5};
K2={1,4};	K9={4,6};	K16={3,5,6};
K3={2,3};	K10={4,7};	K17={3,6,7};
K4={2,4};	K11={5,6};	K18={4,6,7};
K5={2,5};	K12 ={5,7};	K19={5,6,7};
K6={3,5};	K13={6,7};	K20={3,5,7};
K7={3,6};	K14={1,2,4};	K21={3,5,6,7}.

 

Для данного графа максимальными кликами являются K14, K15, K18, K21;

наибольшей кликой является K21.

Плотность графа b(G)=ïK21ï=4.

 

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

Полные двудольные подграфы, изоморфно вложимые в G:

K_p,q=K_2,2; p+q=2+2=4.

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

 

Звезды K_1,n, изоморфно вложимые в G с максимальными n:

K_1,n=K_1,2; n=2.

 

 

 

 

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

 

 

 

Построим граф G1, используя алгоритм генерации варианта GV(13,{6,7}).

S=<юфаеленаяковлевна>;

S=< ю,ф,а,е,л,н,я,к,о,в >;

n(S_i)={32,22,1,6,13,15,33,12,16,3,29,18,14}.

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

G1=(V1,E1): V1={1,2,3,4,5,6,7,8,9,10,11,12,13} – множество вершин графа;

E1={(1,12),(1,13),(2,3),(2,6),(2,9),(2,11),(3,5),(3,6),(3,11),(4,5),

(4,8),(4,12),(6,7),(6,10),(6,11),(7,8),(7,10),(8,12)} – множество ребер графа.

Построим граф G2, используя алгоритм генерации варианта GV(7,{2,3}).

S=<юфаеленаяковлевна>;

S=< ю,ф,а,е,л,н,я,к,о,в>;

n(S_i)={32,22,1,6,13,15,33}.

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

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

G2=(V2,E2):

V2={1,2,3,4,5,6,7} – множество вершин графа;

E2={(1,2),(1,4),(2,3),(2,4),(2,5),(3,5),(3,6),(3,7),(4,6),(4,7),(5,6), (5,7),(6,7)} – множество ребер графа.

Построим графическое изображение графов G1 и G2.