Графы и алгоритмы

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

Номер 1

G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в  графе H 9 ребер, а в графе  12 ребер. Сколько ребер в графе  ?

Ответ:

(1) 5

(2) 7

(3) 12

(4) 17

Номер 2

Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин

Ответ:

(1)

(2)

(3)

(4)

Номер 3

Какие из следующих утверждений верны?

Ответ:

(1) пересечение двух квазициклов - всегда квазицикл

(2) граф, дополнительный к квазициклу - всегда квазицикл

(3) объединение двух квазициклов, не имеющих общих ребер - всегда квазицикл

(4) если пересечение двух квазициклов - квазицикл, то их объединение - тоже квазицикл

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

Номер 1

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

Ответ:

(1) каждое ребро каркаса принадлежит точно одному фундаментальному циклу

(2) каждое ребро каркаса принадлежит хотя бы одному фундаментальному циклу

(3) каждое ребро каркаса, не являющееся перешейком, принадлежит хотя бы одному фундаментальному циклу

(4) каждое ребро графа, не принадлежащее каркасу, принадлежит точно одному фундаментальному циклу

Номер 2

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

Ответ:

(1) обязательно увеличивается

(2) увеличивается или не изменяется

(3) может увеличиться, уменьшиться или остаться прежним

(4) если граф связен, то обязательно увеличивается

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

Номер 1

Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K₇ ?

Ответ:

(1) 45

(2) 56

(3) 60

(4) 90

Номер 2

Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K_3,5?

Ответ:

(1) 4

(2) 5

(3) 6

(4) 8

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

Номер 1

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

Номер 2

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

Ответ:

(1) через любые две вершины проходит простой цикл

(2) через любые два ребра проходит простой цикл

(3) через любые три вершины проходит простой цикл

(4) через любые три вершины, среди которых имеется хотя бы одна пара смежных, проходит простой цикл

Номер 3

Какие из следующих утверждений верны?

Ответ:

(1) если ребро math

циклически связано с ребром math

, а ребро math

циклически связано с ребром math

, то ребра math

и

циклически связаны

(2) если вершина math

циклически связана с вершиной math

, а вершина math

циклически связана с вершиной math

, то вершины math

и

циклически связаны

(3) если вершина math

циклически связана с ребром math

, а ребро

циклически связано с вершиной math

, то вершины math

и

циклически связаны

(4) если ребро math

циклически связано с вершиной math

, а вершина math

циклически связана с ребром math

, то ребра math

и

циклически связаны

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

Номер 1

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

Номер 2

BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

Номер 3

Какие из следующих утверждений верны?

Ответ:

(1) если в графе каждый блок содержит ровно две вершины, то этот граф - дерево

(2) если каждый блок некоторого графа является двудольным графом, то и весь граф двудольный

(3) если каждый блок некоторого графа является планарным графом, то и весь граф планарный

(4) Если в каждом блоке связного графа имеется эйлеров цикл, то и во всем графе есть эйлеров цикл

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