Примеры решения задач
Упражнение 1
Тема: «Графы. Основные понятия. Графы и отношения. Маршруты, пути, цепи, циклы»
Задачи для решения в аудитории
Задать матрицами инцидентности и смежности граф, изображенный на рис.
Пусть ориентированный граф G на рисунке ниже задает отношение R. Каковы свойства отношения?
Изобразить графы, соответствующие отношениям, представленным следующими матрицами:
|
a |
b |
c |
d |
a |
1 |
1 |
0 |
0 |
b |
0 |
1 |
0 |
1 |
c |
1 |
1 |
1 |
0 |
d |
0 |
1 |
0 |
1 |
|
a |
b |
c |
d |
a |
0 |
1 |
0 |
0 |
b |
1 |
0 |
0 |
1 |
c |
1 |
1 |
0 |
1 |
d |
1 |
1 |
1 |
0 |
Для вершин
и
графа
на рисунке ниже привести примеры
маршрута, простого маршрута. Определить
цикл, приняв вершину
на начало и конец цикла. Есть ли на этом
графе эйлеров маршрут и (или) гамильтонов
маршрут?
Для четырех графов на рисунке ниже определить расстояния между вершинами.
Какими свойствами обладает отношение связанности вершин графа, изображенного на рисунке ниже.
Домашнее задание
Построить матрицы смежности и инцидентности графов, изображенных на рисунках ниже. Нумерацию вершин и ребер (дуг) задайте самостоятельно.
Имеют ли графы эйлеров цикл (цепь)? Запишите цикл.
Имеют ли пятигранник-призма и пятиугольник с петлями в некоторых вершинах гамильтонов цикл (цепь)?
Каковы расстояния между вершинами в графе на рисунке ниже.
На рисунке ниже. Показан граф-дерево. Сколько листьев на графе? Определите множество листьев. Сколько ветвей для вершины d на графе. Какая вершина является корнем? Можно ли принять любую вершину графа-дерева за корень? Перерисуйте граф-дерево с другим корнем.
Изобразите граф-лес.
Достижима ли:
вершина h из вершины a;
вершина a из вершины m
для графа, изображенного на рисунке ниже. Если – да, то задайте множество путей.
Какие вершины являются центрами четырех графов на рисунке? Чему равны радиусы графов?
Задайте множество маршрутов графа-дерева в задаче 5.
Постройте граф с гамильтоновым циклом.
Упражнение 2
Тема: «Бинарные операции над графами. Изоморфизм графов»
Задачи для решения в аудитории
Н
айти
объединение графов
и
,
представленных на рис.
1)
2)
3)
4)
5)
Найти пересечение графов, представленных на рисунке в задаче 1.
Найти объединение и пересечение графов
и
,
и
изображенных
на рисунках ниже.
Найти разность графов, изображенных на рисунке ниже.
Найти композицию графов, изображенных на рисунке ниже.
Изоморфны ли графы, изображенные на рисунке ниже.
Изоморфны ли графы, изображенные на рис.
Домашнее задание
Найти объединение графов:
1)
2)
Найти попарно пересечение графов для варианта 1 и 2:
1)
2)
Найти разность двух подграфов полного графа:
Найти модульное произведение двух графов:
Найти декартову сумму графов и
Удалите вершины 1,2, 8, 9 графа на рисунке ниже. Удаление выполнить с помощью матрицы инциденций и графически.
Постройте композицию двух графов:
Постройте композицию двух графов:
Постройте два изоморфных подграфа полного графа с четырьмя вершинами. Покажите их изоморфность алгоритмическим путем.
Определить, изоморфны ли графы.
