Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1716


1.1. некоторые основные определения

Графом (неориентированным графом) G(V,E) называется совокупность двух множеств, где V – конечное непустое множество элементов, называемых вершинами, а E – множество неупорядоченных пар различных элементов множества V (эти пары называются ребрами). Граф, состоящий из одной вершины, называется тривиальным.

 Говорят, что ребро e = (u, v) соединяет вершины u и v. Ребро e и вершина u (а также e и v) называются инцидентными, а вершины u и v – смежными. Ребра, инцидентные одной и той же вершине, также называются смежными.

Степень вершины – это число ребер, инцидентных ей. Вершина графа, имеющая степень 0, называется изолированной, а имеющая степень 1, – висячей.

Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф – мультиграфом.

Если элементом множества E может быть пара одинаковых (не различных) элементов V, то такой элемент E называется петлей. Псевдограф – это граф, у которого наряду с кратными ребрами допускаются и петли, причем даже несколько петель при одной вершине.

Граф называется простым, если любая пара вершин соединена не более чем одним ребром и граф не имеет петель.

Маршрут (путь) – это чередующаяся последовательность

      a = v0, e1, v1, e2, ..., vn–1, en, vn = b

вершин и ребер графа такая, что ei = (vi-1 , vi), 1 ≤ i ≤ n. Говорят, что маршрут соединяет вершины a и b – концы маршрута. В простом графе маршрут можно задать перечислением лишь его вершин a = v0, v1, …, vn = b или его ребер e1 , e2, …, en.

Маршрут называется цепью, если все его ребра различные. Маршрут называется замкнутым, если v0 = vn.

Замкнутая цепь называется циклом. Цепь называется простой, если не содержит одинаковых вершин. Простая замкнутая цепь называется простым циклом.

Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа.

Вершина u достижима из вершины v, если существует путь из v в u.

Длина пути v0 , v1, …, vn равна числу его ребер, т.е. n.

Расстояние между двумя вершинами – это длина кратчайшего пути, соединяющего эти вершины.

 Часть графа G(V, E) – это такой граф G'(V',E'), что V' Í V и E' Í E.

Подграфом графа G называется такая его часть G', которая вместе со всякой парой вершин u, v содержит и ребро (u, v), если оно есть в G.

Дополнением графа G называется граф G' с тем же множеством вершин, что и у G, причем две различные вершины смежны в G' тогда и только тогда, когда они несмежны в G. Ребра графов G и G' вместе образуют полный граф. Граф называется полным, если любые две его вершины смежны.

Два графа G1 и G2 изоморфны, если существует взаимно однозначное отображение множества вершин графа G1 на множество вершин графа G2, сохраняющее смежность.

Граф называется связным, если для любой пары вершин существует соединяющий их путь. Максимальный связный подграф несвязанного графа называется компонентой связности данного графа.

Если задана функция F: V→M, то множество M называется множеством пометок, а граф – помеченным. Если задана функция F: E→M, т.е. ребрам графа приписаны веса, то граф называется взвешенным.

Ребро графа называется ориентированным, если существен порядок расположения его концов. Граф, все ребра которого ориентированные, называется ориентированным графом (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества E – дугами. Дуга (u, v) ведет от вершины u к вершине v, Вершину v называют преемником вершины u, а u – предшественником вершины v. Понятия части орграфа, пути, расстояния, простого и замкнутого пути, цикла определяются для орграфа так же, как и для графа, но с учетом ориентации дуг.

Источник орграфа – это вершина, от которой достижимы все остальные вершины. Сток орграфа – это вершина, достижимая со всех других вершин.

Деревом называется связный граф без циклов.

Корневое дерево – это связный орграф без циклов, удовлетворяющий условиям:

имеется единственная вершина, называемая корнем, в которую не входит ни одна дуга;

к каждой некорневой вершине ведет одна дуга.

Вершины, из которых не выходит ни одна дуга, называются листьями.