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

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

Маршруты и связность в неориентированных графах

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