Определение. Вершина w графа D (или орграфа) называется достижимой из вершины v, если либо w=v, либо существует путь из v в w (маршрут, соединяющий v и w).
Определение. Граф (орграф) называется связным, если для любых двух его вершин существует маршрут (путь), который их связывает. Орграф называется односторонне связным, если если для любых двух его вершин по крайней мере одна достижима из другой.
Определение. Псевдографом D(V, X), ассоциированным с ориентированным псевдографом, называется псевдограф G(V, X0) в котором Х0 получается из Х заменой всех упорядоченных пар (v, w) на неупорядоченные пары (v, w).
Определение. Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.
Эйлеровы и гамильтоновы графы.
Определение. Цепь (цикл) в псевдографе G называется эйлеровым, если она проходит по одному разу через каждое ребро псевдографа G.
Теорема. Для того чтобы связный псевдограф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными.
Теорема. Для того, чтобы связный псевдограф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.
Определение. Цикл (цепь) в псевдографе G называется гамильтоновым, если он проходит через каждую вершину псевдографа G ровно один раз.
Пример.
 |
- в графе есть и эйлеровый и гамильтонов циклы
 |
- в графе есть эйлеров цикл, но нет гамильтонова
- в графе есть гамильтонов, но нет эйлерова цикла
- в графе нет ни эйлерова, ни гамильтонова цикла
Граф G называется полным, если каждая его вершина смежна со всеми остальными вершинами. В полном графе всегда существуют гамильтоновы циклы.
Также необходимым условием существования гамильтонова цикла является связность графа.
Деревья и циклы.
Определение. Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.
У графа, который является деревом, число ребер на единицу меньше числа вершин. Дерево не содержит циклов, любые две его вершины можно соединить единственной простой цепью.
 |
Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина, т.к. в противном случае в графе будет цикл.
Для графов, которые сами по себе не являются деревьями, вводится понятие остовного дерева.
Определение. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G – связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G)-1 ребер.
Таким образом, любое остовное дерево графа G есть результат удаления из графа G ровно m(G) - (n(G) - 1) = m(G) – n(G) + 1 ребер.
Число v (G) = m(G) – n(G) + 1 называется цикломатическим числом связного графа G.
Одной из самых распространенных задач является задача построения остовного дерева минимальной длины графа. Для решения этой задачи применяется следующий алгоритм.
1) Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему вершинами оно образует подграф G2.
2) Строим граф G3, добавляя к графу G2 новое ребро минимальной длины, выбранное среди ребер графа G, каждое из которых инцидентно какой либо вершине графа G2, и одновременно инцидентно какой – либо вершине графа G, не содержащейся в графе G2.
3) Строим графы G4, G5, …, Gn, повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.
Пример. Определить минимальное остовное дерево нагруженного графа.
Граф называется нагруженным, если на множестве его дуг задана некоторая функция, которая называется весовой функцией, и определяет длину дуги.
В нашем примере – весовая функция определяет длины дуг числами 1, 2, 3, 4, 5.
v2 2 v3
 |
1 4
1 v5 3
5 3
v1 4 v4
2 2
1 1 1 1 1 1 1 3
G2 G3 G4 G5
На четвертом шаге алгоритма получили дерево G5, которое соединяет все вершины исходного графа. Таким образом, дерево G5, будет минимальным остовным деревом графа G.
Элементы топологии.
Топология изучает понятия непрерывности и близости с абстрактной точки зрения.
Определение. Окрестностью точки р называется произвольное множество U, содержащее открытый шар (не включая границу) с центром в точке р.
Окрестностью на плоскости, очевидно, является открытый круг с центром в точке р.
Из определения окрестности вытекают следующие очевидные свойства:
1) Точка р принадлежит любой своей окрестности.
2) Если U – окрестность точки р, а V É U, то V – тоже окрестность точки р.
3) Если U и V – окрестности точки р, то их пересечение U Ç V тоже будет окрестностью точки р.
4) Если U – окрестность точки р, то можно найти такую окрестность V точки р, что W = V Ì U является окрестностью является окрестностью каждой из своих точек.
Определение. Топологическим пространством называется множество Е, каждая точка которого р имеет набор подмножеств множества Е, называемых окрестностями точки р и удовлетворяющих приведенным выше свойствам.
Частным случаем топологического пространства является метрическое пространство.
Определение. Пусть Е – топологическое пространство, а F – его подмножество. Пусть р – точка множества F. Назовем подмножество U множества F окрестностью точки р в F, если U=FÇV, где V – окрестность точки р в E.
При этом множество F называется подпространством пространства Е.