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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

5-регулярный граф имеет 10 вершин (степень каждой вершины равна 5). Сколько у него рёбер, |E|?

n = 10k = 5
|E| =
2.Лёгкая
AABBCCDD0011001011011010

Показана матрица смежности простого неориентированного графа. Найдите степень deg(A) вершины A.

deg(A) =
3.Средняя

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

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

У дерева 4 вершин степени 3, 3 вершин степени 4, 3 вершин степени 5, 4 вершин степени 2, а все остальные его вершины — листья (степень 1). Сколько у него листьев, L?

4 × deg 33 × deg 43 × deg 54 × deg 2
L =
5.Сложная
7284183131551ABCDEFG

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

k = 4
  1. 1ребро AB
  2. 2ребро AC
  3. 3ребро BC
  4. 4ребро CE
  5. 5ребро DE
  6. 6ребро EF
  7. 7ребро GB
  8. 8ребро GC
  9. 9ребро GD
  10. 10ребро GE
6.Сложная
ABCDE

Сколько существует замкнутых маршрутов длины 2, начинающихся и заканчивающихся в D? Маршрут может повторять вершины и рёбра. Обозначим это число N.

M = матрица смежностиL = 2
N =

Ответы

  1. 1. |E| = 25
  2. 2. deg(A) = 2
  3. 3. H = 3
  4. 4. L = 21
  5. 5. ребро CE
  6. 6. N = 2

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