Федоров В.Н. - Введение в теорию графов (1023556), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

val(f) = f( ) – f( ) = 5 – 0 = 5 – максимальный поток в сети,

val(f) = c( ).

В результате выполнения алгоритма определены:

• максимальный поток в сети, т.е. ее предельная пропускная способность;

• минимальный разрез (разрез с минимальной пропускной способностью и, возможно, “узкое место сети”),

• загрузка отдельных дуг, которая позволяет сделать, например, вывод о том, что дуги (a, c) и (b, d) не используются (имеют нулевой поток) и их можно удалить.

Задание. Провести исследование сети, в которой изменена ориентация дуги (d, b).

13.4. Контрольные вопросы

1. Сеть – что это такое? Чем она отличается от обычного графа?

2. Поясните понятия пропускной способности дуги и сети.

3. Как определяется поток через дугу и сеть?

4. Что такое насыщенная дуга и нулевая дуга в сети? Чем они похожи и чем различаются?

5. Есть ли различие между полным и максимальным потоками в сети?

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

7. Какой разрез сети называется минимальным? Какую роль играет этот разрез в сети?

14. Примерные темы заданий

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

1. Проиллюстрировать заданные термины и определения теории графов.

(номера терминов задаются по Приложению.)

1. Осуществить над графами K₃ и P₄ операции: , +, .

2. Даны графы G₁ и G₂. Найти G₁ G_2, G₁ G_2, G₁ G₂. графы G₁, G₂ и результаты выполнения операций представить в матричной и векторной формах. Предложить алгоритмы выполнения указанных операций на ЭВМ.

3. Для заданного графа найти радиус, диаметр, средний диаметр, центральные и периферийные вершины.

4. В заданном графе найти все кратчайшие маршруты и циклы.

5. В заданном графе найти все кратчайшие маршруты и циклы с началом в заданной вершине.

6. В заданном графе найти внешне и внутренне устойчивые множества вершин.

7. Раскрасить вершины заданного графа минимальным числом красок (использовать соответствующий алгоритм).

8. Для заданного графа найти сильные компоненты.

9. Для заданного графа найти компоненты связности.

10. Для заданного графа найти матрицы фундаментальных циклов и фундаментальных разрезов.

11. Произвести покрытие заданного графа не пересекающимися по ребрам цепями.

12. Является ли заданный граф планарным? Построить плоское изображение графа.

13. Найти минимальное покрытие заданного двудольного графа.

14. Найти максимальное паросочетание для заданного двудольного графа.

15. Определить дефицит заданного двудольного графа.

16. Найти максимальный поток в заданной сети. Предложить реконструкцию сети для увеличения максимального потока.

Список литературы

1. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2002. –384 с.

2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. – М.: Наука, Физматгиз, 2000. –544 с.

3. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА–М, Новосибирск: Издательство НГТУ, 2002. – 280 с.

4. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для вузов/ Под ред. В.С. Зарубина, А.П. Крищенко. – М.: Изд–во МГТУ им. Н.Э. Баумана, 2001. –744 с.

5. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2003. – 240 с.

6. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2002. –304 с.

7. Акимов О.Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория базовых знаний, 2001. – 376 с.

8. Харари Ф. Теория графов. – М.: Едиториал УРИ, 2003. – 296 с.

9. Зыков А.А. Основы теории графов. М.: Вузовская книга, 2004.-664 с.

10. Овчинников В.А. Алгоритмизация комбинаторно–оптимизационных задач при проектировании ЭВМ и систем. – М.: Изд–во МГТУ им. Н.Э. Баумана, 2001. –288 с.

Приложение

Термины и определения теории графов

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

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

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

В третьей части приводятся основные понятия и определения частей графов и их характеристики.

Примечание. По электронному представлению перечня можно “путешествовать” с помощью гиперссылок, выделенных цветом и подчеркиванием. Двойной щелчок мышью по гиперссылке отправит Вас к определению нужного термина.

1. Элементы графов

1. Вершина (узел, точка) (vertex, node) – элемент множества вершин графа.

2. Ребро (дуга, линия, ветвь) (edge, link) – элемент множества ребер графа.

3. Дуга (arc) – ориентированное ребро [ребро ориентированного графа].

4. Инцидентность вершины и ребра (incident vertex and edge) – вершина графа v и некоторое его ребро e называются инцидентными, если e=(v,w) или e=(w,v), где w – некоторая другая вершина графа.

5. Смежность вершин (contiguous vertices) – две вершины графа называются смежными, если существует ребро, инцидентное обеим этим вершинам (т.е. существует ребро, которое соединяет эти вершины).

6. Петля (loop) – ребро графа, инцидентное единственной вершине.

7. Точка сочленения – вершина, удаление которой из графа увеличивает число компонент связности этого графа.

8. Исток (source) – вершина, являющаяся одним из полюсов ориентированного графа, которой инцидентны только исходящие дуги.

9. Сток (sink) – один из полюсов графа, которому инцидентны только заходящие дуги. Другое название – тупиковая вершина.

10. Корень (root) –вершина – начало дерева.

11. Висячая вершина – вершина, инцидентная единственному ребру.

12. Голая (изолированная) вершина – вершина, которая не имеет инцидентных ребер.

13. Центр (центральная вершина) – вершина, эксцентриситет которой равен радиусу.

14. Периферийная вершина – вершина, эксцентриситет которой равен диаметру.

15. Полюс – выделенная вершина графа. Обычно эти вершины являются истоками и стоками в двухполюсных и многополюсных сетях.

16. Степень вершины (degree) – число инцидентных [этой вершине] ребер, deg(х).

17. Полустепень исхода вершины (outdegree) – число инцидентных исходящих дуг, deg⁺(х).

18. Полустепень захода вершины (indegree) – число инцидентных заходящих дуг, deg^–(х).

19. Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.).

20. Эксцентриситет вершины (eccentricity) х – максимальное расстояние от х до других вершин графа.

21. Удаление вершины. Из графа удаляется вершина вместе с инцидентными ребрами.

22. Добавление вершины. К заданному множеству вершин (х₁, x₂, ... , x_k) добавляется новая вершина y, смежная с х₁, x₂, ... , x_k.

23. Достижимость (соединимость, связность) вершин. Вершина у достижима из х, если существует маршрут из х в у.

24. Односторонняя связность вершин. Вершины х и у односторонне связны в орграфе G, если х достижима из у, а y из x нет, или наоборот.

25. Сильная связность вершин. Вершины х и у сильно связаны в орграфе G, если они взаимно достижимы.

26. Стягивание вершин. Заданное множество вершин объединяется в одну вершину, а полученные петли удаляются.

27. Две вершины s и t k–соединимы, если существует k независимых (s, t)–цепей.

28. Хорда – ребро графа, не принадлежащее остову.

29. Ветвь – ребро графа, принадлежащее остову, или просто ребро дерева.

30. Мост (перешеек) – ребро графа, удаление которого увеличивает число его компонент связности.

31. Висячее ребро – ребро, инцидентное висячей вершине.

32. Мультиребро – множество ребер, инцидентных одной и той же паре вершин.

33. Кратные ребра (duplicate, or parallel, or multiple edges) ребра, инцидентные одной и той же паре вершин.

34. Смежность ребер. Два ребра r₁ и r₂ смежны тогда и только тогда, когда существует, по крайней мере, одна вершина, инцидентная r₁ и r₂.

35. Степень ребра – сумма степеней вершин, инцидентных данному ребру минус два, или число смежных ребер.

36. Вес, длина ребра – число или несколько чисел, которые интерпретируются как длина, пропускная способность и т. д.

37. пропускная способность дуги (ребра) сети – максимальное количество некоторой субстанции, пропускаемое через дугу в единицу времени (обозначается как c(e) 0: e E). Субстанцией может быть информация, некоторый груз, люди, автомобили и т.п.

38. Поток через дугу сети – реальное количество некоторой субстанции, пропускаемое через дугу в единицу времени (обозначается f(e) 0: e E).

39. Насыщенная прямая дуга сети – дуга сети, имеющая направление от истока к стоку сети, в которой поток равен пропускной способности f(e) = c(e). В противном случае дуга не насыщенная. Для прямых дуг 0 f(e) c(e).

40. Нулевая обратная дуга сети – дуга сети, имеющая направление от стока к истоку сети и в которой поток равен нулю f(e)=0. В противном случае дуга не нулевая. Для обратных дуг 0 f(e) c(e)

41. Мощность мультиребра – число ребер в мультиребре.

42. Ориентация ребра. Пара вершин, инцидентная ребру, упорядочивается.

43. Удаление (ребра) дуги. В графе удаляется ребро без инцидентных вершин.

44. Добавление ребра (дуги). Для заданной пары вершин х, у добавляется ребро (х, у).

45. Стягивание ребра (дуги) – вершины х и у, инцидентные заданному ребру, стягиваются в одну вершину.

46. Подразбиение [или подразделение] ребра (дуги). Удаляется заданное ребро u=(х, у) и добавляется вершина z и цепь (x, u₁, z, u₂, у).

2. Структуры графов

1. Граф (graph) – пара G=(V, E), где V – множество объектов произвольной природы, называемых вершинами (vertices), а E – семейство пар e_i=(v_i1, v_i2), v_ijV, называемых ребрами (edges). Соответственно, V называется множеством вершин (vertex set), а E – множеством ребер (edge set). Если порядок элементов, входящих в e_i, имеет значение, то граф называется ориентированным (directed graph), сокращенно – орграф (digraph), иначе – неориентированным (undirected graph). В дальнейшем будем считать, что термин "граф", применяемый без уточнений "ориентированный" или "неориентированный", обозначает неориентированный граф.

2. Граф обыкновенный (simple graph) – граф, не содержащий петель и кратных ребер. Обыкновенные графы нередко называют просто графами; для того, чтобы отличить их от графов, содержащих кратные ребра, последние иногда называют мультиграфами.

3. (n, m)–граф – граф, имеющий в точности n вершин и m ребер. Обозначается G(n,m), например, G(5,7) – граф, имеющий 5 вершин и 7 ребер.

4. Мультиграф – граф, в котором имеются кратные ребра.

5. Псевдограф – граф, в котором имеются дуги, ребра, петли и все они могут быть кратными.

6. Граф полный (complete graph) – граф G=(V,E), в котором любая пара вершин инцидентна единственному ребру [т.е. это обыкновенный граф, в котором любая пара вершин смежна]. Обозначается K_n, где n=|V|, при этом |E|= m = n(n–1)/2.

7. Граф пустой (null graph) – граф G=(V, E), в котором E= [обозначение – N_n].

8. Граф тривиальный – пустой граф, у которого |V|=1.

9. Дерево (tree) – связный ациклический граф.

10. Лес (ациклический граф) (forest, acyclic graph) – обыкновенный граф без циклов (несколько деревьев).

11. Помеченный граф – граф с заданной нумерацией вершин и ребер или с заданными весами вершин и ребер.

12. p–хроматический (p–дольный) граф (p–chromatic graph) – граф G, у которого хроматическое число (G)=p.

13. Граф бихроматический (двудольный граф, граф Кенига) (bipartite graph) – 2–хроматический граф или граф, не содержащий нечетных циклов.

14. Граф двудольный полный (complete bipartite graph) – двудольный граф G=(V₁, V₂, E), у которого любая пара вершин хV₁ и уV₂ смежна. Обозначается K_n1,n2, где n₁=|V₁|, n₂=|V₂|, |E|=n₁n₂.

15. Веер (звезда) – двудольный полный граф K_1,n (другое обозначение – W_n).

16. сеть (двуполюсная) – граф (орграф) с двумя выделенными вершинами (истоком и стоком) без петель.

17. Граф планарный (planar graph) – граф, укладываемый па плоскость без пересечения ребер.

18. Граф плоский (flat graph) – планарный граф, уложенный на плоскость.

19. Граф связный (connected graph) – граф, у которого любая пара вершин взаимодостижима.

20. Сильносвязный орграф (сильный орграф) (strongly connected graph) – орграф, у которого любые две вершины взаимно достижимы.

21. Односторонне связный орграф (односторонний орграф) – орграф, у которого любая пара вершин односторонне связна.

22. Слабосвязный орграф (слабый орграф) – орграф, который после дезориентации дуг будет связным.

23. Однородный [регулярный] (k–регулярный) граф (k–regular graph) – граф, все вершины которого имеют одну и ту же степень, равную k.

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

25. Эйлеров граф (Eulerian graph) – связный граф, не содержащий вершин нечетной степени. В таком графе можно построить цикл или цепь, включающие каждое ребро один раз (Эйлеров_цикл).

26. Гамильтонов граф (Hamiltonian graph)– связный граф, в котором можно построить простой цикл или цепь, проходящие через каждую вершину один раз (Гамильтонов_цикл).

27. Матрица смежности (матрица смежности вершин, матрица смежности графа, матрица соседства) (adjacency matrix) – квадратная матрица, размерности n, A=||a_ij|| является матрицей смежности графа G, если при a_ij=l в графе G вершины x_i и x_j соединены l ребрами, при a_ij=0 вершины x_i и x_j в G не смежны.

Примечание: возможны другие варианты определения понятия матрицы смежности. Во–первых, иногда считают, что матрица смежности может содержать только элементы 0 и 1 (или False и True), где a_ij=1, если вершины x_i и x_j соединены любым количеством ребер, во–вторых, диагональные элементы могут считаться равными 0 или 1.

Характеристики

Список файлов книги