ВУЗ:
Составители:
Рубрика:
14
связный граф стягивается к графу К
3
. Например, граф называемый простой
цепью Р
4
, не стягивается к графу К
3
.
Расщепление вершины – операция двойственная к операции стягивания
ребра. Пусть v – одна из вершин графа G. Разобьем ее окружение произвольным
образом на две части M и N и выполним следующее преобразование графа G:
удалим вершину v вместе с инцидентными ей ребрами, добавим новые вершины u и
w и соединяющее их ребро uw, вершину u соединим ребром с каждой вершиной из
множества М, а
вершину w- с каждой вершиной из множества N. Полученный граф
обозначим символом G. Будем говорить, что G получается из графа G
расщеплением вершины v (рис. 19).
Рис. 19
Операция удаления ребра. Эта операция позволяет обнаружить важные
закономерности, свойственные графам. При удалении ребра (u, v) из графа G
получается граф с теми же вершинами, что и граф G, и всеми ребрами, кроме ребра
(u, v). (рис. 20)
Рис. 20
3. Маршруты, циклы и связность.
Одно из наиболее простых свойств, которым может обладать граф, это
свойство быть связным. Рассмотрим основные структурные свойства связных и
несвязных графов.
Маршрутом, соединяющим вершины v
1
и v
L+1
называется чередующаяся
последовательность v
1
, e
1
, v
2
, e
2
, v
3
, e
3
, …, e
L
, v
L+1
вершин и ребер графа, такая что
е
i
=v
i
хv
i+1
(i=1,…,L). Эта последовательность начинается и кончается вершиной, и
каждое ребро последовательности инцидентно двум вершинам, одна из которых
непосредственно предшествует ему, а другая непосредственно следует за ним.
Очевидно, что (v
1
и v
L+1
) – маршрут можно задать последовательностью v
1
, v
2
,…,
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
