ЛАБОРАТОРНАЯ РАБОТА №1
Тема: « Подграфы. Изоморфизм».
Цель работы: изучение основных понятий теории графов и приобретение практических навыков определения изоморфизмов графа; построение подграфов, независимых множеств и клик.
1. Используя алгоритм генерации варианта GV, построить неориентированный граф G: GV(7,{2,3}).
S=<юфаеленаяковлевна>;
S=< ю,ф,а,е,л,н,я,к,о,в>;
n(Si)={32,22,1,6,13,15,33}.
| Y | |||||||
| A | |||||||
Построим неориентированный граф 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}.
Матрица смежности
| A | |||||||
Матрица инцидентности
| B | (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=(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) Графы с пятью ребрами: G5, G10, G12, G16.
2) Графы с шестью ребрами: G1, G2,G3, G4, G7, G8, G9, G13, G14, G17, G19.
 |
 |
3) Графы с семью ребрами: G6, G11, G15, G20.
 |
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. Найти полный двудольный подграф Kp,q, изоморфно вложимый в граф G, с максимальным количеством вершин p+q ( p¹1).
Полные двудольные подграфы, изоморфно вложимые в G:
Kp,q=K2,2; p+q=2+2=4.
7. Найти звезду K1,n, изоморфно вложимую в граф G с максимальным значением n.
Звезды K1,n, изоморфно вложимые в G с максимальными n:
K1,n=K1,2; n=2.
 |
Вывод: в данной лабораторной работе изучены основные понятия теории графов, приобретены практические навыки определения изоморфизмов графа, построения подграфов, независимых множеств и клик.
ЛАБОРАТОРНАЯ РАБОТА №2
Тема: «Маршруты и связность».
Цель работы: изучение понятий связных графов и маршрутов, приобретение практических навыков построения матрицы расстояний и нахождения матрицы кратчайших маршрутов.
1. Используя алгоритм генерации варианта GV, построить неориентированный граф G1:GV(13,{6,7}) и граф G2:GV(7,{2,3}). Ребра графа G2 взвешены соответствующими элементами матрицы Y.
Построим граф G1, используя алгоритм генерации варианта GV(13,{6,7}).
S=<юфаеленаяковлевна>;
S=< ю,ф,а,е,л,н,я,к,о,в >;
n(Si)={32,22,1,6,13,15,33,12,16,3,29,18,14}.
| Y1 | |||||||||||||
Матрица смежности
| A1 | |||||||||||||
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(Si)={32,22,1,6,13,15,33}.
| Y2 | |||||||
Матрица смежности
| A2 | |||||||
Построим неориентированный граф 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.
 |
 |
2. Определить, является ли граф G1 связным.
Две вершины называются связными, если между ними существует маршрут.
Граф называется связным, если любая пара его вершин связна. Каждая вершина считается связной сама с собой.
Чтобы определить, является ли граф G1 связным, определим, существуют ли маршруты между любыми двумя его вершинами:
| M1,2={1,12,4,5,3,2}; M1,5={1,12,4,5}; M1,8={1,12,8}; M1,10={1,12,8,7,10}; M2,3={2,3}; M2,6={2,6}; M2,9={2,9}; M2,12={2,3,5,4,12}; M3,5={3,5}; M3,8={3,5,4,8}; M3,11={3,11}; M4,5={4,5}; M4,8={4,8}; M4,11={4,5,3,11}; M5,6={5,3,6}; M5,9={5,3,2,9}; M5,12={5,4,12}; M6,8={6,7,8}; M6,11={6,11}; M7,8={7,8}; M7,11={7,6,11}; M8,9={8,7,6,2,9}; M8,12={8,12}; M9,11={9,2,11}; M10,11={10,6,11}; M10,12={10,7,8,12}; | M1,3={1,12,4,5,3}; M1,6={1,12,8,7,6}; M1,9={1,12,4,5,3,2,9}; M1,11={1,12,4,5,3,11}; M2,4={2,3,5,4}; M2,7={2,6,7}; M2,10={2,6,10}; M2,13={2,3,5,4,12,1,13} M3,6={3,6}; M3,9={3,2,9}; M3,12={3,5,4,12}; M4,6={4,8,7,6}; M4,9={4,5,3,2,9}; M4,12={4,12}; M5,7={5,3,6,7}; M5,10={5,3,6,10}; M5,13={5,4,12,1,13}; M6,9={6,2,9}; M6,12={6,7,8,12}; M7,9={7,6,2,9}; M7,12={7,8,12}; M8,10={8,7,10}; M8,13={8,12,1,13}; M9,12={9,2,3,5,4,12}; M10,13={10,7,8,12,1,13}; M12,13={12,1,13}; | M1,4={1,12,4}; M1,7={1,12,8,7}; M1,13={1,13}; M1,12={1,12}; M2,5={2,3,5}; M2,8={2,6,7,8}; M2,11={2,11}; M3,4={3,5,4}; M3,7={3,6,7}; M3,10={3,6,10}; M3,13={3,5,4,12,1,13}; M4,7={4,8,7}; M4,10={4,8,7,10}; M4,13={4,12,1,13}; M5,8={5,4,8}; M5,11={5,3,11}; M6,7={6,7}; M6,10={6,10}; M6,13={6,7,8,12,1,13}; M7,10={7,10}; M7,13={7,8,12,1,13}; M8,11={8,7,6,11}; M9,10={9,2,6,10}; M9,13={9,2,3,5,4,12,1,13}; M11,12={11,3,5,4,12}; M11,13={11,3,5,4,12,1,13}; |
Итак, между любыми двумя вершинами графа существует маршрут, следовательно, граф является связным. Он содержит только одну компоненту связности, которая совпадает с исходным графом.
3. Для максимальной компоненты графа G1 выделить:
