- •Глава 3. Направленные графы
- •3.1.2. Задание диграфов с помощью множеств
- •Определения
- •3.1.3. Полустепени диграфа
- •3.1.4. Последовательности полустепеней диграфа
- •Определение
- •Обратный диграф d-1(V,e-1) – это диграф, у которого множества вершин совпадает с множеством вершин исходного диграфа, а дуги имеют обратную ориентацию.
- •Определение
- •Определение
- •Определения
- •Определение
- •Определение
- •Теорема
- •Класс сложности
- •2.6. Типы связности диграфа.
- •3.7. Достижимость
- •Матрица достижимости r(u,V) задается следующим образом:
- •Замечание
- •3.8. Направленные деревья
- •3.10. Топологическое упорядочение
- •2.11. Подструктуры диграфа
- •2.11.1. Конденсация
- •Класс сложности
- •2.11.2. База и антибаза диграфа
- •2.11.3. Доминирующее множество вершин
- •2.13. Гамильтоновы диграфы
3
Определение
.2.1. Унарные операции
Диграф Н(W,F) являетсяподдиграфомдиграфаD=(V,А), еслиWVиFА (т.е. все вершины и дуги которого являются вершинами и дугами диграфа).
Если множество вершин поддиграфа равно множеству вершин диграфа, то такой поддиграф называется каркасным.
Если Wявляется подмножеством вершин диграфаD=(V,A), топодграфом, индуцированным множеством W, будет подграф с вершинамиWи всеми дугами диграфаDмежду этими вершинами.
Диграф, полученный из диграфа заменой дуг на ребра, называется неографом основания.
Обратный диграф d-1(V,e-1) – это диграф, у которого множества вершин совпадает с множеством вершин исходного диграфа, а дуги имеют обратную ориентацию.
Транзитивным замыканиемдиграфаD=(V,E) называется такой диграфD#=(V,P), который:
имеет те же вершины, что и диграф D;
если Dимеет направленный путь от вершиныuк вершинеv(uv), то диграфD#имеет дугу отuкv
Определение
Операция построения реберного диграфа L(D)=(U,F) диграфаD=(V,A) состоит в следующем:
каждой вершине uUреберного диграфаL(D) сопоставлена дуга диграфаD;
вершины L(D) соединены дугой, если для двух дуг диграфа{x1,y1},{x2,y2}Aвыполняется условиеy1=x2(т.е. голова дуги {x1,y1} совпадает с хвостом дуги {x2,y2}).
При заданном диграфе D=(V,A) имеется рекурсивное определение реберных диграфов порядка два, три и более:
L(L(D))=L2(D),L(L2(D)), …
Определение
Полным подразбитиемдиграфаD=(V,A) является диграфD’=(V,A’), получаемый изDзаменой каждой дуги двумя дугами с новой вершиной между ними ( новые дуги имеют то же направление, что и заменяемая дуга).
Определение
k-ой степенью диграфаD=(V,A) является диграф, с тем же множеством вершин и дугой между двумя вершинами тогда и только тогда, когда в диграфеDмежду ними существует направленный путь длины точноk.
2
Определения
.2.3. Бинарные операции
Объединением (disjoint union) диграфовD1=(V1,A1) иD2=(V2,A2) является диграф (или иной вид графа)D=(V,A),V=V1V2,A=A1A2.
Произведение диграфов (digraph product)D1=(V1,A1) иD2=(V2,A2) - диграф, у которого:
множество вершин равно V1V2(т.е. множество пар, где первый элемент взят из множества вершинV1. а второй – из множестваV2);
смежность дуг к и от полученной вершины определяется неоднозначно.
Определение
Некоторые из произведений двух диграфов определяются следующим образом:
Конъюнкцией (conjunction) D1D2двух диграфов D1=(V1,A1) и D2=(V2,A2) является диграф с множеством вершин V1V2, у которого имеется дуга из вершины (u1,u2) к вершине (v1,v2) тогда и только тогда, когда имеются дуга из вершины u1вершину v1диграфа D1и дуга из вершины u2в вершину v2диграфа D2 .
Круговым произведением (wreathproduct) D1¦D2 двух диграфов D1=(V1,A1) и D2=(V2,A2) является диграф с множеством вершин V1V2, у которого между парами вершин имеется дуга, если выполняются условия:
{(x1,y1),(x1,y2): {x1,y2} является дугой диграфаD1}
и
{(x1,y1),(x1,y2): {x2,y2} является дугой диграфаD2}.
Декартово произведение (Cartesian product)D1D2двух диграфов D1=(V1,A1) и D2=(V2,A2) является диграф с множеством вершин V1V2, у которого дуга начинаетD1D1ся на вершине (u1,u2) и заканчивается на вершине (v1,v2), если {u1,v1}A1, {u2,v2}A2иu1=v1,u2=v2.