Контрольная работа повышенной сложности

Контрольная работа состоит из трех задач следующего списка:

1. Доказать, что влюбом графе число вершин нечетной степени может быть только четным.

2. Рассмотрим на множестве вершин произвольного графа бинарное отношение смежности: будем считать, что вершины связаны этим отношением, если они соединены ребром. Нарисуйте диаграмму графа, для которого отношение смежности будет:

а) рефлексивным, но не транзитивным;

б) транзитивным, но не рефлексивным;

в) отношением эквивалентности.

3. Пусть - полный граф с множеством вершин и множеством ребер .

а) Сколько у графа подграфов с тем же множеством вершин, что и у графа ?

б) Сколько у графа всего подграфов?

4. Доказать, что если графы и изоморфны и одно из ребер графа есть петля, то одно из ребер графа также является петлей.

5. Доказать, что если графы и изоморфны и - взаимно однозначное отображение в этом изоморфизме, то для любой вершины графа выполняется равенство .

6. Доказать, что если графы и изоморфны и на графе есть цикл длины , то и на графе также есть цикл длины .

7. Назовем декартовым произведением графов и граф , вершинами которого являются упорядоченные пары вида , где , и в котором вершины и смежные в точности в одном из двух случаев: 1) и - смежные вершины в графе , а ; 2) и - смежные вершины в графе , а .

а) Пусть - граф вершинами и и ребром , а - граф с вершинами , , и ребрами , Построить диаграмму графа .

б) Пусть - граф вершинами 0 и 1 и ребром . Построить диаграммы графов , , .

в) Построить диаграмму графа .

8. Определим по индукции граф : пусть - граф вершинами 0 и 1 и ребром ; тогда для любого натурального . Найти число вершин и ребер графа .

9. Пусть - обыкновенный граф, - матрица смежности этого графа, отвечающая некоторой нумерации вершин , , …, . Выразить через число вершин, ребер или степени вершин следующие суммы:

а) ; б) .

10. Сколько существует обыкновенных графов, у которых вершин (вершины помечены)? Сколько из них имеет ровно ребер?

11. Доказать, что в любом обыкновенном графе, содержащем более одной вершины, найдутся две различные вершины одинаковой степени.

12. Пусть - обыкновенный граф, - матрица смежности этого графа, отвечающая некоторой нумерации вершин , , …, .

а) Как по матрице определить число путей длины из в .

б) Как в случае связного обыкновенного графа по матрице определить длину кратчайшего пути между вершинами и ()?

13. Доказать, что замкнутый путь нечетной длины содержит простой цикл. Верно ли аналогичное утверждение для замкнутых путей произвольной длины?

14. Доказать или опровергнуть следующие утверждения:

а) объединение любых двух различных цепей, соединяющих две вершины, содержит простой цикл;

б) объединение двух различных простых цепей, соединяющих две вершины, содержит простой цикл.

15. Доказать или опровергнуть следующее утверждение: граф связен тогда и только тогда, когда для любого разбиения множества на два подмножества и существует ребро графа , соединяющее некоторую вершину из с некоторой вершиной из .

16. Показать, что связный граф с вершинами содержит не менее ребер.

17. Доказать, что в связном графе любые две простые цепи максимальной длины имеют по крайней мере одну общую вершину.

18. Показать, что графе с вершинами и двумя компонентами связности число ребер не более .

19. Доказать, что обыкновенный граф, имеющий более ребер (), является связным.

20. Сколько существует попарно неизоморфных обыкновенных графов с 16 вершинами и 118 ребрами?

21. Пусть , , …, - все компоненты связности графа . Доказать, что .

22. Опираясь на теорему о характеристических свойствах деревьев, доказать, что граф , имеющий компонент связности, является лесом в том и только в том случае, когда .

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

24. Используя теорему Кирхгофа, показать, что число остовов в полном графе с помеченными вершинами равно .

25. Рассмотрим на множестве графов бинарное отношение гомеоморфизма (пара графов и связана этим отношением, если гомеоморфен ). Какими свойствами это бинарное отношение обладает?

26. Какие из графов, изображенных на рис., являются планарными?

27. При каких ( - число квадратов) граф, изображенный на рис. 13, является планарным?

28. При каких и граф является планарным?

29. Доказать, что граф непланарен.

30. Доказать, что изоморфные графы имеют одинаковые хроматические числа.

31. Найти хроматическое число графа:

а) ; б) ; в) .

32. Доказать, что для любого натурального найдется обыкновенный граф с вершинами и ребрами, не имеющий циклов нечетной длины.

33. Подсчитать, сколько циклов входит в фундаментальную систему циклов следующих графов:

а) графа, все ребра которого мосты;

в) графа, имеющего 11 вершин, 10 ребер и состоящего из 4-х компонент связности.

34. Подсчитать, сколько циклов входит в фундаментальную систему циклов следующих графов:

а) ; б) ; в) ; г) ; д) .

35. Сколько всего обобщенных циклов имеет граф , если ?

36. Пусть - обыкновенный ориентированный граф, - матрица смежности этого графа, отвечающая некоторой нумерации вершин , , …, . Выразить через число вершин, дуг или степени вершин следующие суммы:

а) ; б) ; в) .

37. Пусть - обыкновенный ориентированный граф, - матрица смежности этого графа, отвечающая некоторой нумерации вершин , , …, .

а) Как по матрице определить число путей длины , ведущих из вершину в вершину ?

б) Как в случае сильно связного ориентированного обыкновенного графа по матрице определить длину кратчайшего по числу дуг пути между вершинами и ()?

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Задание предоставляется индивидуально из учебного пособия Кожухов И. Б., Ревякин А. М., Бардушкина И. В. Дискретная математика: Учебное пособие для студентов специализации «Информационная безопасность». М.: Изд. центр МГАДА, 2013. — 366 с.

Примерные вопросы к дифференцированному зачету.

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. Полугруппы и группы (простейшие свойства).

31. Порядок элемента в группе. Циклические группы.

32. Группа подстановок.

33. Разложение группы по подгруппе. Теорема Лагранжа.

34. Фактор-группа. Теорема об изоморфизме.

35. Абелевы группы.

36. Определение и примеры полей.

37. Поле комплексных чисел.

38. Определение и примеры колец.

39. Гомоморфизмы и изоморфизмы колец. Подкольца и идеалы.

40. Многочлены над полем. Простейшие свойства многочленов над полем. Деление многочленов.

41. Наибольший общий делитель и наименьшее общее кратное. Алгоритм Евклида.

42. Корни многочленов. Теорема Безу. Схема Горнера.

43. Неприводимые многочлены. Теорема Виета.

44. Расширения полей. Конечные поля………………..

45. Китайская теорема об остатках.

48. Алгоритм нахождения больших простых чисел.

49. Схема шифрования с открытым ключом.

 

Учебная дисциплина