Главная / Алгоритмы и дискретные структуры / Графы и алгоритмы / Тест 3

Графы и алгоритмы - тест 3

Упражнение 1:

Номер 1

Сколько имеется абстрактных деревьев с 6 вершинами?

Ответ:

(1) 4

(2) 5

(3) 6

(4) 7

Номер 2

Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?

Ответ:

(1) 10

(2) 11

(3) 12

(4) 13

Номер 3

В дереве имеется ровно три листа , причем , , . Сколько всего вершин в этом дереве?

Ответ:

(1) 10

(2) 11

(3) 12

(4) такого дерева не существует

Упражнение 2:

Номер 1

Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?

Ответ:

(1) 8

(2) 15

(3) 16

(4) 31

Номер 2

Сколько различных каркасов имеется у графа ?

Ответ:

(1) 4

(2) 8

(3) 12

(4) 16

Номер 3

Сколько имеется абстрактных двудольных графов с 4 вершинами?

Ответ:

(1) 6

(2) 7

(3) 8

(4) 9

Упражнение 3:

Номер 1

Какие из следующих графов являются двудольными?

Ответ:

(1)

(2)

(3)

(4)

Номер 2

Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу ?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

Номер 3

Какое наименьшее число ребер нужно удалить из графа K₆, чтобы получился двудольный граф?

Ответ:

(1) 4

(2) 5

(3) 6

(4) 7

Упражнение 4:

Номер 1

В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?

Ответ:

(1) 3

(2) 4

(3) 5

(4) такого графа не существует

Номер 2

Какие из следующих графов планарны?

Ответ:

(1)

(2)

(3)

(4)

Номер 3

Какое наименьшее число ребер нужно удалить из графа K₆, чтобы получился планарный граф?

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

Упражнение 5:

Номер 1

Какое наименьшее количество новых ребер нужно добавить к графу C₆,  чтобы получился непланарный граф?

Ответ:

(1) 3

(2) 4

(3) 5

(4) 6

Номер 2

В планарном графе семь вершин, из которых три имеют степень 4, остальные степень 5. Сколько граней будет в плоском изображении этого графа?

Ответ:

(1) 10

(2) 11

(3) 12

(4) такого графа не существует

Главная / Алгоритмы и дискретные структуры / Графы и алгоритмы / Тест 3