Билет по графам. Воронежский государственный технический университет

• Название: Воронежский государственный технический университет
• Анкор: Билет по графам
• Дата: 06.04.2021
• Размер: 108 Kb.
• Имя файла: 3.doc
• Тип: Документы; #191821

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра высшей математики и физико-математического моделирования

Дисциплина: «Теория графов и её приложения»
БИЛЕТ № 3

1. 
   Матрица смежности вершин. Необходимое и достаточное условие изоморфности графов и следствие из неё. Ранг графа. Дерево. Лес. Теорема о дереве. Остовный подграф. Остовное поддерево (остовный каркас). Алгоритм Прима (алгоритм ближайшего соседа) построения экстремального остовного дерева.
   
2. 
   Используя алгоритм Прима, найти остовное дерево наименьшего веса для неориентированного графа с десятью вершинами, заданного следующим списком рёбер с метками (вершина, вершина, метка):
   

3. 
   С помощью алгоритма Дейкстры найдите два кратчайших пути от вершины до вершины в нагруженном графе:
   

10




5 13 10 12

4 6

10

18 5

4 6 3

8 9




14

Билет рассмотрен и утверждён на заседании кафедры ВМФММ

Протокол № __9_ от «__07_»_____05______ 2019
Зав. кафедрой ВМФММ И.Л. Батаронов