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

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

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

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

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

1.Легка

Скільки ребер |E| має повний дводольний граф K6,4?

K6,4
|E| =
2.Легка
ABCDE

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

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
3.Середня

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

K4
H =
4.Середня

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

|V| = 11|E| = 18
k =
5.Складна
41556973ABCDE

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

початок: Bk = 2
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро BD
  5. 5ребро CE
  6. 6ребро DE
  7. 7ребро BE
6.Складна
126483111418ABCDEF

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

|V| = 6|E| = 8
W =

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

  1. 1. |E| = 24
  2. 2. B
  3. 3. H = 3
  4. 4. k = 8
  5. 5. ребро AB
  6. 6. W = 36

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