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

  • Общее

    Свернуть всё Развернуть всё

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

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

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

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

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

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

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

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

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

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


  • Вопросы к экзамену

    1. Три определения графа. Пути и циклы на графе. Леммы о простых и элементарных путях и циклах.
    2. Изоморфизм графов. Проблема изоморфизма.
    3. Инварианты графа.
    4. Какрасы и разрезы графа.
    5. Пространства циклов и разрезов.
    6. Планарные графы. Теоремы о раскрасках планарного графа.
    7. Гипотеза Хадвигера.
    8. Хроматический многочлен графа.
    9. Хроматическое число.
    10. Ядра графа. Функция Гранди.
    11. Оценки спектрального радиуса.
    12. Собственные подпространства.
    13. Алгебраическая звязность графа.
    14. Задача о максимальном суммарном потоке в динамической периодической сети.
    15. Потоковая модель в сети с потребителями.
    16. Классификация ресурсных сетей.
    17. Пороговое значение эргодической ресурсной сети.
    18. Потоки и предельные состояния в ресурсных сетях.
    19. Аттракторы и их классификация.
    20. Ресурсные сети с ограничениями на ёмкость вершин.
    21. Обратные задачи в ресурсных сетях.

  • 1.1. Изоморфизм. Инварианты

    Контрольные вопросы:

    1. Являются ли следующие графы изоморфными?
      .
    2. Найдите инварианты \( \varphi(G), \varepsilon(G), \gamma(G), \varkappa(G) \)для графов \( G_1 \) и \( G_2 \)

  • 1.2. Цикломатика графа. Каркасы и разрезы. Пространства циклов и разрезов.

    Контрольные вопросы:

    1. Найдите минимальный разрез для следующего графа
      minCut
    2. Найдите базис пространства циклов графа
      Циклы. Базис

  • 1.3. Планарность. Гипотеза Хадвигера

    Контрольные вопросы:

    1. Что означает равенство В + Г - Р = 2?
    2. Докажите указанное равенство для дерева.
    3. Является ли следующий граф планарным? Правильно ли он реализован?

  • 1.4. Раскраски графа. Хроматический многочлен графа

    Контрольные вопросы:

    1. Сформулируйте гипотезу черырёх красок.
    2. Найдите хроматическое число и хроматический многочлен следующего графа

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

    Контрольные вопросы:

    1. Перечислите все внешне устойчивые множества графа \( G1 \) и все внутренне устойчивые множества графа \( G_2 \)
    2. Для следующего графа найдите ядро с наибольшим числом вершин

  • 2.1. Спектры графов. Оценки спектрального радиуса. Собственные подпространства

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

  • 3.2. Потоковая модель в сети с потребителями

  • 3.3. Ресурсные сети. Классификация ресурсных сетей по топологии. Аттракторы и их классификация.

  • 3.4. Пороговое значение. Потоки и предельные состояния в ресурсной сети

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

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


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

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

    1. Определите один из базисов пространства циклов.
    2. Найдите максимальную клику.
    3. Постройте хроматический многочлен.
    4. Определите, чему равны цикломатическое и хроматическое числа.
    5. Постройте ядро максимальной мощности.


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

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

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

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

    Вариант 1.

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


    Вариант 2.

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