Упражнения. 1. Существует ли неориентированный граф, степени всех вершин которого различны?

1. Существует ли неориентированный граф, степени всех вершин которого различны?

2. Постройте неориентированный граф, степени вершин которого равны 2,2,2,3,3,4,5. Существует ли такой граф?

3. Постройте все неизоморфные неориентированные графы, у которых 4, 5, 6 вершин. Тот же вопрос для ориентированных графов с 4 вершинами.

4. Докажите, что среди 6 человек найдется либо трое попарно знакомых, либо трое попарно не знакомых. А среди 5? Какое минимальное число людей надо взять, чтобы среди них нашлись либо двое попарно знакомых, либо двое попарно не знакомых? (Последний вопрос шуточный)

5. Докажите или опровергните изоморфизм данных пар графов.

6. Постройте дополнительные и смежные графы для данных графов.

7. Сколько существует неизоморфных помеченных графов с p вершинами?

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

9. Докажите, что число дуг графа, смежного к Г, равно .

10. Постройте матрицы смежности и инциденций для данных графов при различной нумерации вершин и дуг. Решите обратную задачу.

11. Докажите теорему 15.

12. Докажитетеорему 16.

13. Найдите компоненты сильной связности графов, заданных матрицами смежности.

14. Проверьте или опровергните, что граф, заданный матрицей смежности, дерево.

15. Запишите код данного дерева.

16. Восстановите дерево по коду.

17. Найдите эксцентриситеты всех вершин данных графов (полного, двудольного, цикла, цепи и др.), найдите их радиус, диаметр и центр.

18. Найдите минимальное остовное дерево данных неориентированных взвешенных графов.

19. Установите, является ли данный вектор эйлеровым (полуэйлеровым) и при положительном заключении постройте эйлеров цикл (эйлерову цепь).

20. Постройте все гамильтоновы циклы данного графа, если они существуют.

21. Решите задачу коммивояжера для данных взвешенных графов.

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

23. Найдите в данном графе максимальное паросочетание и минимальное реберное покрытие.

24. Постройте полное паросочетание в данном двудольном графе или докажите, что оно не существует.

25. Постройте критические пути в данном сетевом графике.

26. Найдите в графе при заданных начальной и конечной вершинах максимальный поток и минимальный разрез.

Рекомендуемая литература

По дискретной математике книги различного уровня издаются постоянно. Приведем несколько достойных (по мнению автора) изданий. Большинство книг доступно в сети.

1. Кузнецов О.П. Дискретная математика для инженера. — СПб.: Лань, 2004 (предыдущие издания совместно с Адельсоном-Вельским Г.М.)

2. Романовский И. В. Дискретный анализ. — 4-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2008.

3. Андерсон Дж. Дискретная математика и комбинаторика — М.: «Вильямс», 2006.

4. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1979

5. Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М.: Наука, 1963.

6. Юлмухаметов Р. С., Исаев К.П., Трунов К.В. Дискретная математика: курс лекций Уфа: РИО БашГУ, 2005.

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

7. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. – М.: ФИМА, МЦНМО, 2006.

8. Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990.

9. Кнут Д., Грэхем Ф., Поташник О. Конкретная математика. Основы информатики. – М.: Мир, 2006.

Издается множество книг, посвященных теории графов. Перечислю несколько из них.

10. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

11. Харари Ф. Теория графов. – М.: Либроком, 2009 г.

12. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Либроком, 2009 г.

13. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

14. Дистель Р. Теория графов. – Новосибирск: Изд-во Института математики, 2002.

15. Свами М., Тхулалираман К. Графы, сети и алгоритмы. – М: Мир, 1984.

16. Татт У. Теория графов. – М: Мир, 1988.

Ряд упражнений заимствован из пособия Исаева К.П., Трунова К.В. «Задачи по дискретной математике» (Уфа, БашГУ, 2006).