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

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

Даны матрицы смежности и матрица инцидентности. Соответствуют ли они графу на рисунке?
матрица смежности
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

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

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

соответствует матрица инцидентности

не соответствуют обе матрицы

соответствует матрица смежности(Верный ответ)

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

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

а
		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

Какая из представленных матриц контрдостижимости соответствует графу на рис. 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

Для графа, представленного на рисунке, данаматрица смежности. Верно ли представлен граф?

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

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

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

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

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

Соответствует ли матрица инциденций матрице смежности (обе матрицы представлены ниже):

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

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

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

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

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

c
	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	1	0	0	1
X₆	1	0	1	0	0

Для графа 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	1	0
X₃	0	0	0	1	0
X₅	0	0	1	0	0
X₇	1	0	0	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	1
X₇	1	0	1	0	0