1. Построить конденсацию G* орграфа G.
2. Выделить в конденсации вершины с нулевой полустепенью исхода.
3. Из соответствующих сильных компонент выбрать произвольно по одной вершине.
В рассмотренном выше примере антибаза: B'={v8}.
ОБХОДЫ ОРГРАФА
Определения эйлеровых и гамильтоновых циклов орграфа сходны с аналогичными определениями для неориентированного графа.
Орцепь, содержащая каждую дугу орграфа, называется эйлеровой цепью.
Связный орграф называется эйлеровым графом, если он содержит замкнутую эйлерову цепь.
Теорема. Для связного орграфа G следующие утверждения эквивалентны:
1) орграф G - эйлеров;
2) для любой вершины v орграфа G справедливо следующее равенство:
v = 
v.
3) орграф G является объединением контуров, попарно не имеющих общих дуг.
Контур или замкнутый ормаршрут является гамильтоновым, если он содержит все вершины орграфа, и сам граф является гамильтоновым, если он содержит гамильтонов контур.
Теорема (достаточное условие гамильтоновости).
Пусть G – сильный орграф порядка p > 1 (без петель и кратных дуг). Тогда, если для любой пары его смежных вершин выполняется равенство
deg u + deg v £ 2p – 1, то в графе G есть гамильтонов контур.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Дать определение матрицы смежности и матрицы инцидентности орграфа.
2. Обратный орграф, основание, турнир.
3. Степени вершин орграфа.
4. Дать определение следующим понятиям: ормаршрут, цепь, путь, полумаршрут, полуцепь, полупуть, замкнутый маршрут, цикл, контур.
5. Матрицы достижимости, контрдостижимости и взаимодостижимости.
6. Типы связности орграфа, сильные компоненты.
7. Конденсация, база, антибаза. Алгоритмы построения.
8. Обходы орграфа.
ЗАДАНИЯ ДЛЯ ЛАБОРАТОРНЫХ РАБОТ
ЛАБОРАТОРНАЯ РАБОТА №1
Тема: « Подграфы. Изоморфизм».
Цель работы: изучение основных понятий теории графов, приобретение практических навыков определения изоморфизмов графа; построение подграфов, независимых множеств и клик.
Содержание работы:
1. Используя алгоритм генерации варианта GV, построить неориентированный граф G: GV(7,{2,3}).
2. Описать граф матрицей смежности, матрицей инцидентности. Изобразить графически граф G и его дополнение G̅. Построить произвольный остовный подграф и подграф, порожденный множеством вершин {1,2,5,6,7}.
3. Построить все помеченные 5-графы, изоморфно вложимые в граф G. Среди них определить классы изоморфных графов, построив биекцию их вершин. Для каждого класса изоморфных графов привести рисунок абстрактного графа.
4. Найти все максимальные и наибольшие независимые множества исходного графа. Определить число независимости.
5. Найти все максимальные и наибольшие клики данного графа. Определить плотность графа G.
6. Найти полный двудольный подграф Kp,q, изоморфно вложимый в граф G с максимальным количеством вершин p+q (p¹1).
7. Найти звезду K1,n, изоморфно вложимую в граф G, с максимальным значением n.
ЛАБОРАТОРНАЯ РАБОТА №2
Тема: « Маршруты и связность».
Цель работы: изучение понятий связных графов и маршрутов, приобретение практических навыков построения матрицы расстояний и нахождения матрицы кратчайших маршрутов.
Содержание работы:
1. Используя алгоритм генерации варианта GV, построить неориентированный граф G1: GV(13,{6,7}) и граф G2: GV(7,{2,3}). Ребра графа G2 взвешены соответствующими элементами матрицы Y.
2. Определить, является ли граф G1 связным.
3. Для максимальной компоненты графа G1 выделить:
a) открытый маршрут, не являющийся цепью;
b) замкнутый маршрут, не являющийся циклом;
c) цепь, не являющуюся простой цепью;
d) простую цепь;
e) цикл, не являющийся простым циклом;
f) простой цикл;
g) определить обхват и окружение;
h) найти вершинную и реберную связность.
4. Для каждой компоненты графа G1:
a) построить матрицу расстояний;
b) определить эксцентриситеты вершин, радиус, диаметр, центр, периферию;
c) выделить блоки;
d) найти точки сочленения и мосты.
5. В графе G2:
a) построить кратчайшие маршруты от произвольной вершины ко всем остальным при помощи алгоритма Дейкстры;
b) построить кратчайшие маршруты от произвольной вершины ко всем остальным при помощи алгоритма Форда;
c) построить кратчайшие маршруты при помощи алгоритма Флойда. При построении вести две матрицы – матрицу маршрутов и матрицу расстояний.
ЛАБОРАТОРНАЯ РАБОТА №3
Тема 1: « Деревья и остовы».
Цель работы: изучение понятий деревьев и остовов, приобретение практических навыков построения матрицы Кирхгофа и вычисления количества помеченных остовов.
Содержание работы:
1. Используя алгоритм генерации варианта GV, построить неориентированный граф G1: GV(5,{2,3}) и граф G2: GV(13,{6,7}). Ребра графа G2 взвешены соответствующими элементами матрицы Y.
2. Для графа G1 составить матрицу Кирхгофа и посчитать количество помеченных остовов.
3. Для графа G2:
a) построить дерево обхода вершин графа в ширину и в глубину;
b) решить задачу построения остовов кратчайших маршрутов, используя алгоритмы Прима и Краскала (в качестве весов ребер использовать элементы матрицы Y);
4. Сгенерировать все различные абстрактные не изоморфные друг другу деревья порядка 4 и 7. Разделить множество деревьев на два подмножества: с одной и двумя центральными вершинами.
Тема 2: «Циклы и обходы».
Цель работы: изучение понятий гамильтоновых и эйлеровых циклов, приобретение практических навыков построения матрицы циклов и матрицы фундаментальных циклов.
Содержание работы:
1. Используя алгоритм генерации варианта GV, построить неориентированный граф G1: GV(5,{2,3}) играф G2: GV(13,{6,7}).
2. Для произвольного остова графа G1 построить матрицу фундаментальных циклов. Посчитать циклический и коциклический ранг, выразить 3 непростых цикла (если таковые имеются) через минимальную комбинацию базисных.
3. Определить, являются ли графы G1 и G2 эйлеровыми, построить эйлеровы циклы по алгоритму Флёри, эйлеровы цепи. Если граф не эйлеров, добавить минимальное число ребер, делающих его эйлеровым.
4. Определить, является ли граф G2 гамильтоновым, построить гамильтонов цикл, используя алгоритм Робертса-Флореса. Если граф не является гамильтоновым, то добавить минимальное число ребер, делающих его гамильтоновым.
ЛАБОРАТОРНАЯ РАБОТА №4
Тема: «Ориентированные графы».
Цель работы: изучение основных понятий ориентированных графов, приобретение практических навыков построения матрицы смежности, матрицы инцидентности; определение типов связности орграфа; построение конденсации орграфа.
Содержание работы:
1. Использую алгоритм генерации варианта GV1, построить ориентированный граф G: GV1(9,{6,7}).
2. Построить матрицу смежности и матрицу инцидентности заданного орграфа.
3. Построить основание и обратный граф. Определить, является ли граф симметричным.
4. Построить ормаршрут, цепь, путь, полумаршрут, полуцепь, полупуть, замкнутый маршрут, цикл и контур.
5. Построить матрицу достижимости, контрдостижимости, взаимной достижимости. Представить ограниченно достижимую матрицу для числа достижимости, равного 2.
6. Определить тип связности орграфа, выделить сильные компоненты.
7. Построить конденсацию. Определить базы и антибазы.
Алгоритмы генерации вариантов
GV(p,x): A[1..p,1..p], где
p – количество вершин в графе;
x – параметр генерации варианта;
A – матрица смежности графа.
Алгоритм генерации варианта GV(p,x): A[1..p,1..p]:
Статический локальный параметр S = <фамилия> <имя> <отчество>.
Функция n(c) - номер буквы в алфавите (1..33).
1. Вычеркнуть из S все повторные вхождения букв.
2. Построить Y = ║yij║, i,j = 1̅,p̅, где
yij = │n(Si)-n(Sj)│
3. Построить A = ║aij║, i,j = 1̅,p̅:
если i=j, то aij=0, иначе:
4. Для каждой изолированной (доминирующей) вершины добавить (удалить) одно ребро. Добавляемое (удаляемое) ребро связывает текущую вершину со следующей (по номеру). Для последней вершины следующей считать первую вершину.
Алгоритм генерации варианта GV1(p,x): A[1..p,1..p]:
Статический локальный параметр S = <фамилия> <имя> <отчество>.
Функция n(c) - номер буквы в алфавите (1..33).
1. Вычеркнуть из S все повторные вхождения букв.
2. Построить Y = ║yij║, i,j = 1̅,p̅, где верхний треугольник матрицы заполняется по формуле yij = │n(Si)-n(Sj)│, а нижний - yij = n(Si)+n(Sj).
3. Построить A = ║aij║, i,j = 1̅,p̅,:
если i=j, то aij=0, иначе:
