Билет по графам. Воронежский государственный технический университет
![]()
|
ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра высшей математики и физико-математического моделирования Дисциплина: «Теория графов и её приложения» БИЛЕТ № 3 Матрица смежности вершин. Необходимое и достаточное условие изоморфности графов и следствие из неё. Ранг графа. Дерево. Лес. Теорема о дереве. Остовный подграф. Остовное поддерево (остовный каркас). Алгоритм Прима (алгоритм ближайшего соседа) построения экстремального остовного дерева. Используя алгоритм Прима, найти остовное дерево наименьшего веса для неориентированного графа с десятью вершинами, заданного следующим списком рёбер с метками (вершина, вершина, метка): ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() С помощью алгоритма Дейкстры найдите два кратчайших пути от вершины ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 5 13 10 12 4 6 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 18 5 4 6 3 8 9 ![]() ![]() ![]() Билет рассмотрен и утверждён на заседании кафедры ВМФММ Протокол № __9_ от «__07_»_____05______ 2019 Зав. кафедрой ВМФММ И.Л. Батаронов |