Дискретная математика

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

Номер 1

Существуют ли простые графы 
		без петель с 5 вершинами 
		со следующим набором степеней:

Ответ:

(1) (1,2,3,4,5)

(2) (1,2,3,3,5)

(3) (1,2,3,3,4)

(4) (2,2,3,3,4)

Номер 2

Существуют ли простые графы 
		без петель с 4 вершинами 
		со следующим набором степеней:

Ответ:

(1) (1,2,3,4)

(2) (1,2,3,3)

(3) (1,2,2,3)

(4) (1,1,2,3)

Номер 3

Существуют ли простые графы 
		без петель с 6 вершинами 
		со следующим набором степеней:

Ответ:

(1) (1,2,3,4,5,6)

(2) (1,2,3,4,5,5)

(3) (1,2,3,4,4,5)

(4) (1,3,3,3,3,5)

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

Номер 1

Сколько ребер могут иметь простые графы без петель 
		с 5 вершинами?

Ответ:

(1) одно ребро

(2) 5 ребер

(3) 10 ребер

(4) 25 ребер

Номер 2

Сколько ребер могут иметь простые графы без петель 
		с 6 вершинами?

Ответ:

(1) одно ребро

(2) 6 ребер

(3) 15 ребер

(4) 36 ребер

Номер 3

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

Ответ:

(1) одно ребро

(2) 4 ребер

(3) 6 ребер

(4) 16 ребер

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

Номер 1

Какой радиус может быть у графа
		с 5 вершинами?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 5

Номер 2

Какой радиус может быть у графа
		с 4 вершинами?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

Номер 3

Какой радиус может быть у графа
		с 6 вершинами?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 5

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

Номер 1

Какое расстояние между двумя вершинами возможно графе с 5 вершинами?

Ответ:

(1) 3

(2) 4

(3) 5

(4) 6

Номер 2

Какое расстояние между двумя вершинами возможно графе с 4 вершинами?

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

Номер 3

Какое расстояние между двумя вершинами возможно графе с 6 вершинами?

Ответ:

(1) 2

(2) 4

(3) 5

(4) 6

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

Номер 1

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

Ответ:

(1) первый граф

(2) второй граф

(3) третий граф

Номер 2

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

Ответ:

(1) первый граф

(2) второй граф

(3) третий граф

Номер 3

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

Ответ:

(1) первый граф

(2) второй граф

(3) третий граф

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

Номер 1

Граф задан матрицей смежности:
		0 1 1 0 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0
		Отметьте каким он является:

Ответ:

(1) сильно связным

(2) односторонне связным

(3) слабо связным

(4) несвязным

Номер 2

Отметьте каким является граф заданный матрицей смежности:
0 1 1 1 0
0 0 0 1 0
0 0 0 0 1
0 0 1 0 1
0 0 0 0 0

Ответ:

(1) сильно связным

(2) односторонне связным

(3) несвязным

(4) слабо связным

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

Номер 1

Отметьте графы, в которых возможна топологическая сортировка:

Ответ:

(1) сильно связные

(2) односторонне связным

(3) слабо связные

(4) несвязные

Номер 2

Какие графы могут совпадать со своим 
		графом конденсации?

Ответ:

(1) сильно связным;

(2) односторонне связным;

(3) слабо связным;

(4) несвязным?

Номер 3

Каким может быть граф конденсации?

Ответ:

(1) сильно связным

(2) односторонне связным

(3) слабо связным

(4) несвязным

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

Номер 1

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

Ответ:

(1) 1

(2) 2

(3) n-1

(4) n

Номер 2

Дан ациклический граф с n вершинами. 
Сколько в нем может быть вершин, которые не являются ни источниками, ни стоками?

Ответ:

(1) n

(2) n+1

(3) n²

(4) n-2

Номер 3

Отметьте возможные длины максимального пути в ациклическом графе с 6 вершинами и 5 ребрами:

Ответ:

(1) 1

(2) 2

(3) 4

(4) 5

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

Номер 1

Каким может быть ориентированное дерево?

Ответ:

(1) сильно связным

(2) односторонне связным

(3) слабо связным

Номер 2

Сколько центров может быть у дерева 
		с n вершинами?

Ответ:

(1) 1

(2) 2

(3) n-1

(4) n

Номер 3

Сколько висячих вершин может быть у дерева 
		с n вершинами?

Ответ:

(1) 1

(2) 2

(3) n-1

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

Номер 1

В потоковой сети, приведенной на рисунке, 
		все пропускные способности равны 4:
		
		Нарушены ли в ней правила распределения потоков?

Ответ:

(1) Нет, все верно.

(2) Да, нарушен закон Кирхгофа.

(3) Да, нарушено ограничение на пропускную способность.

Номер 2

В потоковой сети, приведенной на рисунке, 
		все пропускные способности равны 4:
		
		Нарушены ли в ней правила распределения потоков?

Ответ:

(1) Нет, все верно.

(2) Да, нарушен закон Кирхгофа.

(3) Да, нарушено ограничение на пропускную способность.

Номер 3

В потоковой сети, приведенной на рисунке, 
		все пропускные способности равны 4:
		
		Нарушены ли в ней правила распределения потоков?

Ответ:

(1) Нет, все верно.

(2) Да, нарушен закон Кирхгофа.

(3) Да, нарушено ограничение на пропускную способность.

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

Номер 1

Граф является двудольным, если он ...

Ответ:

(1) имеет цикл с четным числом вершин

(2) имеет цикл с нечетным числом вершин

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

Номер 2

Во сколько цветов можно раскрасить цикл, содержащий 
		9 вершин?

Ответ:

(1) в 2 цвета

(2) в 3 цвета

(3) в 4 цвета

Номер 3

Для любого k число путей 
		длины k, начинающихся с любой вершины 
		графа G, всегда одинаково, если

Ответ:

(1) G — неориентированное дерево

(2) G — неориентированный цикл

(3) G — полный граф

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

Номер 1

Степень Cⁿ 
		матрицы смежности C 
		ориентированного графа G 
		содержит ненулевые элементы во всех 
		клетках главной диагонали если:

Ответ:

(1) все вершины G имеют петли

(2) некоторые вершины G имеют петли

(3) граф G содержит циклы

(4) граф G - сильно связный

Номер 2

Ориентированный граф G содержит циклы. 
		Какое из утверждений всегда верно?

Ответ:

(1) степень Cⁿ матрицы смежности C ориентированного графа G содержит ненулевые элементы во всех клетках главной диагонали

(2) степень Cⁿ матрицы смежности C ориентированного графа G содержит ненулевые элементы во некоторых клетках главной диагонали

(3) сумма math

степеней матрицы смежности C ориентированного графа G содержит ненулевые элементы в некоторых клетках главной диагонали

(4) сумма math

степеней матрицы смежности C ориентированного графа G содержит ненулевые элементы во всех клетках главной диагонали

Дискретная математика - тест 16