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

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

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

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

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

1.Легка
AABBCCDDEEFF011000100110100000010011010101000110

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

|E| =
2.Легка
AABBCCDDEEFF011000101110110000010010010101000010

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

deg(B) =
3.Середня
ABCDEЕйлерів циклЕйлерів шлях, не циклжодна з цих

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

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

Зв’язний граф має 20 вершин і 29 ребер. Скільки ребер k треба вилучити, щоб залишилося остовне дерево?

|V| = 20|E| = 29
k =
5.Складна
19614513142016ABCDEF

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

початок: Fk = 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ребро BE
6.Складна
14135151918122111ABCDEFG

Знайдіть загальну вагу W мінімального остовного дерева зваженого графа.

|V| = 7|E| = 10
W =

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

  1. 1. |E| = 7
  2. 2. deg(B) = 4
  3. 3. жодна з цих
  4. 4. k = 10
  5. 5. ребро BC
  6. 6. W = 50

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