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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая
ABCDEF

Найдите сумму степеней всех вершин показанного графа, Σ deg.

|V| = 6
Σ deg =
2.Лёгкая

Сколько рёбер, |E|, у полного графа K5?

K5
|E| =
3.Средняя

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

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

У дерева 2 вершин степени 4, 4 вершин степени 5, 2 вершин степени 2, а все остальные его вершины — листья (степень 1). Сколько у него листьев, L?

2 × deg 44 × deg 52 × deg 2
L =
5.Сложная
209410181211975ABCDEFG

Алгоритм Краскала строит минимальное остовное дерево. Нажмите на ребро, которое он добавляет под номером 2; пропущенные рёбра не считаются.

k = 2
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро CE
  5. 5ребро DE
  6. 6ребро EF
  7. 7ребро GB
  8. 8ребро GC
  9. 9ребро GD
  10. 10ребро GE
6.Сложная
8493612ABCDE

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

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

Ответы

  1. 1. Σ deg = 16
  2. 2. |E| = 10
  3. 3. H = 3
  4. 4. L = 18
  5. 5. ребро BC
  6. 6. W = 13

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