mpei2004@yandex.ru

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



  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. Доминирующее множество. Число доминирования. Полностью зависимое и полностью независимое множество вершин. Число вершинной независимости. Реберная независимость. Теорема о связи независимости и доминирования. Клики.
  27. Реберный граф. Число ребер (с доказательством).
  28. Триангуляция.
  29. Алгоритм поиска совершенного паросочетания в двудольном графе

    30.  


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

Студенты, получившие за семестр более 150 баллов, освобождаются от ОДНОЙ задачи. Отличники (по зачету) имеют еще 2 балла, хорошисты - 1.