Авторы: Тамара Волченская, Владимир Князьков | Вятский государственный университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
6:04:00
Студентов:
2741
Выпускников:
533
Качество курса:
4.31 | 3.94
Приводятся начальные сведения о графах, основные понятия и определения, способы представления графов. Рассматриваются основные операции над графами, такие как - объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание.
Даются понятия прямых и обратных отображений для орграфов различных порядков, прямого и обратного транзитивного замыкания, приводятся способы нахождения транзитивных замыканий по матрице смежности и обсуждаются вопросы достижимости для орграфов, способы нахождения матриц достижимости и контрдостижимости. Рассматриваются типы графов и подграфов, такие как -полный, симметрический, антисимметрический, двудольный, древовидный, планарный и их возможные комбинации. Дается теорема о двудольности графов. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, методы разбиения графов на сильно связные подграфы- метод Мальгранжа и матричный метод. Даются понятия веса и длины пути, сведения о орциклах и циклах и их особенностях. Рассматриваются метод Дейкстра нахождения кратчайших путей и методика построения базы для взвешенного графа.
Специальности: Программист, Математик
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
24 минуты
Графы и способы их представления
Приводятся начальные сведения о графах и основные понятия и определения такие как орграф, смешанный граф, дубликат графа дуга, петля, полустепени исхода и захода. Даются возможные способы представления графов. Цель лекции: Дать представление о графах и возможных способах их представления.
Оглавление
    -
    Лекция 2
    19 минут
    Операции над графами
    Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. Эти операции рассматриваются для представления графов матрицами смежности. Цель лекции: Дать представление об операциях над графами и возможных способах их представления в матричных структурах.
    Оглавление
      -
      Лекция 3
      19 минут
      Многозначные отображения и транзитивные замыкания
      Рассматриваются прямые и обратные отображения для орграфов различных порядков. Даются понятия прямого и обратного транзитивного замыкания и способы нахождения транзитивных замыканий по матрице смежности. Цель лекции: Дать представление о многозначных отображениях и транзитивных замыканиях и способах их нахождения.
      Оглавление
        -
        Лекция 4
        24 минуты
        Достижимость в графах
        Рассматриваются вопросы достижимости для орграфов и способы нахождения матриц достижимости и контрдостижимости. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, а также нахождение множества вершин, входящих в путь между парой вершин. Цель лекции: Дать представление о достижимости и контрдостижимости и способах их нахождения
        Оглавление
          -
          Лекция 5
          23 минуты
          Типы графов
          Рассматриваются типы графов такие как полный, симметрический, антисимметрический, двудольный, дерево, планарный и их возможные комбинации. Дается теорема о двудольности графов. Цель лекции: Дать представление о типах графов и их свойствах
          Оглавление
            -
            Тест 5
            21 минута
            -
            Лекция 6
            14 минут
            Виды подграфов
            Рассматриваются подграфы такие как остовный, порожденный и различные виды подграфов по связности. Цель лекции: Дать представление о видах подграфов и их свойствах.
            Оглавление
              -
              Тест 6
              24 минуты
              -
              Лекция 7
              30 минут
              Методы разбиения графа на максимальные сильно связные подграфы
              Рассматриваются методы разбиения графов на сильно связные подграфы: метод Мальгранжа и матричный метод. Цель лекции: Дать представление о методах разбиения графов на сильно связные подграфы.
              Оглавление
                -
                Лекция 8
                16 минут
                Пути и циклы в графах
                Рассматриваются взвешенные пути и маршруты в графах. Дается понятие веса и длины пути. Приводятся сведения о орциклах и циклах и их особенностях. Цель лекции: Дать представление о путях и циклах в графах и весе и длине пути.
                Оглавление
                  -
                  Тест 8
                  21 минута
                  -
                  Лекция 9
                  24 минуты
                  Алгоритм Дейкстра поиска кратчайших путей в графе
                  Рассматриваются метод Дейкстра нахождения кратчайших путей. Приводятся сведения о методике построения базы для взвешенного графа. Цель лекции: Дать представление о методе нахождения кратчайших путей во взвешенном графе.
                  Оглавление
                    -
                    1 час 40 минут
                    -
                    Dmitry Schelkov
                    Dmitry Schelkov

                    В лекции 3 часть номер 2 приведён пример нахождения транзитивного замыкания по матрице смежности. Из примера для обратного транзитивного замыкания видно, что путь для достижения вершины х6 в вершину х3 равен 3, а не 2, как показано в табличном примере. Мне кажется, что в лекции ошибка.

                    Вячеслав Коваленко
                    Вячеслав Коваленко

                    В курсе "Введение в теорию графов" в лекции 4 "Достижимость в графарх" дано выражение для нахождения множетсва вершин, входящих в путь из одной вершины графа в другую и по рис.4.2. показан пример нахождения такого множества для пути из вершины х2 в вершину х4 - это множетсво (х2, х3, х4, х5). По рисунку видно что путь не оптимален и для того, чтобы он проходил через все вершины этого множества, через х4 нужно пройти два раза. Правильно ли я понимаю, что данное определение пути дает не всегда оптимальный путь и что определение оптимально (кратчайшего) пути - отдельная задача? Или в примере ошибка?

                    Семен Дядькин
                    Семен Дядькин
                    Беларусь, Минск, БГУ, 2003
                    Илья Шапкин
                    Илья Шапкин
                    Россия, пгт Излучинск