mpei2004@yandex.ru

Вопросы к экзамену по дискретной математике.
Вопросы к экзамену по дискретной математике
МЭИ, экзамен 28.5.2012



  1. Лемма о рукопожатиях, следствия. Число ребер в полном графе.
  2. Матрица смежности, матрица Кирхгофа и ее свойства, список ребер, матрица инцидентности. Связность.
  3. Теорема о двухсторонней оценке числа ребер в обыкновенном графе.
  4. Спектр графа, регулярный граф. Дополнение графа.
  5. Центр графа.
  6. Теорема о числе маршрутов определенной длины в графе.
  7. Теорема о числе ребер в обыкновенном связном графе. Теорема о числе ребер в произвольном графе.
  8. Теорема об алгебраических дополнениях в матрице Кирхгофа. Число остовов.
  9. Кодировка дерева. Двоичная кодировка.
  10. Число остовов в полном графе (с доказательством) и теорема Кэли.
  11. Дерево. Листья. Лес. Ярус. Ствол. Высота. Код Прюфера.
  12. Сеть. Алгоритм Форда-Фалкерсона.
  13. Двудольный граф. Покрытие. Максимальное и наибольшее покрытие. Перманент.
  14. Задача о назначениях. Венгерский алгоритм.
  15. Кратчайший путь в орграфе. Алгоритм Дейкстры.
  16. Остов минимального веса. Два алгоритма решения задачи.
  17. Планарность. Плоский граф. Жорданова кривая. Подразбиение. Гомеоморфность. Теорема Понтрягина-Куратовского.
  18. Теорема Эйлера о плоском графе.
  19. Раскраски. Хроматический индекс и хроматическое число. Оценки. Теорема о редукции (с доказательством).
  20. Связность. Разрез, мост.
  21. Центроид. Теорема Жордана о центре и центроиде.
  22. Основание графа. Сильно связный граф. Евклидов граф.
  23. Гамильтоновы графы.
  24. Доминирующее множество. Число доминирования. Полностью зависимое и полностью независимое множество вершин. Число вершинной независимости. Реберная независимость. Теорема о связи независимости и доминирования. Клики.
  25. Реберный граф. Число ребер (с доказательством).
  26. Триангуляция.

     


Экзаменационный билет содержит 6 вопросов ( по 1 баллу), и 2 задачи или задача и вопрос с доказательством (по два балла). На "отл" необходимо набрать 10 баллов, "хор" -9 или 8, "уд" -7 или 6.