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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая
AABBCCDD0101101001001000

Показана матрица смежности простого неориентированного графа. Сколько рёбер, |E|, в графе?

|E| =
2.Лёгкая
ABCDEFG

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

deg = 2
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
3.Средняя
ABCDEЭйлеров циклЭйлеров путь, не циклни то, ни другое

Есть ли в связном графе эйлеров цикл, эйлеров путь, не являющийся циклом, или ни то ни другое? Нажмите на ваш ответ.

|V| = 5|E| = 6
  1. 1Эйлеров цикл
  2. 2Эйлеров путь, не цикл
  3. 3ни то, ни другое
4.Средняя

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

|V| = 18|E| = 23
k =
5.Сложная
15113218126ABCDE

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

начало: Ak = 4
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро BD
  5. 5ребро CE
  6. 6ребро DE
  7. 7ребро BE
6.Сложная
28396181416ABCDEF

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

k = 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

Ответы

  1. 1. |E| = 3
  2. 2. D
  3. 3. Эйлеров путь, не цикл
  4. 4. k = 6
  5. 5. ребро BE
  6. 6. ребро BD

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