Ориентированные графы. Пути и циклы в ориентированном графе.

Орграфом G наз. пара мн-в (N,U), элементы N – вершины, элементы U – упорядоченые пары вершин наз. дугами (i,j)¹(j,i). Вершины (i,j) наз. смежными, если в G имеется дуга (i,j). При этом дугу (i,j) наз. инцедентной вершинам i и j. Вершину i наз. началом дуги, j – концом дуги. Две дуги, имеющие общую вершину наз. смежными. Понятие паралельных дуг как и у графов.

Орграф наз. простым, если он не имеет паралельных дуг. Будем предполагать, что мы работаем с простым огрграфом.

Полустепень захода d^-(i) – это число дуг, выходящих из i. Sⁿ_i=1d^-(i)= Sⁿ_i=1d⁺(i)=m (m – число дуг).

Орграф наз. полным, если "(i,j) существуют дуги (i,j) и (j,i).

Понятия порождённого, остовного подграфа и просто подграфа аналогичны соотв. понятиям для графов. Последовательность вершин i₁, i₂,…, i_m наз. маршрутом, если "(i_p,i_p+1), $(i_p,i_p+1)ÎU.

Последовательность вершин, такая, что " две соседние вершины в этой посл. смежные, наз. полумаршрутом. Понятие замкнутого маршрута аналогично известному.

Маршрут у к-го все дуги различны наз. путём. Полумаршрут, у к-го все дуги различны наз. полупутём. Замкнутый наз. контуром, полупуть – полуконтуром. Понятие простых путей и т.д. аналогичны известным.

Граф D=(N,W) лежит в основе орграфа G, если любые две вершины D смежны тогда и только тогда (неравные вершины), когда они смежны в G.

Способы задания орграфов.

Ориентированый граф можно задать списком дуг, матрицами смежности: a_ij={1,(i,j)ÎU;0(i,j)ÏU}, матрицей инцедентности (предполагается, что дуги перенымерованы: 1,…,m):{1,если из i выжодит дуга в j; -1,если из j в i; ±1,петля; 0, иначе}.

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

Деревья

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

Теорема. Если граф G является деревом, то число его ребер (m) и число его вершин (n) связаны соотношением m= п – 1. Доказательство этой теоремы проведем по индукции по числу вершин. Если данный граф содержит всего 2 вершины, то в нем только 1 ребро, и нужное соотношение выполнено. Пусть наше утверждение выполнено для любого дерева, число вершин которого строго меньше n. Докажем его для дерева G, содержащего n вершин. Возьмем висячую вершину дерева G и удалим ее и графа (вместе с единственным ребром, выходящим из этой вершины). Тогда новый граф также является деревом: новый граф не содержит контуров (циклов), он остается связным. (Если бы новый граф оказался несвязным, то какие-то две вершины графа G были бы связаны между собой через удаленную (висячую) вершину. В этом случае степень этой висячей вершины была бы больше или равна 2, что невозможно). Таким образом, новый граф является деревом, и по индукционному предположению для него число ребер меньше числа вершин на единицу. Так как число вершин и число ребер нового графа отличается от числа вершин и ребер “старого” графа G на единицу, то для графа G также выполнено то же самое соотношение. Таким образом, индукция проведена, и теорема доказана.

Теорема. Следующие 4 условия равносильны:

-граф G является деревом;

-число ребер (т) и число вершин в графе (п) связаны соотношением т = п – 1;

-любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен;

-граф G связен и не содержит контуров.

Заметим, что генеалогическое дерево (в котором вершины графа – это некоторый человек и его прямые предки, а смежные вершины – это люди, связанные родством: мать и ее ребенок или отец и его ребенок) деревом в смысле теории графов не является (так как оно обязательно должно содержать циклы: некоторые предки данного человека должны иметь общего предка).