Контрольная работа №1 по дискретной математике

Задание 1.
Для графа G=(X,U) ( рисунок 1) выполнить следующее:
1.1. Построить:
- матрицу смежности;
- матрицу инциденций.
1.2. Определить степени для всех вершин {xi} данного графа.
(Указать каким способом вычисляли S(xi)).
1.3. а). Подсчитать количество маршрутов длиной в графе G=(X,U).
б). Построить все длиной , связывающие вершины хi и хk ( помечены * ).'
Маршруты записать в форме: =( хi ,... хt ,..., хk), где p номер маршрута.
Примечание. Для выполнения п.1.3а) составить программу на алгоритмическом языке Паскаль (к отчёту приложить исход-ный код программы и exe-file).
Задание 2.
По матрицам А (рисунок 2) и С (рисунок 3) построить гра-фы G1 и G2.
Задание 3.
Для графа G=(X,U) ( рисунок 1) построить кратчайшие мар-шруты, связывающие вершину, помеченную * (любую из двух), с остальными вершинами, указать их длину. Описать способ решения данной задачи.
Задание 4.
Для графа, представленного на рисунке 1 выполнить сле-дующее:
4.1. Привести примеры подграфов 3-х вершинных, 4-х вершин-ных, 1-вершинных.
4.2. Привести пример суграфа данного графа.
4.3. Выполнить унарные операции для вершин, помеченных *.
Задание 5.
Для графа G=(X,U) ( рисунок 1) выполнить следующее:
5.1. Построить матрицу метрики (отклонений).
5.2. Вычислить радиус и диаметр.
5.3. Определить периферийные точки.
Задание 6.
Произвести произвольно ориентацию рёбер графа G=(X,U) (рисунок 1) и для нового графа выполнить задания 1.1, 1.3, 5.
Задание 7.
Построить скелет графа .
Задание 8.
В графе G=(X,U) ( рисунок 1) найти все максимальные пол-ные и максимальные пустые подграфы с помощью алгоритма Магу-Уэйсмана.