Программа дисциплины «Теория графов»
Скачать 250.75 Kb.
|
8Образовательные технологииРазбор примеров и практических задач. 8.1Методические рекомендации преподавателюНет. 8.2Методические указания студентамНет. 9Оценочные средства для текущего контроля и аттестации студента9.1Тематика заданий текущего контроляДомашняя контрольной работа no. 1. Тема: комбинаторика. Примерные вопросы: 1. Сколько существует 100-разрядных десятичных чисел, в каждом из которых цифра 2 встречается 28 раз? 2. Найти количество целых положительных чисел, не превосходящих 9999 и не делящихся ни на одно из чисел 6, 15 и 70. 3. Последовательность a1, a2, a3, … обладает свойствами: a1=1, a2=2 и an+2 -4an+1 +3an=0 при всех n. Найти формулу, выражающую an через n. Домашняя контрольной работа no. 2. Тема: теория графов и теория сетей. Примерные вопросы: 1. Является ли данный граф (он явно указывается) уникурсальным. Ответ обосновать. Если ответ положительный, то указать в этом графе маршрут, содержащий каждое ребро ровно один раз. 2. Найти максимальный поток и минимальный разрез в следующей сети (сеть явно указывается). 3. Выясните тип топологической поверхности, полученной указанным отождествлением Заданной совокупности топологических многоугольников (она явно указывается). Вопросы для оценки качества освоения дисциплины 1. Дать определения перестановок из n по r без повторений и с повторениями. Привести примеры. Вывести формулы для их числа. 2. Дать определения сочетаний из n по r без повторений. Привести примеры. Вывести формулу для их числа. 3. Дать определения сочетаний из n по r с повторениями. Привести примеры. Вывести формулу для их числа. 4. Доказать формулу бинома Ньютона. Дать определение биномиальных коэффициентов и доказать простейшие тождества между ними. 5. Доказать формулу включения и исключения. Привести пример ее применения. 6. Рассказать как решается задача о беспорядках (о шляпах). 7. Дать определение линейной рекуррентной последовательности. Привести пример. Описать способ получения формулы для ее n-го члена. Привести пример нахождения такой формулы в каком-нибудь конкретном случае. Вывести формула n-го члена ряда Фибоначчи. 8. Дать определение чисел Каталана и вывести формулу для n–го числа Каталана. 8. Проиллюстрировать на примерах понятия графа, степени вершины графа, цикла в графе, связного графа, маршрута в графе, цикла, полного графа с n вершинами Kn, полного двудольного графа Kn,m. Дать определение изоморфных графов. Привести примеры изоморфных и неизоморфных графов. Может ли сумма степеней всех вершин графа быть равна 2009? 9. Дать определения эйлерова графа, эйлерова цикла. Доказать критерий эйлеровости графа. Привести пример нахождения эйлерова цикла в эйлеровом графе. 10. Дать определение гамильтонова графа, гамильтонова цикла. Привести примеры гамильтонова и негамильтонова графов. 11. Доказать теорему Эйлера о числе вершин, ребер и граней связного плоского графа. 12. Дать определение правильного выпуклого многогранника. Вывести из теоремы Эйлера о числе вершин, ребер и граней связного плоского графа про возможное число вершин, ребер и граней правильного выпуклого многогранника. 13. Доказать неравенство между числом Р и числом 3В-6 у связного плоского графа. Объяснить как из него вытекает непланарность полного графа с 5 вершинами (т.е. графа К5). 14. . Доказать неравенство между числом Р и числом 2В-4 у связного плоского графа. Объяснить как из него вытекает непланарность графа К3,3. 15. Дать определение гомеоморфных графов. Привести примеры гомеоморфных и негомеоморфных графов. Сформулировать критерий планарности (теорему Понтрягина--Куратовского). Привести пример применения этого критерия для какого-либо конкретного графа. 16. Доказать теорему Кенига. Дать определение рода графа. Какой род имеют графы К5 и К3,3? Обосновать ответ. 17. Дать определение топологической замкнутой поверхности без края. Дать определение ориентируемой и неориентируемой поверхности, привести примеры. Сформулировать теорему о классификации топологических замкнутых поверхностей без края. Зависит ли число В-Р+Г от выбора связного графа без самопересечений на поверхности (подкрепить ответ примером)? Какое дополнительное условие нужно наложить на рассматриваемые графы, чтобы ответ на предыдущий вопрос был отрицательным? Дать определение эйлеровой характеристики топологической поверхности. Доказать теорему о его корректности. 18. Вычислить эйлерову характеристику поверхностей Sg (сферы с g ручками) и Np. 19. Каким неравенством связаны число В-Р-Г для любого связного графа без самопересечений на топологический поверхности и эйлерова характеристики этой поверхности? Доказать его. 20. Каково минимальное число g, такое что полный граф Кs с s вершинами укладывается без самопересечений на сферу с g ручками ? Доказать соответствующее неравенство.Укажите явно укладку без самопересечений графа K5 на тор. 21. Каково минимальное число g, такое что граф Кn,m укладывается без самопересечений на сферу с g ручками ? Доказать соответствующее неравенство. 22. Расскажите о задаче о раскраске карт. Указать формулу для минимального числа красок, с помощью которых можно правильно раскрасить любую карту на замкнутой топологической поверхности без края. Докажите соответствующее неравенство. Вычислите это число с для тора. Нарисуйте на торе карту, которую нельзя правильно раскрасить меньшим, чем с, числом цветов. 23. Докажите теорему о 5 красках. 24. Что такое сеть, ее пропускная способность, поток в сети, величина потока, разрез, пропускная способность разреза ? Привести примеры. Докажите теорему Форда-Фалкерсона. 25. Изложить на примере алгоритм нахождения максимального потока и минимального разреза в сети. 26. Дать определение группы преобразований, привести примеры. Дать определение орбиты точки и стабилизатора точки относительно заданной группы преобразований. Привести примеры. 27. Описать все элементы для каждой из групп правильных многогранников. 28. Сформулировать основную теорему кристаллографии о строении конечных групп вращений трехмерного евклидова пространства. Проиллюстрировать ее на примере группы вращений куба с отпиленным углом при вершине. 29. Как связаны порядок конечной группы преобразований, порядок стабилизатора некоторой точки и порядок орбиты этой точки? Проиллюстрировать эту связь на примерах. 30. Как связаны стабилизатор точки x со стабилизатором точки g(x), где g --- какое-то элемент из группы преобразований множества X? Докажите соответствующе утверждение. Одинаковые ли у этих стабилизаторов порядки? 31. Докажите формулу Бернсайда и проиллюстрируйте ее на примере, где X---множество вершин куба, а G---группа куба (т.е. группа всех его вращений). 32. Р асскажите как подсчитать с помощью теоремы Бернсайда число ожерелий из 6 бусин трех разных цветов. 33. Расскажите как подсчитать с помощью теоремы Бернсайда число различных кубов, вершины которых покрашены в три разных цвета.. 34. Что такое цикловой индекс конечной группы перестановок G множества X из n элементов? Вычислите его когда n=3 и G --- группа всех перестановок из 3 элементов. А какой вид он имеет для произвольного n , когда G --- группа всех перестановок из n элементов? 35. Выпишете все орбиты группы подстановок из 3 элементов на множестве всех неупорядоченных пар различных элементов множества из 3 элементов. 36. Сформулируйте теорему Пойя о цикловом индексе и проиллюстрируйте ее на примере группы подстановок из 3 элементов. 37. Объясните схему нахождения числа неизоморфных графов с n вершинами и m ребрами с помощью теоремы Пойя. Проиллюстрируйте ее на примере, где n=4. |
Похожие:
 | Рабочая учебная программа по дисциплине «Теория графов» для ооп специальности... Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Теория графов Сейчас почти в любой отрасли науки и техники встречается применение графов. В физике при построении электрических схем, в химии и... |
 | Программа вступительных испытаний по дисциплине Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Конспект занятия по факультативу Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) |
| Методические рекомендации по организации математических Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Блок Основные этапы развития геометрии Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) |
| Урок геометрии в 7 классе общеобразовательной школы по теме «Основные... Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Пояснительная записка. За душу каждого математика борются демон абстрактной... Элективный курс «Теория графов» (в рамках предпрофильной подготовки учащихся 9 класса) |
| Реферат по истории математики Научный проф. Верещагин Н. К Теория потоков в сетях – одно из современных направлений развития компьютерных наук в целом, и теории графов в частности. Многие... | | Рабочая программа дисциплины теория государства и права (наименование... ... |
| Рабочая программа учебной дисциплины общая экономическая теория (название... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования | | Рабочая программа дисциплины Теория менеджмента: организационное поведение Дисциплина «Теория менеджмента: организационное поведение» входит в профессиональный цикл дисциплин ( Б. 3). Преподавание дисциплины... |
| Учебно-методическое пособие дисциплины «Общая теория налогов» Структура и объем дисциплины «Общая теория налогов» для направления 080100. 62 «Экономика», профиль «Налоги и налогообложение» | | Рабочая программа Учебной дисциплины управление персоналом для направления... Изучение дисциплины базируется на таких курсах, как «Экономическая теория», «Теория организации и организационное поведение», «Основы... |
| Программа дисциплины «Политическая теория» для направления 03200. 62 «Политология» «Политология» отделения прикладной политологии факультета менеджмента. Она определяет содержание и структуру учебной дисциплины «Политическая... | | Теория менеджмента 2 (организационное поведение) Изучение данной дисциплины базируется на следующих дисциплинах: «История аграрных отношений», «Экономическая теория» |
