Изоморфизм графов. Разрезы в графе.

ТЕОРИЯ КОНЕЧНЫХ ГРАФОВ И ЕЕ ПРИЛОЖЕНИЯ

ОСНОВНАЯ ЛИТЕРАТУРА

1. Харари Ф. Теория графов. – М.: Мир, 1973.

2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

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

4. Берж К. Теория графов и ее применения. – М.: Изд. иностр. лит., 1962.

 

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА

5. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1977.

6. Евстигнеев В.А. Применение теории графов в программировании. - М.: Наука, 1985.

 

Глава I. Начальные понятия теории графов

 

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

 

Из истории теории графов

Родоначальником теории графов является Леонард Эйлер (1707 – 1783).

В 1736 году Эйлер решил задачу о кенигсбергских мостах. Задача состояла в следующем: «Найти маршрут прохождения всех четырех участков суши (см. рис.), который бы начинался на любом из них, заканчивался на этом же участке и ровно один раз проходил по каждому из 7 данных мостов.»

Река Преголь Þ

При решении задачи Эйлер обозначил части суши точками, а мосты – линиями, и получил граф (вообще говоря, мультиграф):

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

В 1847 году инженер-электрик Г. Кирхгофф, рассматривая электрические цепи, каждую из них заменял на соответствующий граф.

В 1857 году математик А. Кэли, стараясь найти все изомеры предельных углеводородов С_nH_2n+2, открыл важный класс графов – деревья.

В 1869 Жордан независимо от Кэли ввел и изучал деревья, как отдельные математические объекты. С того времени можно считать, что теория графов возникла как самостоятельная математическая дисциплина. Однако термин “граф” впервые был введен венгерским математиком Д. Кенигом лишь в 1936 году - спустя 200 лет после решения Эйлером первой задачи теории графов.

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

1. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эту задачу решил польский математик Куратовский (1896-1979) в 1930 году.

2. Задача о четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие 2 соседние области не были закрашены одним цветом. Первое общепризнанное доказательство теоремы о возможности такой раскраски было опубликовано американскими математиками Аппелем и Хаккеном в 1977 г.

Задачи о Кенигсбергских мостах, о трех домах и трех колодцах, о четырех красках являются одними из важнейших задач теории графов. Их решения будут подробно рассмотрены в следующей главе данного курса.

 

 

Из п.2.Определение графа. Приложения теории графов

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

1. Транспортные задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и/или другие транспортные маршруты (например, авиационные). Сюда же можно отнести и модели сетей снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называют задачами обеспечения или задачами о грузоперевозках.

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

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

4. Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения согласованности взаимодействия между представителями группы и др.

Занятие 1. Способы задания графов. Основная теорема теории графов.

1. Даны графы G и H:

а) Составьте для каждого из них списки вершин и ребер (в виде таблицы), а также матрицы смежности, инцидентности, векторов смежности. Определите по этим матрицам минимальную, максимальную и среднюю степени вершин данных графов.

б) Из матрицы смежности для данных графов получите аналогичные матрицы для дополнений к этим графам, и по ним восстановите графы и .

 

G: H:

 

2. По матрице инцидентностиопределите минимальную, максимальную и среднюю степени вершин графа G. Не изображая этот граф в виде диаграммы, составьте список его вершин и ребер, а также матрицы смежности и векторов смежности.

x ₁ x ₂ x ₃ x ₄ x ₅ x ₆ x ₇

3. N шахматистов (N ³2) проводят турнир в один круг (каждый из участников должен сыграть с каждым по одному разу). Докажите, что в любой момент найдутся двое, закончившие одинаковое число партий.

4. N человек (N >2) проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что либо в точности один участник еще не сыграл ни одной партии, либо ровно один сыграл все партии.

5. Существуют ли графы со следующими наборами степеней вершин:

а) {2, 3, 3, 2, 3}; б) {1, 2, 3, 4}?

Если существуют, то изобразите их графически.

6. Сколько рёбер имеет полный граф с p вершинами?

7. Сколько рёбер имеет регулярный граф с p вершинами степени r?

8. Сколько рёбер может быть у регулярного графа с 9 вершинами?

9. Докажите, что каждый кубический граф имеет чётное число вершин.

10. Сколько вершин может быть у графа с 4 ребрами, если петли, кратные ребра и изолированные вершины у него отсутствуют?

 

Занятие 2. Операции над графами. Маршруты, цепи и циклы в графах.

Связные графы.

11. Найти объединение, пересечение и разность двух графов.

а)

б)

 

в)

12. Составьте матрицы смежности для графовG₁ÈG₂, G₁ÇG₂, G₁\G₂, если

а)

 

б)

13. Дайте классификацию маршрутов в графе,
приведенном на рисунке 1.

(1, 2, 3, 5, 2);

(2, 3, 5, 4);

(2, 3, 4, 5, 3, 2);

(3, 4, 5, 3).

Рис. 1.

14. Приведите примеры замкнутого пути, простого цикла и цикла, не являющегося простым, в графах G и H из задачи 1.

15. Дан регулярный граф с 6 вершинами и 9 ребрами.
а) Докажите, что в нем есть хотя бы 1 цикл.

б) Нарисуйте этот граф.

в) Каковы обхват и периметр данного графа?

г) Сколько в этом графе циклов наименьшей длины?

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

17. Докажите, что каждый граф G содержит цепь длины и (при условии, что ) цикл длины не менее .

18. Найдите количество маршрутов длины 3 от i -ой вершины к j -ой при всех i, j =1,…,5 в графе G ₁ (а) из задачи 12.

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

 

20. Пусть р – число вершин, q – число ребер, k – число компонент связности графа. Докажите, что тогда имеет место следующее неравенство: .

 

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

 

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

G:

 

 

23. Найдите все мосты и разделяющие вершины в графеG:

 

G:

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

25. Докажите, что ребро (v, w) в графе G является мостом тогда и только тогда, когда в этом графе существуют 2 вершины u ₁и u ₂ такие, что каждая цепь, соединяющая их, проходит через ребро (v, w).

Занятие 3. Вершинная и реберная связность графов. Расстояния в графе.

Изоморфизм графов. Разрезы в графе.

26. Докажите неравенство , где - вершинная связностьграфа G, - реберная связность, - минимальная степень вершины графа.

27. Найдите радиус, диаметр и центр

а) графа G из задачи 23; б) графа Н ₄ из задачи 31.

28. Докажите, что для любого графа G .

29. Докажите, что для каждого графа G, содержащего цикл, справедливо неравенство: , где - длина наименьшего цикла в графе G.

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

31. Изоморфны ли данные графы? Ответ обоснуйте.

а) G ₁ G ₂

 

 

 

б) H ₁ H ₂

 

 

в) G ₃ G ₄

 

 

г) H ₃ H ₄

 

 

32. Исследуйте данные тройки графов на попарную изоморфность.

а) G ₁ G ₂ G ₃

 

б) Н ₁ Н ₂ Н ₃

 

в) G ₄ G ₅ G ₆

 

33. Пусть связные графы G и H имеют по 6 вершин и по 8 ребер. У графа G ровно 2 вершины степени 2, а граф Н имеет ровно 4 вершины степени 3. Можно ли утверждать, что графы G и H

а) изоморфны? б) не изоморфны?

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

35. Найти минимальный разрез и цикломатический набор ребер в следующих графах:

G: H:

 

 

Занятие 4. Деревья. Двудольные, эйлеровы и гамильтоновы графы

36. Составьте коды для данных деревьев:

Т ₁ Т ₂

 

 

37. Даны коды деревьев:

а) (0100011001101011); б) (00101001110001010111).

Сколько вершин имеет каждое из этих деревьев? Постройте соответствующие деревья.

38. Докажите, что в каждом дереве есть не менее двух листьев.

39. Сколько существует неизоморфных между собой деревьев с 6 вершинами?

40. Сколько ребер имеет лес с p вершинами и n деревьями?

41. Докажите, что графы G и H не содержат циклов нечетной длины.

G: H:

 

 

42. Завуч школы должен составить расписание одного учебного дня для одного класса (все 4 предмета в расписании должны быть разные) с учетом следующих обстоятельств:1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок;2. учитель литературы может дать один, либо второй, либо третий урок;3. математик готов дать либо только первый, либо только четвертый урок;4. преподаватель физкультуры согласен дать только третий или четвертый уроки. Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч?

43. Приведите пример связного графа с циклами, который является

а) эйлеровым, но не гамильтоновым; б) гамильтоновым, но не эйлеровым;

в) не эйлеровым, и не гамильтоновым.

44. Доказать, что в любом полном графе, имеющем не менее 3 вершин, есть гамильтонов цикл.

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

46. Доказать необходимое условие гамильтоновости графа: если граф G является гамильтоновым, то в нем отсутствуют разделяющие вершины.

 

47. Доказать, что в пронумерованном полном графе K_p имеется (p- 1)!/2 различных гамильтоновых циклов.

48. Существуют ли в полном двудольном графе K _3,3 и в графе G, заданном на рисунке, эйлеров цикл, гамильтонов цикл, эйлерова цепь, гамильтонова цепь? Укажите их или докажите их отсутствие.

G:

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

50. Является ли данный граф гамильтоновым?

 

51. Докажите, что любой граф с р вершинами, имеющий не менее ребер, имеет гамильтонов цикл.

Занятие 5. Планарные графы. Раскраска графов

52. Являются ли следующие графы планарными? Ответ обосновать.

 

 

а) G ₁: б) G ₂:

 

 

в) H: г) P – граф Петерсена:

53. Докажите, что в любом планарном графе существует вершина, степень которой не больше 5.

 

54. У графа G с р вершинами () только 1 пара вершин не соединена ребром (все остальные вершины смежные). При каком р граф G является планарным?

55. Плоский связный граф, каждая грань которого, включая и внешнюю, ограничена циклом длины 3, называется триангуляцией. Покажите, что всякая триангуляция с вершинами имеет 3 р -6 ребер и 2 p -4 граней.

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

 

57. Найдите хроматические числа и хроматические индексы графов G ₁ и G ₂, а также графов Н и Р из задачи 52.

G ₁ G ₂

58. Докажите неравенство для хроматического числа графа .