Главная / Алгоритмы и дискретные структуры /
Графы и алгоритмы / Тест 1
Графы и алгоритмы - тест 1
Упражнение 1:
Номер 1
Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?
Ответ:
 (1) 8 
 (2) 16 
 (3) 27 
 (4) 64 
Номер 2
Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?
Ответ:
 (1) 8 
 (2) 16 
 (3) 27 
 (4) 64 
Номер 3
Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
Ответ:
 (1) 2 
 (2) 3 
 (3) 4 
 (4) 5 
Упражнение 2:
Номер 1
Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
Ответ:
 (1) 3 
 (2) 4 
 (3) 5 
 (4) 6 
Номер 2
Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?
Ответ:
 (1) 3 
 (2) 4 
 (3) 5 
 (4) 6 
Номер 3
Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) 3 
Упражнение 3:
Номер 1
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) 3 
Номер 2
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) 3 
Номер 3
Сколько ребер имеет граф пересечений граней трехмерного куба?
Ответ:
 (1) 6 
 (2) 8 
 (3) 12 
 (4) 24 
Упражнение 4:
Номер 1
В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
Ответ:
 (1) 7 
 (2) 14 
 (3) 18 
 (4) 21 
Номер 2
Граф имеет 4 вершины, а в его матрице смежности 8 единиц. Граф имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа ?
Ответ:
 (1) 20 
 (2) 40 
 (3) 60 
 (4) 80 
Номер 3
Какие из следующих графов изоморфны графу?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)