Дискретная математика. Прокушев Л.А. - 36 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

34
Эти же множества можно получить по матрице смежности графа на
рис. 2. Для каждого столбца v
i
не нулевые значения в столбце указыва-
ют смежные вершины (обозначения строк), из которых можно придти в
вершину v
i
за одну дугу.
Множества вершин, из которых можно придти за две дуги к верши-
нам v
1
, v
2
:
Г
-2
v
1
= Г
-
{Г
-
v
1
} = Г
-
{v
2
, v
4
} = Г
-
{v
2
} ∪ Г
–
{v
4
} = {v
1
} ∪ {v
3
, v
5
}
= {v
1
, v
3
, v
5
};
Г
-2
v
2
= Г
-
{Г
-
v
2
} = Г
-
{v
1
} = Г
-
{v
2
, v
4
} = Г
–
v
2
∪ Г
–
v
4
= {v
1
} ∪ {v
3
,
v
5
} = {v
1
, v
3
, v
5
}.
Множества вершин, из которых можно придти за три дуги к верши-
нам v
1
, v
2
: Г
–3
v
1
= Г
–
{Г
–2
v
1
} = Г
–
{v
1
, v
3
, v
5
} = Г
–
v
1
∪ Г
–
v
3
∪ Г
–
v
5
=
{v
2
, v
4
} ∪ {v
2
, v
3
} ∪ {v
5
} = {v
2
, v
3
, v
4
, v
5
};
Г
–3
v
2
= Г
–
{Г
–2
v
2
}=Г
–
{v
1
, v
3
, v
5
} = Г
–
v
1
И Г
–
v
3
∪ Г
–
v
5
={v
2
, v
4
}
∪ {v
2
, v
3
} ∪ {v
5
} = {v
2
, v
3
, v
4
, v
5
}.
Обратные транзитивные замыкания вершин v
1
, v
2
, т. е. множества вер-
шин, из которых можно прийти к этим вершинам без повторения дуг:
2
11 1 1
ˆ
{}vv v v
−−−
Γ = ∪Γ ∪Γ ∪
…
= {v
1
} И {v
2
, v
4
} И {v
1
, v
3
, v
5
} = {v
1
,
v
2
, v
3
, v
4
, v
5
};
2
22 2 2
ˆ
{}vv v v
−−−
Γ = ∪Γ ∪Γ ∪
…
= {v
2
} И {v
1
} И {v
1
, v
3
, v
5
} И {v
2
, v
3
,
v
4
, v
5
} = {v
1
, v
2
, v
3
, v
4
, v
5
};
Вершины v
1
, v
2
доступны из любых вершин графа.
Обработка ориентированного графа
№
.рав
}U{афаргигуД
0
,)0,3(,)5,2(,)3,2(,)1,2(,)5,1(,)4,1(,)0,1(,)0,1(,)5,0(,)2,0(,)1,0({
})5,5(,)4,5(,)2,5(,)1,5(,)0,5(,)4,4(,)0,4(,)1,4(,)5,3(,)4,3(,)3,3(
1
,)2,3(,)0,3(,)5,2(,)4,2(,)2,2(,)5,1(,)3,1(,)2,1(,)4,0(,)2,0(,)0,0({
})4,5(,)4,5(,)3,5(,)2,5(,)0,5(,)5,4(,)3,4(,)1,4(,)0,4(,)5,3(,)3,3(
2
,)1,3(,)0,3(,)3,2(,)3,2(,)2,2(,)5,1(,)3,1(,)1,1(,)5,0(,)3,0(,)0,0({
})5,5(,)4,5(,)4,5(,)3,5(,)2,5(,)0,5(,)5,4(,)2,4(,)0,4(,)5,3(,)4,3(
3
,)5,2(,)4,2(,)3,2(,)0,2(,)5,1(,)4,1(,)2,1(,)1,1(,)5,0(,)4,0(,)2,0({
})5,5(,)4,5(,)3,5(,)0,5(,)5,4(,)4,4(,)2,4(,)3,3(,)1,3(,)0,3(,)0,3(
4
,)1,3(,)0,3(,)5,2(,)4,2(,)0,2(,)5,1(,)5,1(,)3,1(,)1,1(,)5,0(,)3,0({
})3,5(,)2,5(,)0,5(,)5,4(,)4,4(,)2,4(,)1,4(,)5,3(,)5,3(,)4,3(,)2,3(
Варианты множества дуг графа
Таблица 5

Страницы