§2. Маршруты, цепи, циклы

Маршрутом в графе называется конечная последовательность ребер вида: Этот маршрут обозначают:

Петля называется тривиальным маршрутом.

Длиной маршрута называется число ребер в нем.

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

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

Если то цепь называется замкнутой.

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

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

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

Теорема. Первое и второе определения связности равносильны.

Связанность вершин является отношением эквивалентности на множестве вершин графа.

Свойства отношения эквивалентности:

1. рефлексивность ;

2. симметричность (если то );

3. транзитивность (если и то )

Отношение эквивалентности задает разбиение графа на компоненты связности.

Теорема. Каждый граф единственным образом представляется в виде объединения непересекающихся связных подграфов (компонент связности).

Число ребер в графе минимально, если удаление любого ребра приводит к увеличению компонент связности.

Если при удалении какого-то ребра в графе, число компонент связности увеличилось на единицу, то это ребро называется мостом или перешейком.

§3. Числовые функции на графе

Говорят, что на вершинах графа реализуется числовая функция, если каждой вершине ставится в соответствие некоторое число из некоторого множества L.

Значением маршрута через вершины называется число .

Минимальным (максимальным) маршрутом через вершины некоторого множества маршрутов Р называется маршрут с минимальным (максимальным) значением λ.

Говорят, что на ребрах графа реализуется числовая функция, если каждому ребру сопоставлено число из некоторого множества М. Причем

Значением маршрута через ребра, соединяющие вершины называется число

Минимальным (максимальным) маршрутом через ребра некоторого множества маршрутов Р называется маршрут с минимальным (максимальным) значением λ.

§4. Деревья и леса

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

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

Теорема (характеристические свойства дерева). Пусть граф имеет n вершин. Тогда следующие утверждения равносильны:

1. Т – дерево (определение)

2. Т не содержит циклов и имеет (n-1) ребер

3. Т – связен и имеет (n-1) ребер

4. Т – связен и каждое его ребро является мостом

5. Любые две вершины графа Т соединены ровно одной простой цепью

6. Т не содержит циклов, но, добавляя в него любое новое ребро, получим граф, содержащий ровно один цикл.

Остовным деревом называется подграф графа G, полученный стиранием ребер из циклов до удаления всех циклов, являющийся деревом.

Полным графом называется граф (без кратных ребер), в которых каждая пара вершин соединена ребром. Число рёбер полного графа равно .

Теорема. Число остовных деревьев полного графа с n вершинами равно .

Следствие. Для произвольного простого графа с n вершинами число его остовных деревьев не превосходит числа .