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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

У дерева 36 рёбер. Сколько у него вершин, |V|?

|E| = 36
|V| =
2.Лёгкая
ABCDE

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

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

Связный граф имеет 13 вершин и 20 рёбер. Сколько рёбер, k, нужно удалить, чтобы осталось остовное дерево?

|V| = 13|E| = 20
k =
4.Средняя

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

K8
H =
5.Сложная
71617183195106ABCDEFG

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

начало: Ek = 3
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро BD
  5. 5ребро CE
  6. 6ребро DF
  7. 7ребро EF
  8. 8ребро GD
  9. 9ребро GE
6.Сложная
452914117ABCDE

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

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

Ответы

  1. 1. |V| = 37
  2. 2. B
  3. 3. k = 8
  4. 4. H = 2520
  5. 5. ребро GE
  6. 6. W = 16

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