Тест по теории графов

Дата добавления: 2015-07-23; просмотров: 3382; Нарушение авторских прав

1. Дан граф G:

Цикломатическое число графа G равно

а) 2;

б) 3;

в) 0;

г) 4.

2. Степень каждой вершины графа Е⁴ равна:

а) 4;

б) 3;

в) 16;

г) 8;

3. В полном графе К₈ диаметр и радиус равны:

а) 1;

б) 2;

в) 8;

г) 4.

4. Для того, чтобы граф обладал эйлеровым циклом, необходимо и достаточно, чтобы:

а) степени всех вершин были нечетными

б) степени ровно двух вершин были четными

в) степени всех вершин были четными

г) степени ровно двух вершин были нечетными

5. Матрица смежности реберного графа вычисляется по формуле:

а) А(G_Р)=В^т(G)´В(G) – sE; б) А(G_Р)=В(G)´В^т(G) – sE;

в) А(G_Р)=В(G)´В^т(G) – 2E; г) А(G_Р)=В^т(G)´В(G) – 2E.

6. Если в алгоритме фронта волны v_jÎFW_k(v_i) (k£n-1, n – количество вершин орграфа), то

а) вершина v_j достижима из вершины v_i

б) вершина v_j не достижима из вершины v_i

в) вершина v_i достижима из вершины v_j

г) вершина v_i не достижима из вершины v_j

7. У графа К₇ хроматическое число c(К₇) равно:

а) 1;

б) 3;

в) 4;

г) 7;

8. Дан граф G:

Количество компонент связности графа G

а) 2;

б) 1;

в) 4;

г) 5;

9. Матрица достижимости орграфа D обозначается:

а) T(D);

б) S(D);

в) B(D);

г) D(D).

10. Формула Эйлера для планарного графа имеет вид:

а) n + m - г = 2;

б) n - m + г = 2;

в) n + m + г = 2;

г) n - m - г = 2;

11. Длина минимального пути в нагруженном орграфе среди всех путей из v₁ в v₆, содержащих не более 4 дуг, обозначается:

а)

;

б) l_6,4;

в)

;

г) l_4,6.

12. Количество циклов в любом дереве D:

а) 1;

б) 0;

в) 2;

г) 3;

13. Однородный граф G имеет 15 ребер, степень каждой вершины равна 5, тогда количество вершин графа G:

а) 15

б) 6

в) 20

г) 10

14. Число полных трехвершинных подграфов в полном двудольном графе К_6,7 равно

а) 6;

б) 7;

в) 13;

г) 0.

15. Дан граф:

Степень вершины 1 равна

а) 1;

б) 2;

в) 3;

г) 4;

16. Цикломатическое число графа равно

а) количеству компонент связности

б) размерности пространства базисов циклов графа

в) количеству циклов в графе

г) количеству ребер в цикле

<== предыдущая лекция	\|	следующая лекция ==>
Тест по теории множеств и отношений	\|	V. Экология и безопасность жизнедеятельности