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

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. Какие из графов, изображенных на рис. 10 – 12, являются планарными?

Рис. 10	Рис. 11	Рис. 12

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

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

Рис. 13	Рис. 14

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

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

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

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

а) ; б) ; в) .

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

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

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

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

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

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

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

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

а) ; б) ; в) .

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

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

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

39. Построить минимальные УБДР функции относительно порядка:

а) ; б) .

40. Построить минимальную УБДР относительно порядка для функции , заданной формулой:

а) ; б) .