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

<<- Назад к вопросам

Выполнить операцию объединения 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

(Отметьте один правильный вариант ответа.)

Варианты ответа

граф представлен в(Верный ответ)

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

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

Похожие вопросы

Выполнить операцию нахождения кольцевой суммы 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

Выполнить операцию пересечения 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	1	1	1
0	0	1	1
0	0	0	1
1	1	1	1

b
0	1	0	1
0	0	0	1
0	0	1	0
1	0	1	0

c
1	0	1	1
1	1	0	1
0	1	1	1
1	1	1	1

d
0	0	0
1	0	0
1	1	0
1	1	1

По матрицам смежности определить какие из графов являются полными.

а
1	1	1	1
0	0	1	1
0	0	0	1
0	0	0	0

b
0	1	0	1
0	0	0	1
0	0	1	0
1	0	1	0

c
1	0	1	0
1	1	0	1
0	1	1	1
0	1	1	1

d
1	0	1
1	1	0
0	1	1
1	0	1

По матрицам смежности определить какие из графов являются полными.

а
1	1	1	1
0	1	0	1
0	0	1	1
0	0	0	1
1	1	1	1

b
0	1	0	1	0
0	0	0	1	1
1	1	0	0	0
0	0	1	0	1
1	0	1	0	0

c
1	1	0	1	1
1	1	1	0	1
0	1	1	1	1
1	0	1	1	1
1	1	1	1	1

d
0	0	0	0
1	0	0	0
1	1	0	0
1	1	1	0
1	1	1	1

Какая из представленных матриц достижимости соответствует графу на рисунке 1?

а
		X₁	X₂	X₃	X₄	X₅	X₆
	X₁	0	0	0	1	1	1
R=	X₂	1	0	1	1	1	1
	X₃	1	0	0	1	1	1
	X₄	1	0	0	0	1	1
	X₅	1	0	0	1	0	1
	X₆	1	0	0	1	1	0

б
		X₁	X₂	X₃	X₄	X₅	X₆
	X₁	1	0	0	1	1	1
R=	X₂	1	1	1	1	1	1
	X₃	1	0	1	1	1	1
	X₄	1	0	0	1	1	1
	X₅	1	0	0	1	1	1
	X₆	1	0	0	1	1	1

в
		X₁	X₂	X₃	X₄	X₅	X₆
	X₁	1	1	1	1	1	1
R=	X₂	0	1	0	0	0	0
	X₃	0	1	1	0	0	0
	X₄	1	1	1	1	1	1
	X₅	1	1	1	1	1	1
	X₆	1	1	1	1	1	1

Даны матрицы смежности и матрица инцидентности. Соответствуют ли они графу на рисунке?

матрица смежности
	X₁	X₂	X₃	X₄
X₁	1	1	0	0
X₂	0	0	1	1
X₃	0	0	0	0
X₄	1	1	1	0

матрица инциденций
	a₁	a₂	a₃	a₄	a₅	a₆	a₇
X₁	0	1	1	0	0	0	-1
X₂	0	-1	0	-1	1	0	0
X₃	0	0	0	0	-1	-1	0
X₄	0	0	-1	1	0	1	1

Какая из представленных матриц контрдостижимости соответствует графу на рис. 1?

а
		X₁	X₂	X₃	X₄	X₅	X₆
	X₁	0	0	0	1	1	1
Q=	X₂	1	0	1	1	1	1
	X₃	1	0	0	1	1	1
	X₄	1	0	0	0	1	1
	X₅	1	0	0	1	0	1
	X₆	1	0	0	1	1	0

б
		X₁	X₂	X₃	X₄	X₅	X₆
	X₁	1	0	0	1	1	1
Q=	X₂	1	1	1	1	1	1
	X₃	1	0	1	1	1	1
	X₄	1	0	0	1	1	1
	X₅	1	0	0	1	1	1
	X₆	1	0	0	1	1	1

в
		X₁	X₂	X₃	X₄	X₅	X₆
	X₁	1	1	1	1	1	1
Q=	X₂	0	1	0	0	0	0
	X₃	0	1	1	0	0	0
	X₄	1	1	1	1	1	1
	X₅	1	1	1	1	1	1
	X₆	1	1	1	1	1	1

Для графа, представленного на рисунке 1 построить матрицу достижимости R

а
		X₁	X₂	X₃	X₄	X₅
	X₁	1	1	1	1	1
R=	X₂	0	0	1	1	1
	X₃	0	0	1	1	0
	X₄	0	0	0	1	0
	X₅	0	0	0	1	1

б
		X₁	X₂	X₃	X₄	X₅
	X₁	1	1	1	1	1
R=	X₂	0	0	1	1	1
	X₃	0	0	0	1	0
	X₄	0	0	0	0	0
	X₅	0	0	0	1	0

в
		X₁	X₂	X₃	X₄	X₅
	X₁	1	1	1	1	1
R=	X₂	0	1	1	1	1
	X₃	0	0	1	1	0
	X₄	0	0	0	1	0
	X₅	0	0	0	1	1

Для графа G = (X, A), представленного на рисунке 1, описать матрицей смежности порожденный подграф {х₁,х₂,х₃,х₄,х₅}

а
	X₁	X₂	X₃	X₄	X₅
X₁	0	1	0	0	0
X₂	0	0	1	0	1
X₃	0	0	0	0	1
X₄	0	0	1	0	0
X₅	0	0	1	0	0

b
	X₁	X₂	X₃	X₄	X₅
X₁	0	1	0	0	0
X₂	0	0	1	0	1
X₃	0	0	0	1	1
X₄	0	0	0	1	0
X₅	0	0	1	1	0

c
	X₁	X₂	X₃	X₄	X₅
X₁	0	1	0	0	0
X₂	0	0	1	0	1
X₃	0	0	0	1	1
X₄	0	0	0	0	0
X₅	0	0	1	0	0