Домашнее задание по теме «ГРАФЫ»
Постановка задачи:
-
Упорядочить элементы орграфа (привести к ярусно параллельной форме) (1 балл). В отчете привести исходный граф, матрицу смежности вершин, упорядоченный граф.
-
Определить ядро для орграфа (2 балла). В отчете привести исходный граф, матрицу смежности вершин, решение с указанием множеств вершин внутренней и внешней устойчивости, ядра графа. Объяснить полученные результаты.
-
Определить клику для неориентированного графа (1 балл). Для определения клики взять граф из задания 2 , не учитывая направления дуг. В отчете привести исходный граф, матрицу смежности вершин, решение c указанием множеств вершин, образующих клику графа. Объяснить полученные результаты.
-
Найти минимальный путь в графе от а до f или g (в зависимости от числа вершин), используя метод Дейкстры (2 балла). В отчете привести исходный граф, матрицу смежности вершин с метками, решение с указание длины пути.
-
Найти минимальный по весу остов (2 балла). В отчете привести исходный граф, матрицу смежности вершин, решение, остов графа.
-
Найти в графе кратчайший путь из k ребер, используя алгоритм Шимбелла (2 балла). В отчете привести исходный граф, матрицу смежности вершин, решение, объяснить полученные результаты.
База заданий
Задание 1.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
|
|
|
|
|
|
|
|
g
|
|
|
a b
c
f i
d
e
h
g
|
|
|
|
|
|
a b
c
d
f g
d e
|
|
|
b
a c
d
h f g
e
|
|
|
a b
c
d
f g
h e
|
|
|
b
a
c
d
h f g
e
|
Задание 2.
|
|
a b
c
f
d
e
|
|
|
a b c d e f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b
a
d
g
f
|
|
|
b
c
d
f
a e
|
|
|
a b
c
d
d
e
|
|
|
a b
c
f
d e
|
|
|
b
a
d
f g
e
|
Задание 4.
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|