Ориентированные графы

Определение 1. Ребро графа называется ориентированным ребром, если одну из его вершин считать началом, а другую — концом этого ребра.

Определение 2. Граф, у которого все ребра ориентированные, называется ориентированным графом.

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

Определение 3. Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины).

Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).

Так, на рисунке изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:

Ст.вх.А=2, Ст.вых.А=1

Ст.вх.В=2, Ст.вых.В=0

Ст.вх.Д=1, Ст.вых.Д=3

Определение 4. Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3,..., Аn-1Аn в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.

На ниже приведенном рисунке показаны примеры путей в ориентированном графе. Причем, первые два пути— простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым, т. к. через вершину Г путь «проходил» дважды.

Определение 5. Ориентированным циклом называется замкнутый путь в ориентированном графе.

На предыдущем рисунке приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути. Так, на рисунке пути от А к Д могут быть различны и иметь различную длину.

Первый путь имеет длину 2, второй - 3, а третий — 4.

Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка равно 2; записывают так: S(АД)=2.

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

Так, расстояние между вершинами Б и Д графа, представленного на рисунке бесконечно:

Самым известным примером производящей функции является, конечно, бином Ньютона.

Здесь

-биномиальные коэффициенты

(число сочетаний из n по к, то есть число к-элементных подмножеств n-элементного множества).

БИЛЕТ 7