Автор: Нина Костюкова | Новосибирский Государственный Университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Для всех
Длительность:
11:03:00
Студентов:
3055
Выпускников:
527
Качество курса:
4.21 | 3.83
В курсе излагаются основные понятия теории графов. Описаны методы решения задач.
Материал организован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется увидеть возможность перевести условие на язык графов, решить задачу внутри теории графов, интерпретировать получение решение в исходных терминах. Если в начале курса рассматриваются приложения частного характера, иллюстрирующие теорию графов и ее связь с жизнью, то вторая половина книги посвящена прикладным разделам теории графов, имеющим практическое значение в экономике и управлении.
Специальности: Программист, Математик
ISBN: 978-5-9556-0069-7
 

План занятий

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

                                  Оглавление
                                    -
                                    1 час 40 минут
                                    -
                                    Никита Толышев
                                    Никита Толышев
                                    Владислав Нагорный
                                    Владислав Нагорный

                                    Подскажите, пожалуйста, планируете ли вы возобновление программ высшего образования? Если да, есть ли какие-то примерные сроки?

                                    Спасибо!