Дискретная математика

168 13. Что можно определить по матрице инциденций графа? 14. Деревья. 15. Основные свойства деревьев. 16. Ориентированные деревья. 17. Задача о минимальном соединении. 18. Эйлеровы графы, 19. Критерий эйлеровости графа. 20. Алгоритм построения эйлерова цикла, 21. Гамильтоновы графы. 22. Ппанарные графы. Неппанарность графов Ks и Кз,з- 23. Критерий ппанарности графов. 24. Задачи о кратчайшей цепи в графе с ребрами единичной длины. 25. Задача о кратчайшей цепи в графе с ребрами произвольной длины. 26. Алгоритм Дейкстры нахождения кратчайших путей в орграфе. 27. Потоки в сетях. 28. Нахождение максимального потока. Упорство - благоприятно. И. Цзт § 21. Упражнения 1. Построить всевозможные неизоморфные непомеченные графы с тремя вершинами. 2. Построить всевозможные неизоморфные непомеченные орграфы с тремя вершинами. Сколько их и сколько среди них направленных графов? 3. Построить всевозможные неизоморфные графы с тремя помеченными вершинами, 4. Построить всевозможные неизоморфные орграфы с тремя помеченными вершинами. 5. Определить максимально возможное число ребер в графе с п вершинами. 6. Дан граф с 2п (п >2) вершинами, перенумерованными числами 1, 2, ..., In. Смежными являются только вершины с нечетными номерами, и только они. Сколько ребер в этом графе? 7. Пусть граф состоит из вершин и ребер тетраэдра. Определите локальные степени его вершин. Является ли граф полным? 8. Пусть граф состоит из вершин и ребер куба. Сколько ребер нузкно добавить, чтобы получить полный граф? 9. Построить полный граф с 5 вершинами; с 7 вершинами. 10. Пусть дан граф G - (V,X), представленный на рис.5.17. Задать его; 1) перечислением множества вершин и множества ребер; 2) перечислением списков смежностей.