ВУЗ:
Составители:
Рубрика:
3. Суграф, каждой вершине которого инцидентна хотя бы одна дуга, (∀ v
i
∈H ∃
e
j
∈H (e
j
adj v
i
)) называется покрывающим. В нем нет изолированных вершин (рис. 24,г).
4. Покрывающий суграф с минимальным числом ребер называется остовом или
стягивающей сетью (рис. 24,д).
5. Часть H графа G, сохраняющая все дуги, инцидентные выделенным вершинам
графа G, называется подграфом, порожденным графом G (рис. 24,е).
6. Полный подграф H графа G называется кликой (рис. 24, ж).
Каждый подграф
полного графа является кликой.
7. Подграф, образованный выделением одной вершины v
i
∈
G и всех смежных с
нею вершин, называется звездным (рис. 24,з).
2.7. Маршруты, цепи и циклы
Маршрут или путь – это такая последовательность дуг (e
1
, ..., e
i
, ..., e
l
), что
каждые 2 соседних дуги имеют общую, инцидентную им вершину, причем e
1
– первая
дуга, а e
l
– последняя дуга маршрута l
≤
m. В неорграфе маршрут выражается через
последовательность ребер, поскольку направленность маршрута несущественна. Дуга e
i
может встречаться в маршруте более одного раза.
Поскольку каждая дуга графа может быть представлена парой смежных вершин,
маршрут может выражаться через последовательность попарно смежных вершин, число
которых на 1 больше числа дуг: (v
1
, ..., v
j
, ..., v
l+1
). Здесь началом v
1
маршрута является
вершина, инцидентная e
1
, и не инцидентная e
l
, а концом v
l+1
маршрута – вершина,
инцидентная e
l
и не инцидентная e
l-1
. Внутренние (промежуточные) вершины
инцидентны дугам маршрута. Начало (конец) маршрута может оказаться внутренней
вершиной, если она входит в маршрут более одного раза.
Пример.
Выразить маршруты μ соединяющие вершины v
1
и v
3
графа G, через дуги
и вершины (рис. 25).
а) б) в) г)
д) е) ж) з)
Рис. 24
