[ДВГУПС] Дискретная математика (контрольная №2, вариант 7)

Дальневосточный государственный университет путей сообщения. Дискретная математика. Контрольная №2. Вариант 7.

Задание 1

Дана матрица смежности. Изобразить соответствующий размеченный граф.

Задание 2

Даны графы G1 и G2. Выпишите для каждого графа множества вершин и ребер. Определите степень каждой вершины. Найдите матрицы смежности и инцидентности. Укажите для графа G1 какой-либо маршрут из вершины 1. Укажите для графа G2 подграфы.

Задание 3

Постройте односторонне связный ориентированный граф на пяти вершинах. Найдите диаметр этого графа.

Задание 4

Найдите остовные деревья графа, представленного на рисунке 23, без учета веса ребер:

а) методом поиска в ширину;

б) методом поиска в глубину.

В качестве начальной вершины выберите вершину V6.

Задание 5

Для графа, представленного на рисунке 20, задайте весовую функцию ребер и постройте остовное дерево минимального веса, полагая, что ребра имеют различные положительные целые веса. Минимальный вес ребра равен 7.