Теория графов: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Теория графов»: 6 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

Для преподавателей: можно бесплатно печатать, копировать и использовать на занятиях. Каждый новый лист содержит новые значения и собственные ответы. Будем благодарны за ссылку на ExamProblems на странице вашего курса.

Имя: ____________________   Дата: ____________

1.Лёгкая

4-регулярный граф имеет 7 вершин (степень каждой вершины равна 4). Сколько у него рёбер, |E|?

n = 7k = 4
|E| =
2.Лёгкая
ABCDEFG

Ровно одна вершина графа имеет степень 4. Нажмите на неё.

deg = 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
3.Средняя

Сколько различных гамильтоновых циклов, H, в полном графе K8? Циклы, отличающиеся только начальной вершиной или направлением, считаются одним и тем же.

K8
H =
4.Средняя

Сколько различных гамильтоновых циклов, H, в полном графе K4? Циклы, отличающиеся только начальной вершиной или направлением, считаются одним и тем же.

K4
H =
5.Сложная
20751581221716ABCDEF

Алгоритм Прима строит минимальное остовное дерево, начиная с вершины A. Нажмите на ребро, которое он добавляет под номером 4.

начало: Ak = 4
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро BD
  5. 5ребро CE
  6. 6ребро DE
  7. 7ребро DF
  8. 8ребро EF
  9. 9ребро BE
6.Сложная
1935208112ABCDE

Найдите суммарный вес W минимального остовного дерева взвешенного графа.

|V| = 5|E| = 7
W =

Ответы

  1. 1. |E| = 14
  2. 2. E
  3. 3. H = 2520
  4. 4. H = 3
  5. 5. ребро DE
  6. 6. W = 21

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.