Реферат: Орграфы, теория и применение
Контур (замкнутый путь) орграфа G называется ГАМИЛЬТОНОВЫМ, если он содержит все вершины орграфа G. ГАМИЛЬТОНОВ ГРАФ – это орграф, имеющий гамильтонов контур.
Распознавание гамильтоновости орграфов и построение гамильтоновых контуров так же сложны, как и для неориентированных графов. Рассмотрим одно из достаточных условий гамильтоновости орграфа.
Теорема (Мейниэл, 1973). Пусть G – сильносвязный орграф порядка n>1 без петель и параллельных дуг. Если для любой пары v и w его несовпадающих несмежных вершин справедливо неравенство
delta(v)+delta(w)>=2*n-1,
то в G есть гамильтонов контур.
Пусть G=(V,E) – АЦИКЛИЧЕСКИЙ ОРГРАФ. Вершину v in V называют ЛИСТОМ, если delta+(v)=0. Если (v,w) in E, то v является НЕПОСРЕДСТВЕННЫМ ПРЕДКОМ w, а w – НЕПОСРЕДСТВЕННЫМ ПОТОМКОМ v. Если существует маршрут из v в w, то говорят, что v является ПРЕДКОМ w, а w – ПОТОМКОМ v. Эти понятия не имеют смысла для графов, имеющих циклы, так как в этом случае вершины в цикле являлись бы потомками и предками самих себя!
+-------v1------+ v4
v2<-----------------v3----------->v5<---------v6
Из вершин v2, v4, v5 дуги не выходят (листья графа), v1 является предком v5, v5 является потомком v1 и прямым потомком v3 и т.д.
Существует тесная связь между ациклическими графами и частично упорядоченными отношениями. Частичные порядки будут основаны скорее на отношении <, чем на отношении <=, и, следовательно, являются нерефлексивными и транзитивными.
Утверждения:
а) Пусть G=(V,E) - а–иклический орграф и отношение < определяется следующим образом: v<w, если v является предком w. Тогда отношение < является частичным отношением порядка на V.
б) Пусть отношение < является частичным отношением порядка на конечном множестве V. Тогда, если E={(v,w): v<w}, то пара G=(V,E) является ациклическим графом.
ОРИЕНТИРОВАННОЕ ДЕРЕВО T=(V,E) - э–о ациклический орграф, в котором одна вершина vr in V не имеет предков и называется КОРНЕМ, а каждая другая вершина имеет ровно одного непосредственного предка. Корень соединяется с любой другой вершиной единственным маршрутом. БИНАРНОЕ ДЕРЕВО - э–о ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, т.е. delta+(v)<=2 для всех v in V. Бинарное дерево является ПОЛНЫМ, если каждая вершина, не являющаяся листом дерева, имеет ровно 2 непосредственных потомка. Очевидно обобщение на k-арное дерево.
УРОВЕНЬ ВЕРШИНЫ - м–ксимальная длина маршрута от этой вершины до листа дерева.
ГЛУБИНА ВЕРШИНЫ - д–ина пути от корня до этой вершины.
ГЛУБИНА ОРДЕРЕВА - д–ина самого длинного пути в Т.
Утверждение. Для полного k-арного ордерева, в котором все l листьев имеют одинаковую глубину d, справедливо следующее:
l<=k^d; d=log(k) l.
Планарность
Плоский граф - г–аф с вершинами, расположенными на плоскости и непересекающимися ребрами. Планарный граф изоморфен плоскому. Всякий подграф планарного графа планарен. Задача о трех домах и трех колодцах. Провести от каждого из трех домов дорожки ко всем трем колодцам так, чтобы дорожки не пересекались. Граф этой задачи не является планарным. Грань графа - м–ожество всех точек плоскости, каждая пара которых может быть соединена жордановой кривой. Граница грани - м–ожество вершин и ребер, принадлежащих грани. Всякий плоский граф имеет одну, и притом единственную, неограниченную грань. Эта грань является внешней гранью графа, остальные - в–утренние.
Теорема Эйлера. Для всякого связного плоского графа n-m+f=2, где n - ч–сло вершин,m - ч–сло ребер, f - ч–сло граней. Подразбиение ребра - у–аление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной. Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ребер.
Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3. Деревья и лес. Дерево - с–язный граф без циклов. Лес (или ациклический граф) - н–ограф без циклов (может быть и несвязным).
Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:
G - д–рево;
G - с–язный граф, содержащий n-1 ребро;
G - а–иклический граф, содержащий n-1 ребро;
Любые две несовпадающие вершины графа G соединяет единственная цепь.
G - а–иклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.
Остов (каркас) связного графа - д–рево, содержащее все вершины графа. Определяется неоднозначно. Редукция графа - о–тов с наибольшим числом ребер. Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - ч–сло вершин,m - ч–сло ребер, c - ч–сло компонент связности графа. Коциклический ранг (или коранг) ν*=n-c.