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

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

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

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

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

1.Легка
AABBCCDD0110101011010010

Показано матрицю суміжності простого неорієнтованого графа. Знайдіть степінь deg(C) вершини C.

deg(C) =
2.Легка

Простий граф має 6 вершин зі степенями 3, 3, 2, 2, 1, 1. Скільки ребер |E| він має?

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

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

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

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

2 × deg 32 × deg 4
L =
5.Складна
9171575810ABCDE

Алгоритм Крускала будує мінімальне остовне дерево. Клікніть ребро, яке він додає як ребро номер 3; пропущені ребра не враховуються.

k = 3
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро BD
  5. 5ребро CE
  6. 6ребро DE
  7. 7ребро BE
6.Складна
110105921510ABCDEF

Алгоритм Дейкстри працює від A. Клікніть вершину, яку фіксують (роблять остаточною) у раунді 5; сама A — це раунд 1.

початок: Aраунд 5
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

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

  1. 1. deg(C) = 3
  2. 2. |E| = 6
  3. 3. Ейлерів шлях, не цикл
  4. 4. L = 8
  5. 5. ребро DE
  6. 6. C

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