Введение в теорию графов

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

Номер 1

Выполнить операцию объединения G₁   G₂ для графов, показанных на рисунке 1

Ответ:

(1) граф представлен на рис.2 а

(2) граф представлен на рис.2 б

(3) граф представлен на рис.2 в

(4) нет верного рисунка

Номер 2

Выполнить операцию пересечения G₁  G₂ для графов, показанных на рисунке 1

Ответ:

(1) граф представлен на рис.2 в

(2) граф представлен на рис.2 б

(3) граф представлен на рис.2 а

Номер 3

Выполнить операцию нахождения кольцевой суммы G₁   G₂ для графов, показанных на рисунке 1

Ответ:

(1) граф представлен на рис.2 в

(2) граф представлен на рис.2 б

(3) граф представлен на рис.2 а

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

Номер 1

Выполнить операцию объединения G₁  ∪ G₂ для графов, представленных матрицами смежности в таблице 1Матрица смежности G1 X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 0 1 0
X₃ 0 0 0 0 0
X₄ 0 0 1 0 0
X₅ 0 1 0 1 0 
Матрица смежности G2 X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 1 0 1
X₃ 0 0 0 0 0
X₄ 0 1 1 0 1
X₅ 0 0 0 0 0

a X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 0 0 0
X₃ 0 0 0 0 0
X₄ 0 0 1 0 0
X₅ 0 0 0 0 0 б X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 0
X₂ 0 0 1 1 1
X₃ 0 0 0 0 0
X₄ 0 1 0 0 1
X₅ 0 1 0 1 0 в X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 1 1 1
X₃ 0 0 0 0 0
X₄ 0 1 1 0 1
X₅ 0 1 0 1 0

Ответ:

(1) граф представлен б

(2) граф представлен а

(3) граф представлен в

Номер 2

Выполнить операцию пересечения G₁ ∩ G₂ для графов, представленных матрицами смежности в таблице 1
Матрица смежности G1 X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 0 1 0
X₃ 0 0 0 0 0
X₄ 0 0 1 0 0
X₅ 0 1 0 1 0 
Матрица смежности G2 X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 1 0 1
X₃ 0 0 0 0 0
X₄ 0 1 1 0 1
X₅ 0 0 0 0 0

a X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 0 0 0
X₃ 0 0 0 0 0
X₄ 0 0 1 0 0
X₅ 0 0 0 0 0 б X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 0
X₂ 0 0 1 1 1
X₃ 0 0 0 0 0
X₄ 0 1 0 0 1
X₅ 0 1 0 1 0 в X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 1 1 1
X₃ 0 0 0 0 0
X₄ 0 1 1 0 1
X₅ 0 1 0 1 0

Ответ:

(1) граф представлен б

(2) граф представлен а

(3) граф представлен в

Номер 3

Выполнить операцию нахождения кольцевой суммы G₁  ⊕ G₂ для графов, представленных матрицами смежности в таблице 1
Матрица смежности G1 X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 0 1 0
X₃ 0 0 0 0 0
X₄ 0 0 1 0 0
X₅ 0 1 0 1 0 
Матрица смежности G2 X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 1 0 1
X₃ 0 0 0 0 0
X₄ 0 1 1 0 1
X₅ 0 0 0 0 0

a X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 0 0 0
X₃ 0 0 0 0 0
X₄ 0 0 1 0 0
X₅ 0 0 0 0 0 б X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 0
X₂ 0 0 1 1 1
X₃ 0 0 0 0 0
X₄ 0 1 0 0 1
X₅ 0 1 0 1 0 в X₁ X₂ X₃ X₄ X₅
X₁ 0 0 0 0 1
X₂ 1 0 1 1 1
X₃ 0 0 0 0 0
X₄ 0 1 1 0 1
X₅ 0 1 0 1 0

Ответ:

(1) граф представлен б

(2) граф представлен а

(3) граф представлен в

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

Номер 1

Для графа G₁, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х₁,х₂). Верно ли результат представлен  матрицей смежности ниже? 
			 X_(1,2) X₃ X₄ X₅
X_(1,2) 1 1 1
X₃ 
X₄ 1 
X₅ 1 1

	X_(1,2)	X₃	X₄	X₅
X_(1,2)	1		1	1
X₃
X₄		1
X₅	1		1

Ответ:

(1) неверно

(2) верно

Номер 2

Для графа G₁, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х₃,х₄). Верно ли результат представлен  матрицей смежности ниже? 
X₁ X₂ X_(3,4) X₅
X₁ 1
X₂ 1 
X_(3,4) 1 
X₅ 1 1

	X₁	X₂	X_(3,4)	X₅
X₁				1
X₂	1
X_(3,4)			1
X₅		1	1

Ответ:

(1) неверно

(2) верно

Номер 3

Для графа G₁, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х₃,х₄). Верно ли результат представлен  на рис. 2а?

Ответ:

(1) неверно

(2) верно

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

Номер 1

Для графа G₂, показанном на рисунке 1, выполнить операцию стягивания двух вершин (х₁,х₂). Верно ли результат представлен  матрицей смежности ниже?
X_(1,2) X₃ X₄ X₅
X_(1,2) 1 1
X₃ 
X₄ 1 1 1
X₅

	X_(1,2)	X₃	X₄	X₅
X_(1,2)		1		1
X₃
X₄	1	1		1
X₅

Ответ:

(1) неверно

(2) верно

Номер 2

Для графа G₂, показанном на рисунке 1, выполнить операцию стягивания двух вершин (х₃,х₄). Верно ли результат представлен  матрицей смежности ниже?
 X₁ X₂ X_(3,4) X₅
X₁ 1
X₂ 1 1 1
X_(3,4) 1 1
X₅

	X₁	X₂	X_(3,4)	X₅
X₁				1
X₂	1		1	1
X_(3,4)		1		1
X₅

Ответ:

(1) неверно

(2) верно

Номер 3

Для графа G₂, показанном на рисунке a, выполнить операцию стягивания двух вершин (х₃,х₄). Верно ли результат представлен  графом на рисунке б?

Ответ:

(1) неверно

(2) верно

Номер 4

Для графа G₁, показанном на рисунке a, выполнить операцию стягивания двух вершин (х₁,х₂). Верно ли результат представлен  графом на рисунке б?

Ответ:

(1) неверно

(2) верно

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

Номер 1

В графе  G₆ , показанном на рис. 1 удалить вершину х₁. Результат представлен ниже в матричном виде а X₂ X₃
X₂ 0 1
X₃ 1 0 б X₁ X₂
X₁ 0 1
X₂ 1 0 в X₁ X₃
X₁ 0 1
X₃ 1 0

Ответ:

(1) верно б

(2) верно а

(3) верно в

Номер 2

В графе  G₆ , показанном на рис. 1 удалить вершину х₂. Результат представлен в матричном виде ниже  а X₂ X₃
X₂ 0 1
X₂ 1 0 б X₁ X₂
X₁ 0 1
X₂ 1 0 в X₁ X₃
X₁ 0 1
X₃ 1 0

Ответ:

(1) верно б

(2) верно а

(3) верно в

Номер 3

В графе  G₆ , показанном на рис. 1 удалить вершину х₃. Результат представлен в матричном виде ниже  а X₂ X₃
X₂ 0 1
X₂ 1 0 б X₁ X₂
X₁ 0 1
X₂ 1 0 в X₁ X₃
X₁ 0 1
X₃ 1 0

Ответ:

(1) верно б

(2) верно а

(3) верно в

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

Номер 1

В графе  G₆ , показанном на рис. 1 удалить дугу (х₃,х₂). Результат представлен в матричном виде ниже  а X₁ X₂ X₃
X₁ 1 1
X₂ 1 1
X₃ 1 б X₁ X₂ X₃
X₁ 1
X₂ 1 1
X₃ 1 1 в X₁ X₂ X₃
X₁ 1 
X₂ 1 1
X₃ 1 1

Ответ:

(1) верно б

(2) верно а

(3) верно в

Номер 2

В графе  G₆ , показанном на рис. 1 удалить дугу (х₁,х₂). Результат представлен ниже  в матричном виде   а X₁ X₂ X₃
X₁ 1 1
X₂ 1 1
X₃ 1 б X₁ X₂ X₃
X₁ 1
X₂ 1 1
X₃ 1 1 в X₁ X₂ X₃
X₁ 1 
X₂ 1 1
X₃ 1 1

Ответ:

(1) верно б

(2) верно а

(3) верно в

Номер 3

В графе  G₆ , показанном на рис. 1 удалить дугу (х₁,х₃). Результат представлен ниже  в матричном виде  а X₁ X₂ X₃
X₁ 1 1
X₂ 1 1
X₃ 1 б X₁ X₂ X₃
X₁ 1
X₂ 1 1
X₃ 1 1 в X₁ X₂ X₃
X₁ 1 
X₂ 1 1
X₃ 1 1

Ответ:

(1) верно б

(2) верно а

(3) верно в

Введение в теорию графов - тест 2