Основы синтеза и диагностирования автоматов. Воронин В.В. - 77 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

Составители: 

Рубрика: 

73
v
2
хотя бы в одном исходном графе] или [u
2
=v
2
и u
1
смежна с v
1
хо-
тя бы в одном исходном графе]. Например, найдем произведение
G
1
×
G
2
=К
2
×
К
3
. Результирующий граф представлен на рис. 2.42.
Важный тип графов, называемых кубами, наиболее естественно
описывается с помощью операции произведения графов. Рекурсивно
п-мерный куб
θ
n
определяется в следующем виде
θ
1
=К
2
;
θ
n
=К
2
×
θ
n-1
.
Таким образом
θ
n
имеет 2
n
вершин, которые можно пред-
ставлять наборами (a
1
,a
2
,…,a
n
),
где а
i
равно 0 или 1. Две вер-
шины куба
θ
n
смежны, если их
двоичное представление отличается только в одной позиции (разря-
де). Пример рекурсивного вычисления первых трёх кубов приведен
на рис. 2.43. При произведении графов число вершин результирую-
щего графа определится как п
1
п
2
, а число дуг – п
1
q
2
+п
2
q
1
, где п
1
и п
2
,
соответственно, число вершин первого и второго исходных графов, а
q
1
и q
2
– их число дуг.
4. Дополнение⎯G графа G имеет в качестве множества вершин
множество Х, две вершины в⎯G смежны тогда и только тогда, когда
они не смежны в G. В полном графе К
p
каждая пара вершин смежная,
следовательно, в⎯К
p
нет ни одной дуги. Граф⎯К
p
называют вполне не
связным. Пример дополнения полного графа приведён на рис. 2.44.
Рис. 2.42
=
×
b
а
a
b
c
(b,a) (b,b) (b,c)
(a,a) (a,b) (a,c)

Страницы