КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Тест по теории графов
1. Дан граф G:
Цикломатическое число графа G равно
| а) 2; | б) 3; | в) 0; | г) 4. |
2. Степень каждой вершины графа Е4 равна:
| а) 4; | б) 3; | в) 16; | г) 8; |
3. В полном графе К8 диаметр и радиус равны:
| а) 1; | б) 2; | в) 8; | г) 4. |
4. Для того, чтобы граф обладал эйлеровым циклом, необходимо и достаточно, чтобы:
а) степени всех вершин были нечетными
б) степени ровно двух вершин были четными
в) степени всех вершин были четными
г) степени ровно двух вершин были нечетными
5. Матрица смежности реберного графа вычисляется по формуле:
| а) А(GР)=Вт(G)´В(G) – sE; б) А(GР)=В(G)´Вт(G) – sE; | в) А(GР)=В(G)´Вт(G) – 2E; г) А(GР)=Вт(G)´В(G) – 2E. |
6. Если в алгоритме фронта волны vjÎFWk(vi) (k£n-1, n – количество вершин орграфа), то
а) вершина vj достижима из вершины vi
б) вершина vj не достижима из вершины vi
в) вершина vi достижима из вершины vj
г) вершина vi не достижима из вершины vj
7. У графа К7 хроматическое число c(К7) равно:
| а) 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. Длина минимального пути в нагруженном орграфе среди всех путей из v1 в v6, содержащих не более 4 дуг, обозначается:
а)  ;
| б) l6,4; | в)  ;
| г) l4,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. Цикломатическое число графа равно
а) количеству компонент связности
б) размерности пространства базисов циклов графа
в) количеству циклов в графе
г) количеству ребер в цикле
Дата добавления: 2015-01-29; просмотров: 444; Мы поможем в написании вашей работы!; Нарушение авторских прав |