Тематический план

  • Содержание учебного материала

    Раздел 1. Изоморфизм. Цикломатика. Раскраски

    Изоморизм графов. Инварианты графа. Проблема изоморфизма.

    Цикломатика графа. Каркасы и разрезы. Пространства циклов и разрезов. Планарность. Гипотеза Хадвигера.

    Раскраски графа. Хроматический многочлен графа. с Внутренне и внешне устойчивые множества. Ядра графа. Функция Гранди.

    Раздел 2. Спектры графов

    Спектры графа. Оценки спектрального радиусов графов. Спектры графов. Оценки спектрального радиуса. Собственные подпространства. Связь спектра и структуры графа. Приложения спектральной теории графов в математике, физике, химии.

    Раздел 3. Динамические графовые модели

    Потоковые модели в динамических сетях. Задача о максимальном суммарном потоке в динамической периодической сети. Потоковая модель в сети с потребителями.

    Ресурсные сети. Классификация ресурсных сетей по топологии. Пороговое значение. Потоки и предельные состояния в ресурсной сети. Аттракторы и их классификация.


    • Контрольные работы

      Примерные задания (по разделам)


      Контрольная работа №1 (раздел 1, 15 баллов)

      Для представленного на рисунке графа

      1. Определите один из базисов пространства циклов.

      2. Найдите максимальную клику.

      3. Постройте хроматический многочлен.

      4. Определите, чему равны цикломатическое и хроматическое числа.

      5.Постройте ядро максимальной мощности.

       

      Контрольная работа № 2 (раздел 2, 15 баллов)

      1. Граф G1 задан своей матрицей смежности А. Определите его спектральный радиус.

      2. Граф G1' получен из G1 стягиванием дуги (1,2). Определите спектральный радиус графа G1'.

      3.  Граф G2 представлен на рисунке. Найдите величину его алгебраической связности.

      4. Найдите собственное подпространство для алгебраической связности произведения графов G1G2.


      • Индивидуальное задание

        Вариант 1.
        1. Для графа вычислить суммарный поток за 7 тактов
        2. Для сети из первого задания рассчитать максимально возможную суммарную величину потребления. Указать частный случай распределения потока при котором она достигается.
        3. Для ресурсной сети найти пороговое значение и предельное состояние для следующего начального Q(0)=(50,0,0,0,0,0,0,0,0,0).

        Вариант 2.
        1. Для графа вычислить суммарный поток за 7 тактов
        2. Для сети из первого задания рассчитать максимально возможную суммарную величину потребления. Указать частный случай распределения потока при котором она достигается.
        3. Для ресурсной сети найти пороговое значение и предельное состояние для следующего начального Q(0)=(40,0,0,0,0,0,0,0,0,0).