Робочий аркуш «Теорія графів» з відповідями

Безкоштовний робочий аркуш для друку «Теорія графів»: 6 задач від легких до рівня іспиту, з ключем відповідей. Роздрукуйте його або збережіть як PDF.

Новий робочий аркушТренуватися онлайн з підказками

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

Ім’я: ____________________   Дата: ____________

1.Легка

Дерево має 38 ребер. Скільки вершин |V| воно має?

|E| = 38
|V| =
2.Легка
ABCDEFG

Рівно одна вершина графа має степінь 1. Клікніть її.

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
3.Середня
ABCDEFGЕйлерів циклЕйлерів шлях, не циклжодна з цих

Чи має зв’язний граф ейлерів цикл, ейлерів шлях, що не є циклом, чи нічого з цього? Клікніть свою відповідь.

|V| = 7|E| = 10
  1. 1Ейлерів цикл
  2. 2Ейлерів шлях, не цикл
  3. 3жодна з цих
4.Середня

Дерево має 4 вершин степеня 3, 4 вершин степеня 5, 2 вершин степеня 2, а всі його інші вершини — листки (степінь 1). Скільки листків L воно має?

4 × deg 34 × deg 52 × deg 2
L =
5.Складна
152016143549131ABCDEFG

Алгоритм Пріма будує мінімальне остовне дерево, починаючи з вершини A. Клікніть ребро, яке він додає як ребро номер 3.

початок: Ak = 3
  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ребро GC
  10. 10ребро GE
6.Складна
ABCDE

Скільки маршрутів довжиною 3 ведуть від D до C? Маршрут може повторювати вершини й ребра. Позначте число N.

M = матриця суміжностіL = 3
N =

Ключ відповідей

  1. 1. |V| = 39
  2. 2. A
  3. 3. жодна з цих
  4. 4. L = 18
  5. 5. ребро DF
  6. 6. N = 1

Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.