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

Определение 1.: Пусть V - непустое множество, V² - множество всех его двухэлементных подмножеств. Пара (V,E), где E - произвольное подмножество V², называется неориентированным графом. Элементы множества V называются вершинами, а элементы множества E - ребрами. Если {v₁,v₂} - ребро, то вершины v₁ и v₂ будем называть концами ребра.

Будем использовать символы |V| и |E| для обозначения, соответственно, числа вершин и числа ребер в графе (V,E).

Определение 2.: Пусть V - непустое множество, V*V - его декартов квадрат. Пара (V,A), где A - произвольное подмножество V*V, называется ориентированным графом (орграфом). Элементы множества V называются вершинами, а элементы множества A - дугами (ориентированными ребрами). Если (v₁,v₂) - дуга, то вершины v₁ и v₂ называются началом дуги и концом дуги, соответственно.

Хотя неориентированные и ориентированные графы - существенно различные объекты, в определенных случаях неориентированные графы можно рассматривать как ориентированные графы, в которых каждому ребру соответствует две противоположно ориентированные дуги.

Определение 3.

Пусть G и H - графы, f - взаимно однозначное отображение множества V(G) на множество V(H), а g - взаимно однозначное отображение E(G) на E(H). Обозначим Q упорядоченную пару (f,g). Будем говорить, что Q есть изоморфное отображение (изоморфизм) графа G на граф H, если выполняется следующее условие: вершина x инцидентна ребру A в графе G тогда и только тогда, когда вершина fx инцидентна ребру gA в графе H.

Если такой изоморфизм Q существует, то будем говорить, что графы G и H изоморфны. Ясно, что необходимым условием изоморфизма является тот факт, что |V(G)|=|V(H)| и |E(G)|=|E(H)|.

Мы можем рассматривать Q как операцию, преобразующую граф G в граф H, и в соответствии с этим писать QG=H. Удобно также писать Qv=fv и QA=gA (для каждой вершины v и каждого ребра A графа G).

Автоморфизмом графа G называется изоморфизм графа G на себя.

Определение 4.

Простой путь в неориентированном графе - это последовательность смежных ребер (v₁,v₂), (v₂,v₃),..., (v_k-1,v_k), таких, что все v_i кроме, быть может, v₁ и v_k различны. Простой путь в ориентированном графе - это последовательность смежных одинаково ориентированных дуг (v₁,v₂), (v₂,v₃),..., (v_k-1,v_k), таких, что все v_i , кроме, быть может, v₁ и v_k различны. Число ребер, составляющих простой путь, называется длиной простого пути.

Простой путь называется:

в неориентированном графе - цепью, а
в ориентированном графе - путем.

Простой путь, начинающийся и заканчивающийся в одной и той же вершине, называется:

в неориентированном графе - циклом, а
в ориентированном графе - контуром.

Расстояние между вершинами u и v в связном неориентированном графе - это минимальная длина цепи между u и v.

Определение 5.

Неориентированный граф называется ациклическим, если в нем отсутствуют циклы. Будем называть ориентированный граф бесконтурным, если он не содержит контуров. В литературе для обозначения таких ориентированных графов употребляется также термин "ациклический ориентированный граф".

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

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

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

Существует один простой и важный тип графов, которому, однако, разные авторы дали одинаковое название, - это деревья. Деревья важны не только потому, что они находят приложения в различных областях знания, но и в силу их особого положения в самой теории графов. Последнее вызвано предельной простотой структуры деревьев. Часто при решении какой-либо задачи о графах ее сначала исследуют на деревьях.

Определение 6.

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

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

Известны и другие определения дерева. В приведенной ниже теореме отражены некоторые из них.

Назовем два ребра смежными, если у них есть общая вершина.

Пусть p - натуральное число. Граф K_p будем называть полным, если каждая пара его вершин смежна.

Пусть графы G₁ и G₂ имеют непересекающиеся множества вершин V₁ и V₂ и непересекающиеся множества ребер E₁ и E₂. Объединением G₁UG₂ таких графов называется граф, множеством вершин которого является V=V₁UV₂, а множеством ребер - E=E₁UE₂.

Теорема.

Для графа G, имеющего p вершин и q ребер, следующие утверждения эквивалентны:

G - дерево;
любые две вершины в G соединены единственной цепью;
G - связный граф и p=q+1;
G - ациклический граф и p=q+1;
G - ациклический граф, и если любую пару несмежных вершин соединить ребром x, то в графе G+x будет точно один цикл;
G - связный граф, отличный от K_p для p>=3, и если любую пару несмежных вершин соединить ребром x, то в графе G+x будет точно один цикл;
G - граф, отличный от K₃UK₁ и K₃UK₂, p=q+1, и если любую пару несмежных вершин соединить ребром x, то в графе G+x будет точно один цикл.

Со следующего шага мы начнем рассматривать способы представления графов.

Предыдущий шаг Содержание Следующий шаг