Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
В курсе излагаются основные понятия теории графов. Описаны методы решения задач.
Материал организован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется увидеть возможность перевести условие на язык графов, решить задачу внутри теории графов, интерпретировать получение решение в исходных терминах. Если в начале курса рассматриваются приложения частного характера, иллюстрирующие теорию графов и ее связь с жизнью, то вторая половина книги посвящена прикладным разделам теории графов, имеющим практическое значение в экономике и управлении.
Цель: Курс предназначен для лиц, желающих расширить свои знания и умения в области программирования.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
37 минут
Основные понятия теории графов
Определение графа. Определение орграфа. Полный граф. Полный ориентированный граф. Двудольный граф. Степень вершины. Связность графа. Задачи, приводящие к графам
Оглавление
    -
    Тест 1
    9 минут
    -
    Лекция 2
    33 минуты
    Некоторые определения теории графов
    Определения и примеры. Удаление ребер, мосты. Деревья. Перечисление деревьев.
    Оглавление
      -
      Тест 2
      9 минут
      -
      Лекция 3
      27 минут
      Представления о планарном графе
      Плоский граф. Гомеоморфные графы. Формула Эйлера. Триангулированный граф. Задачи.
      Оглавление
        -
        Тест 3
        9 минут
        -
        Лекция 4
        36 минут
        Эйлеровы графы
        Эйлеровы графы. Лабиринты. Геометрическая постановка задачи о лабиринтах. Решение задачи о лабиринтах.
        Оглавление
          -
          Тест 4
          9 минут
          -
          Лекция 5
          24 минуты
          Гамильтоновы графы
          Гамильтоновы графы. Теорема Дирака.
          Оглавление
            -
            Тест 5
            9 минут
            -
            Лекция 6
            28 минут
            Бесконечные графы
            Бесконечные графы. Краткий обзор свойств бесконечных эйлеровых графов.
            Оглавление
              -
              Тест 6
              9 минут
              -
              Лекция 7
              39 минут
              Графы с цветными ребрами
              Реберная раскраска. Задачи на графы с цветными ребрами и вытекающие из них свойства. Задача о несцепленных треугольниках с одноцветными сторонами.
              Оглавление
                -
                Тест 7
                9 минут
                -
                Лекция 8
                25 минут
                Раскрашивание графов
                Хроматическое число. Гипотеза о четырех красках. Раскрашивание карт.
                Оглавление
                  -
                  Тест 8
                  9 минут
                  -
                  Лекция 9
                  39 минут
                  Орграфы
                  Определения. Эйлеровы и гамильтоновы орграфы. Турниры.
                  Оглавление
                    -
                    Тест 9
                    9 минут
                    -
                    Лекция 10
                    40 минут
                    Цепи Маркова
                    Еще раз об ориентированных графах. Задачи на круговые бескомпромиссные турниры. Цепи Маркова.
                    Оглавление
                      -
                      Тест 10
                      9 минут
                      -
                      Лекция 11
                      31 минута
                      О деревьях
                      Представления деревьев. Представление с помощью матрицы смежности. Представление с помощью списков смежности. Представление с помощью списка ребер и кода Прюфера. Алгоритм построения кода Прюфера. Алгоритм раскодирования. Уровневые коды корневых деревьев. Перечисление и подсчет деревьев. Непомеченные деревья. Ориентированные деревья. Каркасы в неориентированном графе. Каркасы в ориентированных графах.
                      Оглавление
                        -
                        Тест 11
                        9 минут
                        -
                        Лекция 12
                        20 минут
                        Каркасы и изоморфизм деревьев
                        Каркас неориентированного графа. Нахождение каркасов в графе. Алгоритм Краскала. Изоморфизм деревьев.
                        Оглавление
                          -
                          Тест 12
                          9 минут
                          -
                          Лекция 13
                          10 минут
                          Деревья, вероятность и генетика
                          Поиск кратчайшего пути. Вероятность и генетика.
                          Оглавление
                            -
                            Тест 13
                            9 минут
                            -
                            Лекция 14
                            40 минут
                            Сетевое планирование и управление
                            Введение. Сетевой график. Правила построения сетевого графика. Анализ сетевой модели. Определение критического пути. Определение полного резерва времени ненапряженного пути. Формирование временных оценок работ.
                            Оглавление
                              -
                              Тест 14
                              9 минут
                              -
                              Лекция 15
                              22 минуты
                              Паросочетания и свадьбы
                              Паросочетания и свадьбы. Теорема Холла о свадьбах. Приложение теоремы Холла. Латинские квадраты.
                              Оглавление
                                -
                                Тест 15
                                9 минут
                                -
                                Лекция 16
                                33 минуты
                                Теория трансверсалей
                                Теория трансверсалей. Приложение теории трансверсалей.
                                Оглавление
                                  -
                                  Тест 16
                                  9 минут
                                  -
                                  Лекция 17
                                  26 минут
                                  Потоки в сетях
                                  Оглавление
                                    -
                                    Тест 17
                                    9 минут
                                    -
                                    5 часов
                                    -