Home

Information

Тест (личная):

Graphs and Algorithms

: Information
[-]
Created: 26.09.2006 | Level: specialist | Access: free | University: Нижегородский государственный университет им. Н.И.Лобачевского
Graphs and Algorithms Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.
Основной принцип отбора и организации материала состоял в том, что каждый рассматриваемый пример должен нести определенную идейную нагрузку, знакомить слушателя с одним из важных изобретений или открытий в алгоритмической области. При этом предпочтение отдавалось не самым последним или рекордным алгоритмам, а более простым для понимания и убедительно демонстрирующим ту или иную идею. Для большинства рассматриваемых алгоритмов даются доказательства их правильности (т.е. того, что алгоритм действительно решает поставленную задачу) и оценок трудоемкости. Умение достаточно строго обосновывать алгоритмы и оценивать их трудоемкость является существенной частью квалификации алгоритмиста. Материал первой части может быть использован и в общем курсе дискретной математики.
| | Share |

План занятий

LessonTitle <<Date
-
Lecture 1
1 hour 17 minutes
Начальные понятия теории графов
Начальные понятия теории графов. Определение графа. Графы и бинарные отношения. Откуда берутся графы. Число графов. Смежность, инцидентность, степени. Некоторые специальные графы. Графы и матрицы. Взвешенные графы. Изоморфизм. Инварианты. Операции над графами. Локальные операции. Подграфы. Алгебраические операции.
Contents
    		-
    Тест 1
    12 minutes
    		 -
    Lecture 2
    43 minutes
    Маршруты, связность, расстояния
    Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики графов. Маршруты и связность в орграфах. Эйлеровы пути и циклы.
    Contents
      		-
      Тест 2
      12 minutes
      		 -
      Lecture 3
      1 hour 5 minutes
      Важнейшие классы графов
      Деревья. Центр дерева. Корневые деревья. Каркасы. Двудольные графы. Планарные графы.
      Contents
        		-
        Тест 3
        15 minutes
        		 -
        Lecture 4
        38 minutes
        Поиск в ширину
        Поиск в ширину. Процедура поиска в ширину. BFS-дерево и вычисление расстояний.
        Contents
          		-
          Тест 4
          9 minutes
          		 -
          Lecture 5
          43 minutes
          Поиск в глубину
          Процедура поиска в глубину. DFS-дерево. Глубинная нумерация. Построение каркаса. Шарниры.
          Contents
            		-
            Тест 5
            9 minutes
            		 -
            Lecture 6
            45 minutes
            Блоки
            Блоки. Двусвязность. Блоки и BC-дерево. Выявление блоков.
            Contents
              		-
              Lecture 7
              44 minutes
              Пространство циклов графа
              Пространство подграфов. Квазициклы. Фундаментальные циклы. Построение базы циклов. Рационализация.
              Contents
                		-
                Тест 6
                15 minutes
                		 -
                Lecture 8
                38 minutes
                Эйлеровы и гамильтоновы циклы
                Построение эйлерова цикла. Гамильтоновы пути и циклы.
                Contents
                  		-
                  Lecture 9
                  49 minutes
                  Независимые множества, клики, вершинные покрытия.
                  Независимые множества, клики, вершинные покрытия . Три задачи. Стратегия перебора для задачи о независимом множестве. Эвристики для задачи о независимом множестве. Приближенный алгоритм для задачи о вершинном покрытии. Перебор максимальных независимых множеств.
                  Contents
                    		-
                    Тест 7
                    15 minutes
                    		 -
                    Lecture 10
                    35 minutes
                    Раскраски
                    Раскраска вершин. Переборный алгоритм для раскраски. Раскраска ребер.
                    Contents
                      		-
                      Lecture 11
                      35 minutes
                      Рационализация переборных алгоритмов
                      Рационализация поиска наибольшего независимого множества. Хордальные графы. Рационализация алгоритма для задачи о раскраске вершин.
                      Contents
                        		-
                        Тест 8
                        12 minutes
                        		 -
                        Lecture 12
                        57 minutes
                        Паросочетания
                        Паросочетания и реберные покрытия. Метод увеличивающих путей. Паросочетания в двудольных графах. Паросочетания в произвольных графах (алгоритм Эдмондса).
                        Contents
                          		-
                          Lecture 13
                          28 minutes
                          Оптимальные каркасы
                          Задача об оптимальном каркасе. Алгоритм Прима. Алгоритм Крускала.
                          Contents
                            		-
                            Тест 9
                            15 minutes
                            		 -
                            Lecture 14
                            40 minutes
                            Жадные алгоритмы и матроиды
                            Матроиды. Теорема Радо-Эдмондса. Взвешенные паросочетания.
                            Contents
                              		-
                              Lecture 15
                              21 minute
                              Кратчайшие пути
                              В этой лекции рассматриваются связные графы с неотрицательными весами ребер. А также кратчайшие пути, геодезическое дерево и алгоритм Дейкстры.
                              Contents
                                		-
                                Lecture 16
                                35 minutes
                                Потоки
                                В этой лекции будем рассматривать ориентированные графы без петель и кратных ребер: задачу о максимальном потоке и метод увеличивающих путей.
                                Contents
                                  		-
                                  Тест 10
                                  18 minutes
                                  		 -
                                  5 hours
                                  		 -