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

UptoLike

ВУЗ: 

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

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

Рубрика: 

31
пересекать границу выделенной области. Обозначим через U
+
(V
1
) и
U
-
(V
1
)
множества дуг, заходящих в V
1
и исходящих из него. Например,
для графа на рис. 2
U
+
(V
1
) = {u
1
= (v
1
, v
2
)}, U
-
(V
1
) = {u
2
= (v
2
, v
1
), u
6
= (v
3
, v
4
)}.
Разделение орграфа (рис. 3, а) заключается в удалении некоторых его
частей. Суграф получается из исходного графа удалением некоторых
его дуг, но с сохранением числа вершин. На рис. 3, б показан суграф без
петель и параллельных дуг. Такой граф называется обыкновенным. Для
v
3
v
2
v
1
v
4
v
2
v
3
v
4
v
1
v
2
v
4
v
1
v
2
v
4
а) б) в) г)
Рис. 3. Разделение орграфа на подчасти:
а – орграф; б – суграф; в – подграф; г – частичный граф
а) б) в)
v
2
v
2
v
2
v
3
v
1
v
3
v
1
v
3
v
111
v
4
v
4
v
4
Рис. 3. Разновидности орграфов:
а – симметрический; б – антисимметрический; в – полный
него сохраняется связность исходного графа. Подграф образуется из ис-
ходного графа удалением некоторых вершин вместе с инцидентными
им дугами (например, вершины v
3
на рис. 3, в). Частичный подграф
получится, если к исходному графу применены обе операции, описан-
ные выше (рис. 3, г).
Некоторые специальные классы орграфов могут быть получены до-
полнительной трансформацией исходного графа.

Страницы