Автор: Борис Бояршинов | Московский государственный гуманитарный университет имени М.А. Шолохова
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Для всех
Длительность:
0:03:00
Студентов:
628
Выпускников:
1
Практикум по решению задач по теории графов и связанным с ними алгоритмам.
Даются основные понятия теории графов, решаются оптимизационные задачи на графах, рассказывается об алгоритмах поиска и матричных методах анализа графов.
Специальности: Программист, Математик
 

План занятий

Занятие
Заголовок <<
Дата изучения
Логика предикатов. Графы, общие определения
Кванторы всеобщности и существования. Связанные переменные. Область действия квантора. Эквивалентные соотношения в логике предикатов. Чистая логика предикатов и прикладные логики предикатов. Понятия графа. Классификация графов: по наличию ориентирования ребер (неориентированный и ориентированный графы), по наличию кратности ребер (простой граф и мультиграф). Отношение смежности между вершинами, матрица смежности. Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины. Пустой граф, полный граф.
Оглавление
    -
    Теория графов. Основные понятия
    Матрица смежности, степень вершины. Подграф и часть графа. Звезда вершины графа. Полный граф. Клика. Максимальный и минимальный (относительно некторого свойства) подграф. Изоморфизм графов. Неориентированные графы. Путь, цепь, простая цепь, цикл. Связанные вершины. Связный граф. Компоненты связности. Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния).
    Оглавление
      -
      Теория графов. Основные понятия (продолжение)
      Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах. Алгоритм построения эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера). Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость. Виды связности: сильная связность, односторонняя связность, слабая связность. Компонента сильной связности. Конденсация, граф конденсации. Ациклический граф. Источники и стоки. Топологическая сортировка.
      Оглавление
        -
        Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути
        Неориентированные деревья. Ориентированные деревья. Применение деревьев: классификация, представление формул, бинарное дерево поиска. Оптимизационные задачи на графах. Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов. Ранжирование вершин. Задача о кратчайшем пути в взвешенном графе. Алгоритм Дейкстры.
        Оглавление
          -
          Оптимизационные задачи на графах. Сетевое планирование. Потоки в сетях
          Сетевой график. Задача поиска максимальных путей в графе. Понятия раннего срока и позднего срока. Критический путь. Виды резерва: полный резерв, свободный резерв, независимый резерв. Потоки в сетях. Понятие потока, величина потока. Закон Кирхгофа. Увеличивающаяся цепь.
          Оглавление
            -
            Оптимизационные задачи на графах. Алгоритм поиска увеличивающей цепи
            Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.
            Оглавление
              -
              Матричные методы анализа графов. Графы и бинарные отношения
              Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения. Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мультиграфов. Двудольные графы. Задача о раскраске графа.
              Оглавление
                -
                Зарема Батчаева
                Зарема Батчаева

                Здравствуйте! Записалась на курс "Практикум по теории графов", не могу просмотреть лекции, пишут, что устарел  Адоб Флеш Плеер.

                Что мне делать?

                Борис Никитин
                Борис Никитин

                Записался на курс "Практикум по теории графов".

                А лекции по "Дискретной математике"

                И читает не Бояршинов, а Кузнецов.

                Почему ?

                Артем Тихомиров
                Артем Тихомиров
                Россия, г. Москва
                Ольга Ханина
                Ольга Ханина
                Россия, г. Шадринск