- •1(18).Основное понятие теории графов. Определения и разновидности графов. Способы задания графов: аналитический, геометрический, матричный. Изоморфизм графов. Примеры.
- •2(19). Операции над графами с примерами.
- •3(20) Маршруты. Цепи. Циклы.
- •4(21) Метрические характеристики графа
- •5(22) Понятие сети. Матрица весов.
- •6(23) Алгоритм Беллмана-Мура (алгоритм корректировки меток)
- •7(24). Деревья и их свойства. Лес.
- •8(25). Задача об остове экстремального веса.
- •9(26) Эйлеровы графы и циклы. Алгоритм Флерн. Гальмитоновые графы и циклы
- •10(27) Планарные графы. Укладка графа. Теорема Эйлера. Теорема Понтрягина-Куратовского. Понятие искаженности и толщины непланарных графов
- •11(28) Алгоритм плоской укладки
- •2 Итерация
- •12(29). Раскраски графов
- •13(30)Потоки в сетях.
- •14(31) Потоки минимальной стоимости.
- •15(32)Элементы теории кодирования. Кодирование как способ представления информации.
- •16(33) Общий критерий взаимной однозначности. Теорема Маркова. Примеры
- •17(34) Неравенство Макмиллана.
- •18(35) Коды с минимальной избыточностью. Примеры.
- •19(36). Оптимальное кодирование Хаффмана. Решение задачи о построении кодов с минимальной избыточностью для двоичного кодирования.
- •20(37) Самокорректирующиеся коды. Коды Хэмминга. Алгоритм построения кода Хэмминга
- •21(38) Обнаружение ошибки в кодах Хемминга.
4(21) Метрические характеристики графа
Опр Длины кратч-го из v1 в v2 – растояние между вершинами v1 и v2
Обозначение d(v1,v2)
Очевидно,что расстояние между вершинами явл-я простой цепью.d(vi,vj)=0
Опр Для любой вершины v e(v)=max d(v,u) u€V – эксцентр-т вершины
Опр Максим-й из всех эксцен-в графа – диаметр графа d(G),т.е D(G)=max e(v)v€V
Опр Мин из эксц-в вершин графа – радиус
R(G)=min e(v)
Вер v – пер-й,если её эксц-т вер равен диаметру графа.
Опр Простая цепь-расстояние междду концами которой равно диаметру графа-диаметральная цепь.
Опр Вер v – центральной,если её эксц-т равен радиусу графа,т.е e(v)=r(G)
Опр Мн-во всех центр-х вершин графа-центр
Центр графа может быть единственной верш-й или несколько вер.
Теор.Для любого связного графа G вып-я d(G) ≤rang G
Док-во Пусть d(G) =d и v1,v2,….,v d+1 – одна из диаметральных цепей
Перенумеруем вершины графа таким образом,чтобы вершины имели собственно номера 1,2…d+1
Диаметр цепь-подграф графа G штрих графа G
Согласно нумерации вершин графа G матрица смежности вершин P(G’) явл-я подматрицей матрицы смежности P(G) графа G ,расположенной на пересечении строк и столбцов
P(G)= (P(G’) А
B C)
P(G’) = (01000
10100
01000
………..
00001
00010)
G’ – простая цепь,т.е матрица симметричная порядка d+1, все элементы которой за исключением 2 ближайщихх к главной диагонали полос равны 0
Опр Ранг матрицы – наивысший из порядков её ненулевых миноров
Рассмотрим миноры порядка d матрицы P от G’ ,получ-й вычёркиванием первого столбца и последней строки
Этот минор =1(определитель соотв-й мат). Получили,что P(G’) имеет ненулевой минор порядка d,значит rang P(G’)≥d следует rang(G)= rang P(G)≥rang P(G’)≥d-d(G)
D(G)≤rangG
5(22) Понятие сети. Матрица весов.
Опр. Пусть G=(V,A) – орграф. Если каждой дуге поставить в соответствие некоторое число , то G называется графом со взвешенными дугами, или сетью. При этом вершины графа называются узлами сети. Число называется весом дуги
Опр. Весом пути μ сети G называется число где μ – путь из вершины в
Сеть может быть представлена своей матрицей весов , где – вес соответствующего ребра
Веса несуществующих ребер полагают равными нулю (или бесконечности)
Алгоритм Дейкстры. (решение задачи о нахождении кратчайшего пути)
Пусть G=(V,A) – сеть, s – вершиной начала пути, t – конец пути.
В процессе работы этого алгоритма узлами сети приписываются числа (метки) , которые служат оценкой длины (веса) от s к . Если получила на некотором шаге метку , это означает что в графе G существует путь из s в , имеющий вес . Метки могут быть временными или постоянными. Если метка становится постоянной – значит, что кратчайший путь от s до найдено. Ограничение на применение алгоритма Дейкстры: веса дуг должны быть положительными.
Алгоритм состоит из двух этапов:
Нахождение длины кратчайшего пути
Шаг 1: Присвоение вершинам начальных меток.
Полагаем, что , и считаем эту метку постоянной. Для остальных вершин положим , и считаем эти метки временными. Пусть
Шаг 2: Изменение меток: для каждой вершины с временной меткой, непосредственно следующей за меняем метку в соответствии с правилом:
Шаг 3: превращение метки из временной в постоянную.
Из всех вершин с временными метками выбираем вершину с наименьшим значением метки. Превращаем эту метку в постоянную:
Шаг 4: Проверка на завершение первого этапа. Если , то – длина кратчайшего пути от s к t. Иначе возвращаемся к Шагу 2.
Строим сам путь от s к t
Шаг 5: последовательный поиск дуг кратчайшего пути. Среди вершин, непосредственно предшествующих с постоянными метками, находим , удовлетворяющую соотношению . Если это так, что включаем в искомый путь, и полагаем, что
Шаг 6: проверка на завершение второго этапа. Если , то кратчайший путь найден. В противном случае возвращаемся на Шаг 5