Учебная работа № 3958. «Контрольная Вариант 9 графы
Учебная работа № 3958. «Контрольная Вариант 9 графы
Содержание:
«Вариант 9
Сделайте разметку вершин и ребер графа в произвольном порядке
Задание 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) найти все максимальные полные и максимальные пустые подграфы с помощью алгоритма Магу-Уэйсмана.
КОНТРОЛЬНАЯ РАБОТА №2
Контрольная работа №2 содержит 3 задания.
ЗАДАНИЕ 1. Решить задачу коммивояжёра.
Исходные данные:
Значения элементов матрицы расстояний:
ВАРИАНТ 9
a(1,1)= ; a(2.1)=53 ; a(3.1)=32; a(4.1)=11; a(1.2)=25; a(2.2)= ; a(3.2)=72; a(4.2)=35; a(1.3)=115; a(2.3)=24; a(3.3)= ; a(4.3)=129; a(1.4)=13; a(2.4)=36; a(3.4)=18; a(4.4)= ; a(1.5)=46; a(2.5)=75; a(3.5)=24; a(4.5)=38; a(5.1)=22; a(5.4)=16; a(5.2)=63; a(5.5)= ; a(5.3)=34
ЗАДАНИЕ 2. Найти минимальную раскраску графа своего варианта с помощью алгоритма Магу. Определить хроматическое число.
Вариант 9
ЗАДАНИЕ 3.
ЗАДАЧА о максимальном потоке на сети.
Исходные данные:
Дана сеть S(X,U)
x0 ? исток сети; x7 – сток сети, где x0 ?X; x7?X.
1. Вычислить значение максимального потока на сети S, с помощью алгоритма
Форда?Фалкерсона.
2. Построить минимальный разрез сети S.
Варианты значений пропускных ri,j способностей дуг сети (значения пропускных способностей дуг ri,j заданы по направлению ориентации дуг: от индекса i к индексу j):
ВАРИАНТ 9
»
Выдержка из похожей работы
и l
формируют значения индексов ,
, …
переменной x
в отображении Гxi
= {x
,
x
,
x,…},
Если значения индексов ,
,
…
переменной x
не соответствуют ни одному из номеров
вершин графа, то эта переменная не
учитывается во множестве Гxi,
Выполнить
следующие действия:
а)
определить исходный граф и ассоциированный
с ним неориентированный граф графическим,
матричным и аналитическим способами;
б)
установить центры и периферийные вершины
графов, найти радиусы и диаметры графов;
в)
выделить в ориентированном графе два
подграфа, Найти объединение, пересечение
и разность подграфов;
г)
описать систему уравнений, соответствующую
сигнальному графу, считая, что передача
между вершинами xi
и xj
i*j
при
i
j;
Kij
=
1/(p+1)
при i
Центры
графа – это вершины с наименьшей
удаленностью, Периферийные вершины —
вершины с
наибольшей удаленностью, В данном случае
периферийными вершинами являются две
вершины x2,
x4,
а центрами
графа являются три вершины x1,
x3,
x5,
Тогда радиус ρ(G)
=2, а диаметр графа D(G)
= 3,
в)
выделим в ориентированном графе два
подграфа и найдем объединение, пересечение
и разность подграфов:
Выделяем
два подграфа: G1
и G2
X1
– {x1,
x2},
Г1х1
= { x2
}, Г1х2
= {x1},
X2
– {x1,
x2,
x3},
Г2х1
= {x2},
Г2х2
= {x3},
Г2х3
= {x2},
Объединение
графов:
,,
,
,
,
G
Пересечение
,
,
,
,
G
Разностью
графов G1(X1, Г1)
и G2(X2, Г2)
называется граф
,
где
– дополнение по отображению графа G2
до насыщенного,
,
где
,
Он
имеет вид
;,
