Автоматизированное проектирование промышленных изделий

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

Номер 1

Как называют запись вида ?

Ответ:

(1) цикломатическое число

(2) бихроматическое число

(3) хроматическое число

Номер 2

Как называют запись вида
 $X_{1},  X_{2}, … , X_{k},  \;\;X = \bigcup\limits_{i=1}^{k}{X_i}, \;\;
\forall X_{i}, X_{j} \suset X;\;\; [X_{i}\cap X_{j}=\varnothing ] ;$

Ответ:

(1) цикломатическое число

(2) бихроматический граф

(3) хроматическое число

Номер 3

Как называют запись вида
 $X = X_{1}\cupX_{2},   X_{1}\cap X_{2};\\
\forall x_{i} , x_{j}\in X [(x_{i} , x_{j}) = u_{f }\in U \Rightarrow (x_{i}\in X_{1 }& x_{j}\in X_{2})\cup(x_{i}\in X_{2} & x_{j}\in X_{1})].$

Ответ:

(1) цикломатическое число

(2) бихроматический граф

(3) хроматическое число

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

Номер 1

Какая характристика графа указывает то наименьшее число рёбер, которое нужно удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т.е. добиться отсутствия у графа циклов?

Ответ:

(1) цикломатическое число

(2) бихроматический граф

(3) хроматическое число

Номер 2

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

Ответ:

(1) цикломатическое число

(2) бихроматический граф

(3) хроматическое число

Номер 3

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

Ответ:

(1) цикломатическое число

(2) бихроматический граф

(3) хроматическое число

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

Номер 1

Как называют граф , если удаление любой его вершины  с инцидентными ей рёбрами уменьшает хроматическое число графа?

Ответ:

(1) критический

(2) критический 1 - хроматический

(3) критический 2 - хроматический

(4) критический 3 - хроматический

Номер 2

Как называют простой цикл нечётной длины, если  при удалении из него любой вершины с инцидентными ей рёбрами получим двудольный граф?

Ответ:

(1) критический

(2) критический 1 - хроматический

(3) критический 2 - хроматический

(4) критический 3 - хроматический

Номер 3

Как называют граф, имеющий две вершины, соединённые ребром?

Ответ:

(1) критический

(2) критический 1 - хроматический

(3) критический 2 - хроматический

(4) критический 3 - хроматический

Номер 4

Как называют граф, имеющий одну вершину?

Ответ:

(1) критический

(2) критический 1 - хроматический

(3) критический 2 - хроматический

(4) критический 3 - хроматический

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

Номер 1

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

Ответ:

(1) заведомо неплоский граф

(2) заведомо плоский граф

(3) плоский гра

Номер 2

Как называют граф, если известно, что число некратных рёбер графа
                              ?

Ответ:

(1) заведомо неплоский граф

(2) заведомо плоский граф

(3) плоский гра

Номер 3

Как называют граф, если известно, что   число некратных рёбер графа                                                                           ?

Ответ:

(1) заведомо неплоский граф

(2) заведомо плоский граф

(3) плоский граф

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

Номер 1

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

Ответ:

(1) число планарности графа

(2) толщина графа

(3) критерий бипланарности произвольного графа.

Номер 2

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

Ответ:

(1) число планарности графа

(2) толщина графа

(3) критерий бипланарности произвольного графа

Номер 3

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

Ответ:

(1) число планарности графа

(2) толщина графа

(3) критерий бипланарности произвольного графа

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

Номер 1

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

Ответ:

(1) полный граф

(2) пустой граф

(3) критический граф

Номер 2

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

Ответ:

(1) полный граф

(2) пустой граф

(3) критический граф

Номер 3

Как называется  полный граф, если его хроматическое число равно ?

Ответ:

(1) полный граф

(2) пустой граф

(3) критический граф

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

Номер 1

Как называется матрица, строки и столбцы которой со Ответствуют вершинам графа, а её    элемент равен числу кратных рёбер, связывающих вершины и  (или направленных от вершины  к вершине  для орграфов).

Ответ:

(1) матрица смежности

(2) матрица весовых соотношений

(3) матрица длин

(4) матрица инцидентности.

Номер 2

Как называется  матрица  , общий элемент которой
 $d_{i j}  =    \left \{ \begin{array}{l}
l_{i j }\text{, если }x_{i}\text{ и }x_{j}\text{ смежны};\\
0 \text{, если }x_{i}\text{ не смежна }x_{j}, 
\end{array}$ 
где  - длина ребра ?

Ответ:

(1) матрица смежности

(2) матрица весовых соотношений

(3) матрица длин

(4) матрица инцидентности

Номер 3

Как называется  матрица , общий элемент которой
 $c_{i j}  =    \left \{ \begin{array}{l}
t_{i j }\text{, если }x_{i}\text{ и }x_{j}\text{ смежны};\\
0 \text{, если }x_{i}\text{ не смежна }x_{j}, 
\end{array}$ 
где  - вес связи ?

Ответ:

(1) матрица смежности

(2) матрица весовых соотношений

(3) матрица длин

(4) матрица инцидентности

Номер 4

Как называется матрица, если для неориентированного графа её элементы определяются по следующему правилу: - элемент равен , если вершина   инцидентна ребру и равен нулю, если  и  не инцидентны; в случае орграфа ненулевой  - элемент равен , если  - начальная вершина дуги , и равен , если  - конечная вершина дуги .

Ответ:

(1) матрица смежности

(2) матрица весовых соотношений

(3) матрица длин

(4) матрица инцидентности

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

Номер 1

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

Ответ:

(1) маршрут

(2) простой цикл

(3) простая цепь

Номер 2

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

Ответ:

(1) маршрут

(2) простой цикл

(3) простая цепь

Номер 3

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

Ответ:

(1) маршрут

(2) простой цикл

(3) простая цепь

Автоматизированное проектирование промышленных изделий - тест 18