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

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

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

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

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

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

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

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

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

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

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

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

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

1. Что такое неориентированный граф?

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

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

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

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

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

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

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

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

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

Лабораторная работа №2