nextupprevious

Next:2.2 Грамматики, языки и автоматы
Up:2 Словарь понятий, используемых в заданиях
Previous:2 Словарь понятий, используемых в заданиях
 

2.1 Графы и системы дорог

Граф -- это пара $(V,T)$, где $V$ -- конечное непустое множество вершин, а $E$ -- множество неупорядоченных пар $(u,v)$ вершин из $V$, называемых ребрами. Говорят, что ребро $s=<u,v>$соединяет вершины $u$ и $v$. Ребро $s$ и вершина $u$ (а также $s$ и $v$) называются инцидентными, а вершины $u$ и $v$ -- смежными. Ребра, инцидентные одной и той же вершине, также называются смежными. Степень вершины равна числу ребер, инцидентных ей.


Рис. 1. Граф $G_1$

Для простоты мы будем ограничиваться классом графов без петель, т.е. таких ребер $<u,v>$, что $u=v$, и без кратных ребер, т.е. таких, которые соединяют одну и ту же пару вершин. Если же есть кратные ребра, то граф называется мультиграфом, а если еще и петли, то -- псевдографом.

На рис. 1 приведен пример графа. В этом графе шесть вершин и семь ребер, степень вершин 1 - 4 равна 3, а вершин 5 - 6 равна 1.

Часть графа$G=(V,E)$ -- это такой граф $G'=(V',E')$ что $V' \subseteq V$ и $E' \subseteq E$. Подграфом графа $G$ называется такая его часть $G'$, которая вместе со всякой парой вершин $u,v$ содержит и ребро $(u,v)$, если оно есть в $G$. Например, граф без ребер

является частью графа $G_1$ (рис. 1), но не его подграфом; граф


 

является подграфом графа $G_1$.

Путь, соединяющий вершину $u$ с вершиной $v$, -- это последовательность вершин $P=v_0,v _1,\ldots,v_n$$(n \geq 0)$ такая, что $v_0=u, v_n=v$ и для любого $i$$(0 \leq i \leq n-1)$ вершины $v_i$ и $v_{i+1}$ соединены ребром. В нем вершина $v_0$ называется начальной, $v_n$ -- конечной, а остальные -- внутренними. Длина пути$P$ равна количеству ребер, т.е. $n$. Например, в графе $G_1$ путь 1,3,4,2 имеет длину 3 и соединяет вершины 1 и 2.

Путь $P=v_0,v _1,\ldots,v_n$ называется простым, если все его вершины различны. Путь $P$замкнут, если $v_0=v_n$. Замкнутый путь, в котором все ребра различны, называется циклом. Простой цикл -- это замкнутый путь, все вершины которого, кроме $v_0$ и $v_n$, попарно различны.

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

Рис. 2. Пример гамильтонова графа $G_2$.Его простой цикл выделен полужирными линиями

Расстояние между двумя вершинами -- это длина кратчайшего пути, соединяющего эти вершины. Например, расстояние между вершинами 3 и 4 в $G_2$ (рис. 2) равно 2.

Обод -- это простой цикл -- граф, вершины которого $v_0,v_1,\ldots,v_n (n>2)$ можно занумеровать так, что для всех $i$$(1 \leq i \leq n-1)$ вершина $v_i$ соединена ребрами с $v_{i-1}$ и $v_{i+1}$, вершина $v_0$ -- с $v_n$, а других ребер нет.

Граф называется связным, если для любой пары вершин существует соединяющих их путь. Максимальный связный подграф графа называется его компонентой связности. Вершины одной компоненты называются взаимно достижимыми. Например, графы $G_2$ и $G_3$ (рис. 3) связны, а $G_1$ -- нет: он содержит две компоненты связности.

Рис. 3. Обод $G_3$ с минимальным числом вершин

Дополнением графа $G$ называется граф $G'$ с тем множеством вершин, что и у $G$, причем две различные вершины смежны в $G'$ тогда и только тогда, когда они не смежны в $G$. Граф называется полным, если любые две его различные вершины соединены ребром. Тривиальный граф -- это граф с пустым множеством ребер, а упорядоченный -- это граф, в котором множество преемников каждой вершины упорядочено. Два графа $G$ и $H$изоморфны, если существует взаимно однозначное отображение (называемое изоморфизмом) множества вершин графа $G$ на множество вершин графа $H$, сохраняющее смежность. Автоморфизмом графа $G$ называется изоморфизм графа $G$ на себя. Например, отображение $\phi,$ определяемое по правилам $\phi(1)=3,$$\phi(2)=4,$$\phi(3)=1,$ и $\phi(4)=2$, является автоморфизмомом графа $G_4$ (рис. 4).

Рис. 4. Граф $G_4$

Ориентированный граф, или орграф, $G=(V,E)$ отличается от графа тем, что $E$ -- это множество упорядоченный пар $(u,v)$ вершин $u,v \in V$, называемых дугами. Дуга $(u,v)$ ведет от вершины $u$ к вершине $v$. При этом вершину $v$ называют преемником вершины $u$, а $u$ -- предшественником вершины $v$. Мы будем ограничиваться орграфами без петель, т.е. без дуг $(u,v)$ с $u=v$ (рис. 5).

Рис. 5. Орграф $G_5$

Понятия части орграфа, пути, расстояния между вершинами, простого и замкнутого пути, цикла определяются для орграфа так же, как и для графа, но с учетом ориентации дуг. Вершина $v$ орграфа $G$достижима из вершины $u$, если существует путь в $G$, ведущий от $u$ к $v$. Например, в $G_5$ (рис. 5) все вершины достижимы из верхней.

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

Корневое дерево -- это дерево с выделенной вершиной, называемой корнем. Все вершины корневого дерева распадаются на уровни по величине их расстояния от корня, так, что все ребра соединяют вершины соседних уровней. Рассматривая каждое ребро $<u,v>$ корневого дерева как дугу $(u,v)$ от вершины меньшего уровня к вершине большего уровня получаем понятие ориентированного дерева (или ордерева). Это -- связный орграф без циклов, удовлетворяющий следующим условиям:

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

б) к каждой вершине, отличной от корня, ведет ровно одна дуга; говорят, что она соединяет отца с сыном.

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

Граф $G_4$ (рис. 4) является деревом, а орграф $G_5$ (рис. 5) -- ордеревом.

Поддеревом корневого дерева $T$ называется его часть $T'$, которая является корневым деревом, удовлетворяющим следующему условию: $T'$ состоит из вершин и дуг, достижимых в $T$ от корня $T'$.

Двоичное (или бинарное) дерево -- это ордерево, в котором каждая вершина имеет не более двух преемников, называемых левым и правым преемниками (или сыновьями). Орграф на рис. 5 является двоичным деревом.

2-3-дерево -- это упорядоченное ордерево, в котором расстояния от корня до всех листьев совпадают, а каждая вершина, отличная от листа, имеет двух или трех преемников. На рис. 6 дан пример 2-3-дерева.

Рис. 6. Пример 2-3-дерева

Деревом (двоичного) поиска для множества чисел $S$ называется размеченное двоичное дерево, в котором каждая вершина $v$ помечена числом $l(v)\in S$ и которое удовлетворяет следующим условиям:

а) $l(u)<l(v)$ для всех вершин $u,v$, если вершина $u$ находится в поддереве, корень которого -- левый преемник $v$;

б) $l(u)>l(v)$ для всех вершин $u,v$, если вершина $u$ находится в поддереве, корень которого -- правый преемник $v$;

в) для всякого числа $a \in S$ существует единственная вершина $v$, для которой $l(v)=a$.

Пример дерева двоичного поиска для множества чисел {5,4,8,6,1,3,9} приведен на рис. 7.

Рис. 7. Дерево двоичного поиска для целых чисел
 

Обозначим через $\rho(T)$ максимум среди расстояний от корня дерева $T$ до его листьев (мы полагаем $\rho(T)=-1$, если $T$ пусто).

АВЛ-деревом называется дерево двоичного поиска, в котором для каждой вершины $v$ выполнено следующее условие:

\begin{displaymath}\vert \rho (T_1)- \rho (T_2)\vert \leq 1,\end{displaymath}

где $v_1$ и $v_2$ -- преемники $v$, а $T_1$ и $T_2$ -- поддеревья с корнями $v_1$ и $v_2$. На рис. 8 дан пример АВЛ-дерева.

Рис. 8 АВЛ-дерево для множества чисел {5,1,7,0,3,2,4,6,9,8}

Обход корневого дерева (или ордерева)$T$ состоит в посещении вершин этого дерева в некотором порядке. Например, при его обходе в ширину вершины $T$ посещаются по уровням, начиная с корня, и слева направо (от старших потомков к младшим). Рассмотрим три разных обхода упорядоченного дерева $T$ (с корнем $v$ и его сыновьями $v_1,\ldots,v_n)$в глубину: префиксный, постфиксный и инфиксный обходы.

Префиксный обход (прямой обход или П-обход) выполняется по следующим правилам:

1) посетить корень $v$;
2) выполнить префиксный обход поддеревьев с корнями $v_1,\ldots,v_n$ в указанной последовательности.

Постфиксный обход (обратный обход или О-обход) описывается следующим образом:

1) выполнить постфиксный обход поддеревьев с корнями $v_1,\ldots,v_n$ в указанной последовательности;
2) посетить корень $v$.

Инфиксный обход (обход во внутреннем порядке или В-обход) определяется так:

1) выполнить инфиксный обход поддерева с корнем $v_1$;
2) посетить корень дерева $T$;

3) выполнить инфиксный обход поддеревьев с корнями $v_2,\ldots,v_n$ в указанной последовательности.

На рис. 9 приведен порядок посещений вершин двоичного дерева при П-, О- и В-обходе.

Рис. 9. Порядок обхода вершин двоичного дерева при П-, О- и В-обходе

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

Рис. 10. Пример системы односторонних дорог

Понятия пути, достижимости и замкнутого пути определяются для систем дорог аналогично подобным понятиям для графов и орграфов. Длина пути в системе дорог -- это сумма длин дорог этого пути. Расстояние между двумя городами -- это длина минимального пути между этими городами. Например, расстояние между городами $A$ и $C$ в изображенной на рис. 10 системе дорог равно 6.

Next:2.2 Грамматики, языки и автоматы
Up:2 Словарь понятий, используемых в заданиях
Previous:2 Словарь понятий, используемых в заданиях

 © В.Н. Касьянов, Е.В. Касьянова, 2004