Основы дискретной математики

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

Номер 1

 Сколько нулей в матрице смежности ориентированного графа
G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,c), (a,a), (b,a), (c,d), (c, a), (c,c), (d,a), (d,b)}.

Ответ:

(1) 5

(2) 7

(3) 9

(4) 11

(5) 16

Номер 2

 Сколько нулей в матрице смежности ориентированного графа
G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,c), (a,a), (b,a), (b,b), (c, a), (c,d), (d,b)}.

Ответ:

(1) 4

(2) 6

(3) 8

(4) 10

(5) 16

Номер 3

 Сколько нулей в матрице смежности ориентированного графа
G= (V, E), где V={a, b, c, d}, E={ (a,b), (a,d), (b,a), (b,b), (c, a), (c,d), (d,b)}.

Ответ:

(1) 6

(2) 7

(3) 8

(4) 9

(5) 10

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

Номер 1

 Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 6-вершинном графе?

Ответ:

(1) 6

(2) 9

(3) 12

(4) 15

(5) 30

Номер 2

 Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 7-вершинном графе?

Ответ:

(1) 7

(2) 14

(3) 21

(4) 28

(5) 49

Номер 3

 Неориентированный граф называется полным, если для каждой пары разных вершин имеется соединяющее их ребро. Сколько ребер в полном 8-вершинном графе?

Ответ:

(1) 8

(2) 16

(3) 24

(4) 28

(5) 32

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

Номер 1

 Пусть G=( V, E) - это конечный ориентированный граф без циклов и  |E |> 0. Какие из следующих утверждений верны?
В G есть вершина, в которую не входят ребра.
В G есть вершина, из которой не выходят ребра.
В G есть изолированная вершина, т.е. вершина, у которой нет инцидентных ребер.

Ответ:

(1) только 1

(2) только 2

(3) только 3

(4) только 1 и 2

(5) 1, 2, и 3

Номер 2

 Пусть G=( V, E) - это конечный ориентированный граф без циклов и  |E |> 0. Какие из следующих утверждений верны?
Сумма степеней всех вершин G четна.
Если в G имеется ровно две вершины четной степени, то они связаны путем 
Если в G имеется ровно две вершины нечетной степени, то они связаны путем

Ответ:

(1) только 1

(2) только 3

(3) только 1 и 3

(4) только 1 и 2

(5) 1, 2, и 3

Номер 3

 Пусть G=( V, E) - это конечный неориентированный граф. Какие из следующих утверждений верны?
Если |E| < |V| - 1, то .граф G не является связным.
Если |E| > |V| - 1, то в G имеется цикл. 
Если в G имеется цикл, то |E| > |V| - 1

Ответ:

(1) только 1

(2) только 2

(3) только 1 и 3

(4) только 1 и 2

(5) 1, 2, и 3

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

Номер 1

 Пусть граф G=(V,E) задан своей матрицей смежности
 $A_G=\begin{array}{ccccc}
0& 1 &0 &0 &0\\
0 &1& 0& 0& 0\\
0 &0 &0 &1 &0\\
0 &1 &0 &0 &1\\
1 &0 &0 &0 &1
\end{array}$ 
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.

Ответ:

(1) 4

(2) 5

(3) 6

(4) 7

(5) 8

Номер 2

 Пусть граф G=(V,E) задан своей матрицей смежности

 $A_G=\begin{array}{ccccc}
0 & 1 & 1 & 1 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 1
\end{array}$ 
Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер,
т.е. чему равна разность |E*| - |E|.

Ответ:

(1) 4

(2) 5

(3) 6

(4) 7

(5) 8

Номер 3

 Пусть граф G=(V,E) задан своей матрицей смежности
 $A_G=\begin{array}{ccccc}

1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1\\
1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1\\
0 & 0 & 1 & 0 & 0
\end{array}$ 

Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер,
т.е. чему равна разность |E*| - |E|.

Ответ:

(1) 15

(2) 16

(3) 17

(4) 18

(5) 19

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

Номер 1

 Чему равно число связных компонент неориентированного графа
G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (5,4), (1,5), (6,7)}?

Ответ:

(1) 5

(2) 3

(3) 7

(4) 6

(5) 4

Номер 2

 Чему равно число связных компонент неориентированного графа
G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (7,4), (1,5), (6,7)}?

Ответ:

(1) 5

(2) 3

(3) 7

(4) 6

(5) 4

Номер 3

 Чему равно число связных компонент неориентированного графа
G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (1,7), (3,9), (7,4), (8,5), (6,7)}?

Ответ:

(1) 5

(2) 3

(3) 7

(4) 6

(5) 4

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

Номер 1

 Определите все базы следующего ориентированного графа G:

Ответ:

(1) {a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}

(2) {g, k, m, f}, {g, k, n, f}

(3) {g, m, n, f}

(4) {g, m, f}, {g, n, f}

(5) {g, m, e, f}, {g, n, e, f}

Номер 2

 Определите все базы следующего ориентированного графа G:

Ответ:

(1) {a, m, f}, {g, m, f}, {h,m,f}, {a, n, f}, {g, n, f}, {h, n,f}

(2) {a, m}, {g, m}, {h,m}, {a, n}, {g, n}, {h, n}

(3) {a, g, h, m, n}

(4) {g, m}, {g, n}, {h, m}, {h,n}

(5) {a, m, e}, {g, m, e}, {h,m,e}, {a, n, e}, {g, n, e}, {h, n,e}

Номер 3

 Определите все базы следующего ориентированного графа G:

Ответ:

(1) {d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}

(2) {d, h}, {e, h}, {k, h}, {m, h}

(3) {d, e, k, m, f, h}

(4) {d, f, h}, {e, f, h}, {k, f, h}, {m, f, h}, {n,f,h}

(5) {d, f, h}, {k, f, h}, {m, f, h}

Основы дискретной математики - тест 9