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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая
ABCDE

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

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
2.Лёгкая
ABCDE

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

|V| = 5
Σ deg =
3.Средняя

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

|V| = 14|E| = 16
k =
4.Средняя

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

K4
H =
5.Сложная
111965143188712ABCDEFG

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

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

С помощью алгоритма Дейкстры найдите длину d(E) кратчайшего пути от A до E во взвешенном графе.

начало: Aконец: E
d(E) =

Ответы

  1. 1. C
  2. 2. Σ deg = 12
  3. 3. k = 3
  4. 4. H = 3
  5. 5. ребро GC
  6. 6. d(E) = 5

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