Группы: мк-301, мт-301



Скачать 24.79 Kb.
Дата11.10.2012
Размер24.79 Kb.
ТипДокументы
Дисциплина: дискретная математика, теория графов
Группы: МК-301, МТ-301
Форма аттестации: зачет

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

Похожие:

Группы: мк-301, мт-301 iconУдлинитель 3 гнезда 10 м 50-301

Группы: мк-301, мт-301 iconТехническое задание модернизация охранной сигнализации (ОС) нву вентшахт №04, 201,219, 301, 315, 319, 323, 407, 412, 619 Общие сведения
Предмет выполнения работ: модернизация охранной сигнализации (ОС) нву вентшахт №04, 201, 219, 301, 315, 319, 323, 407, 412, 619
Группы: мк-301, мт-301 iconКурсовая работа по литературе стран изучаемого языка студентки III курса факультета международных отношений группы л-301
Смерть Байрона вызвала на континенте в либеральной части общества чувство печали и была оплакана Гёте (во II ч. "Фауста" в образе...
Группы: мк-301, мт-301 iconНаселение 2 301,4 тыс чел Площадь
Распространенность вич-инфекции и спид среди граждан Украины на 01. 01. 2010 р
Группы: мк-301, мт-301 iconЛаверна-Холдинг групп
Промкомзона, Производственный проезд, 45, оф. 207 К/ с 301 018 106 000 000 00821
Группы: мк-301, мт-301 iconУдк 519. 248: [004. 8+33+301+159. 9] Эвентологическая формализация лингвистической переменной
Такая теория была предложена известным американским математиком Л. Заде в 1965г [1]
Группы: мк-301, мт-301 iconА. Переверзева история армянской церкви
Армянская апостольская церковь является одной из древнейших христианских церквей. Христианство появилось в Армении во II – III вв.,...
Группы: мк-301, мт-301 iconПросмотр работ участников олимпиады и апелляция 26 декабря, в 9-30, ауд. 301. Награждение победителей в 10-30
Математическая олимпиада Омгу носит имя профессора Г. П. Кукина, создателя системы городских математических олимпиад
Группы: мк-301, мт-301 iconСреднюю общеобразовательную школу №301 Фрунзенского района
...
Группы: мк-301, мт-301 iconПамятка для туристов географическое положение
Апеннинском полуострове, островах Сицилии, Сардинии, Искья, Капри и других. Площадь 301,3 тыс кв км. Граничит на севере со Швейцарией...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org