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

ID: 67956
Дата закачки: 04 Мая 2012
Продавец: a-cool-a (Напишите, если есть вопросы)
Посмотреть другие работы этого продавца

Тип работы: Работа Контрольная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: ТУСУР

Описание:
Задание 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) найти все максимальные пол-ные и максимальные пустые подграфы с помощью алгоритма Магу-Уэйсмана.

Размер файла: 998,5 Кбайт
Фаил: