Составители:
Рубрика:
8
Для ряда практических задач удобно использовать понятие взвешенного
графа. Граф называется взвешенным, если каждому его ребру (дуге) (x
i
, x
j
)
поставлено в соответствие вещественное число p
ij
, называемое весом этого
ребра ( дуги ). Для взвешенного графа аналогичным образом определяется
матрица весов.
В зависимости от конкретной задачи веса несуществующих
ребер считаются равными нулю или бесконечности.
Простой путь, цикл графа. Дерево
Приведем еще ряд понятий и определений , которые нам потребуются в
дальнейшем.
Простой путь
в графе - это последовательность смежных ребер, у
которой все вершины, за исключением, может быть, последней и первой,
различны. Простой путь можно задавать последовательностью смежных
вершин в виде: x
i1
, x
i2
, ... , x
ip
. Если G - орграф, то путь в нем называется
ориентированным
. В графе G расстояние от вершины x
i
до вершины x
j
- это
наименьшая из длин путей между ними. Если в пути первая и последняя
вершины совпадают, то такой путь называется
циклом
. Так, для графа на рис.1а
из вершины x
1
в
x
4
можно попасть, например, путями: x
1
, x
4
; x
1
, x
5
, x
2
, x
4
.
На этом же графе путь x
1
, x
5
, x
2
, x
4
, x
1
является циклом.
Если для любой пары вершин существует хотя бы один путь между ними,
то граф называется
связным
. Так, все графы, изображенные на рис.1(а-г),
являются связными.
Деревом
называется связный граф, не содержащий циклов. Если у
дерева выделена одна вершина, то она называется
корнем
дерева, а сам граф -
корневым
деревом. Так, легко видеть, что графы 1б, 1в, являются деревьями,
причем, 1б - корневым деревом (корень x
1
); графы же 1а, 1г не являются
деревьями, как содержащие циклы.
Любопытно, что теория деревьев была впервые разработана при изучении
конкретных физических объектов и связей между ними. В 1847г. Г. Кирхгоф,
изучая вопрос об определении тока в каждом контуре и проводнике заданной
электрической цепи, заменил электрическую цепь соответствующим графом.
Кирхгоф показал, что для решения поставленной задачи, достаточно
рассматривать циклы полученного графа. Он установил также, что каждый
такой цикл определяется любым из остовных деревьев, т.е. остовных
подграфов, являющихся деревьями. Через 10 лет А.Кели, пытаясь перечислить
изомеры предельных углеводородов с данным числом атомов углерода, пришел
к абстрактной постановке задачи: найти число деревьев с заданным
количеством вершин, таких, что вершине могут быть смежны одно или четыре
ребра. Лишь в 1869г. известный математик К. Жордан независимо от работ
Кирхгофа и Кели начал систематически изучать деревья, как абстрактные
математические объекты.
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
