Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

Примеры решения

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

орграф без петель"), имеющий единственный источник (будем обозначать его Vj) и единственный сток (vn). Все остальные вершины графа будем называть промежуточными. Если каждой дуге графа а е А поставлено в соответствие неотрицательное целое число с(а) (пропускная способность дуги), то говорят, что задана транспортная сеть (или просто: сеть) (G, с).

Функция (р: А N0 (определенная на семействе дуг орграфа и принимающая неотрицательные целые значения) называется потоком в сети (G, с), если выполняются следующие условия: 1) для любой дуги 2) для любой промежуточной вершины графа v Величину будем называть потоком по дуге а. Таким образом, 1) поток по каждой дуге не должен превышать ее пропускной способности; 2) сумма потоков по дугам, заходящим в произвольную промежуточную вершину, равен сумме потоков по дугам, исходящим из этой вершины.

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

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

Дуга о € А называется насыщенной, если поток по ней равен ее пропускной способности: . Поток называется полным, если любой пугь в орграфе содержит по меньшей мере Петя в орграфе — дуга вида (и, и). одну насыщенную дугу. Очевидно, что всякий максимальный поток является полным (иначе увеличив потоки по ненасыщенным дугам,4 составляющим путь W| -» ... vn> на 1, мы не нарушим условий 1) и 2) потока и получим поток с большей на 1 величиной, чем у данного потока).

В дальнейшем будем считать, что орграф G = (V, А) — антисимметрический, т. е. он не содержит кратных дуг и если (u, v) € А, то (v, и) А. Это предположение не является сильно ограничительным, поскольку подразбиением дуг (введением дополнительных «фиктивных» вершин) всегда можно по данной сети построить сеть с антисимметрическим орграфом и той же величиной потока. Максимальный поток можно найти с помощью следующего алгоритма. Алгоритм Л. Форда-Д. Фалкерсона 1.

Построить произвольный поток в сети (G\c) (можно и нулевой). 2 Построить полный поток. Если поток не полный, то в сети существует путь из 1/о в vn, все дуги которого не насыщены. Увеличивая потоки через все дуги такого пути Р на величину , получаем путь, некоторая дуга а€Р которого является насыщенной. Такую операцию следует повторять до тех пор, пока не получится полный поток. 3. Построить максимальный поток. а) Начальные пометки. Присвоить источнику пометку 0: l(v|) = 0, а остальным вершинам пометку оо. Следующий шаг повторять до тех пор, пока в результате его выполнения не будет помечен сток vn либо пока не перестануг появляться новые пометки.

б) Пересчет пометок. Для каждой помеченной вершины Vj, пометить символом -ft все непомеченные вершины , для которых дуги (vi, v) ненасыщенные и символом -i все непомеченные вершины, для которых в) Увеличение потока. Если сток vn не получает новую пометку, то закончить работу алгоритма (максимальный поток найден), в противном случае существует цепь, все вершины которой помечены. Если ориентация дуги совпадает с направлением прохождения цепи, будем обозначать ее а*, в противном случае — V.

Если то положить . Если то положить = Пусть (минимум вычисляется по всем дугам, составляющим указанную цепь). По каждой дуге а* поток увеличить на е, а по каждой дуге V поток уменьшить на е. (При этом величина потока в сети W(tp) увеличится на е.) Перейти к шагу а). Перед тем, как обосновать алгоритм Форда—Фалкерсона, проиллюстрируем его работу на примере (рис. 32, на котором насыщенные дуги помечены значком " х "). Начальный поток не является полным. В пути W| v3 -» v4 v6 все дуги не насыщены; увеличение потока, проходящего через этот путь, на 2 приводит к насыщению дуги v3 -> vA. Находим, еще один путь (vi -> v3 -> v$ -» t/6), Примеры решения.

Заметьте: в обшем случае — не путь\ ис. 32. Алгоритм Форда—Фалкерсона нахождения максимального потока состоящий из ненасыщенных дуг; увеличение потока через каждую из этих дуг на 1 делает дугу v3 v5 насыщенной. Теперь получен полный поток. Переходим к 3-му этапа алгоритма Форда-Фалкерсона. Расставляем пометки вершин, как показано на рис. 32 г.

Возможно вам будут полезны данные страницы:

Алгоритм Флери построения эйлерова цикла
Химические расчеты
Каркас это несущая конструкция здания. Вертикальные и горизонтальные нагрузки
Предел сложной функции

Получаем цепь Имеем: Уменьшаем поток на 1 через дугу (ъ, V;) и увеличиваем его на 1 через остальные дуги этой цепи.

При повторении процедуры (рис. 32 д) удается пометить только две вершины (vi и v3). Максимальный поток найден: Доказательство корректности алгоритма Форда-Фалкерсона Так как количество различных (целочисленных) потоков в фиксированной транспортной сети конечно, максимальный поток существует.

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

Разрезом сети относительно В называется множество А~в дуг, исходящих из вершин, не принадлежащих В, и заходящих в вершины из В: Сумма пропускных способностей всех дуг разреза называется пропускной способностью разреза: Разрезе минимальной пропускной способностью называют минимальным разрезом. Из «физических» соображений кажется почти очевидным, что выичина потока в сети не превосходит пропускной способности любого разреза (значит, и минимального).

Для строгою доказательства этого факта нам понадобится Лемма 5. Для любого множества В вершин орграфа G, среди которых есть сток и нет источника, справедливо следующее равенство'. где Прибавив к уменьшаемому и вычитаемому в разности (1) сумму потоков по всем дугам, исходящим из В и заходяшим в В, получим равенство, равносильное (1): Вклад стока vn в левую часть (2) равен , а вклад каждой из остальных вершин из множества В (так как среди них нет и источника, все они — промежуточные) равен 0 в силу условия 2) потока. Соотношение (2), а вместе с ним и (1), доказано.

Дальнейшее рассуждение очевидно: Итак, мы выяснили, что величина потока в сети не превосходит пропускной способности минимального разреза. После окончания работы алгоритма Форда— Фалкерсона в сети не существует цепи Wi v„f вдоль которой возможно уве- личение потока. Пусть В — множество вершин, которые не получают (конечной пометки на последней итерации алгоритма. Заметим, что . Рассмотрим разрез сети относительно В.

Пусть и — помеченная вершина -непомеченная (v € В). Если дуга имеет вид (и, v)\ то согласно алгоритму эта дуга является насыщенной: . Если дуга имеет вид (v.tx), то согласно алгоритму поток по этой дуге равен нулю: Применим теперь лемму 5: Таким образом, в результате работы алгоритма построен поток, величина которого равна пропускной способности некоторого разреза сети; поэтому поток — максимальный. Мы доказали следующее утверждение: Теорема 19 (Л. Форд-Д. Фалкерсон, 1956 г.).

Величина максимального потока в сети равна пропускной способности минимального разреза. В заключение параграфа — несколько замечаний. 1. Приведенное выше доказательство теоремы Форда—Фалкерсона показывает, как найти один из минимальных разрезов. Это разрез составляют дуги, ведущие из помеченных вершин в непомеченные на последнем этапе работы алгоритма Форда —Фалкерсона. Например, для транспортной сети, изображенной на рис. 32а, минимальный разрез образуют дуги W1V2, V3V5. 2.

Если величина пропускной способности дуги не обязательно является неотрицательным целым числом, то, как показали сами Форд и Фалкерсон, если «неудачно-» выбирать увеличивающие цепи, то процесс выполнения алгоритма может никогда не кончиться, более того, величина текущего потока может все время не превосходить четверти максимального потока. В настоящее время известен эффективный алгоритм нахождения максимального потока трудоемкости 0(п?). 3.

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

Пусть Gn — простой граф с множеством

вершин в котором вершины v, и Vj смежны тогда и только тогда, когда числа * и j взаимно просты. Изобразить графы Ga и Gb и найти их матрицы смежности. Показать, что если 2. Ячя графов из каждой пары графов, изображенных на рис. 33, выяснить, изоморфны ли они. Найти все (с точностью до изоморфизма) простые графы, в которых не более пяти вершин.

4. Сколько существует попарно неизоморфных простых графов с 10 вершинами и 1) 44; 2) 43 ребрами? 5. Сколько существует помеченных простых графов с п вершинами? Сколько из них имеет m ребер? Примеры решения 6. Доказать, что в простом графе с не менее чем двумя вершинами найдутся две вершины одинаковой степени. 7. Показать, что реберные графы L(Kn) и ЦКп>т) являются регулярными. 8. Доказать, что при п > 2 звездный граф Ку>п не является реберным графом.

9. Пусть рп — степени вершин графа G. Сколько вершин и ребер содержит реберный граф 10. Доказать, что простой граф изоморфен своему реберному графу тогда и только тогда, когда он является дизъюнктным объединением циклических графов. 11. Привести примеры (когда это возможно) 1) двудольного графа, являющегося регулярным; 2) кубического графа с 9 вершинами; 3) (для каждого п) простого графа с п вершинами и ---ребрами; 4) (для каждого п) простого графа с п вершинами, изоморфного своему реберному графу;

5) связных графов, являющихся регулярными графами степени 4. 12. Какие из Платоновых графов являются двудольными? [Теорема Кёнига.] Граф является двудольным тогда и только тогда, когда все его циыы имеют четную длину. Доказать. 14. Доказать, что в непустом двудольном регулярном графе доли содержат равное число вершин. 15. Может ли регулярный степени выше 1 двудольный граф иметь мосты? 16. В связном графе степени четырех вершин равны 3, а степени остальных вершин равны 4.

Доказать, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности. 17. Пусть в графе среди любых четырех вершин найдется вершина, смежная с тремя остальными. Доказать, что радиус графа равен единице. 18. Найти дополнения к графам, соответствующим тетраэдру, кубу и октаэдру. Вычислить: - простые графы). 20. Пусть G, Н и К — простые графы; доказать или опровергнуть следующие равенства: 21. Найти матрицы смежности (рафов Kn,Nn 22.

Чем характерна матрица смежности двудольного графа? 23. Какова связь между матрицами смежности простого графа и его дополнения? 24. Пусть А — матрица смежности регулярного графа степени к. Доказать, что к есть собственное значение матрицы А. Найти отвечающий ему собственный вектор. 25. В графе Петерсена найти циклы длины 5, 6, 8 и 9. 26. В графе Петерсена найти разрезы из 3, 4 и 5 ребер. 27. Доказать, что дополнение к (простому) несвязному графу есть связный граф. 28.

Доказать, что реберный граф связного графа связен. 29. Пусть G — граф с множеством вершин { и матрицей смежности А. Доказать, что число маршрутов длины к из v, в vi равно элементу матрицы Ак. Показать также, что если G — простой граф, то число треугольников (циклов длины 3) в С? равно (г — (где tr А — ~ матрицы А). Верно ли, что число циклов длины 4 равно 30. Основываясь на результате предыдущей задачи, предложите алгоритм определения диаметра графа по его матрице смежности. 31. [Экстремальная теорема Турана.] Пусть G — простой граф с 2п вершинами, не содержащий треугольников.

Доказать, что в G не более п2 ребер и привести пример, когда эта верхняя граница достигается. 32. Найти максимальное число ребер в простом графе с 2n+ 1 вершинами, не содержащем треугольников. 33. Найти радиус и диаметр графа Петерсена. 34. Для каждого п построить пример графа, центр которого состоит из п вершин и не совпадает с множеством всех вершин. 35. Пусть 1) Найти цикловой индекс группы подстановок на множестве ребер полного графа с п вершинами, порожденных перестановками вершин.

2) С помошью теоремы Пойа найти число попарно неизоморфных простых графов с п вершинами и m ребрами. Гамильтоновы и эйлеровы графы 36. Для какихчисел тип следующие графыявляются а) эйлеровыми; б) гал*ильтоноиыми: 37. Привести пример эйлерова графа, не являюшегося гамильтоновым, и гамильтонова графа, не являющегося эйлеровым. 38. Пусть G — двудольный граф. доли которого содержат тип вершин соответственно.

Доказать, что 1) если G — гамильтонов граф, 2) если G — полугамильтонов граф. то |m - n| ^ I. Может ли а) конь; б) король; в) ладья побывать на каждой клетке шахматной доски размером 8x8 ровно один раз и последним ходом возвратиться в исходную позицию? Решить такую же задачу для доски 7x7. 40. Можно ли прогуляться по парку и его окрестностям (рис.34) так, чтобы при этом перелезть через каждый забор ровно один раз? 41. Доказать, что если граф G связен и имеет к > 0 вершин нечетной степени, то минимальное число не имеющих общих ребер цепей, объединение которых содержит каждое ребро графа G, равно к/2. 42.

Дан кусок проволоки длиной 120 см. Какое наименьшее число раз придется ломать проволоку, чтобы изготовить каркас куба с ребром 10 см? 43. Можно ли сетку, составленную из единичных квадратов (рис.35), представить в виде объединения 1) восьми ломаных длины 5; 2) пяти ломаных длины 8? 44. С помощью алгоритма Флери найти эйлеров цикл в графе на рис. 36. 45. Доказать, что реберный граф простого эйлерова графа является одновременно эйлеровым и гамильтоновым.

46. Доказать, что реберный граф простого гамильтонова графа является гамильтоновым. Деревья 47. Найти все (с точностью до изоморфизма) деревья, в которых не более семи вершин. 48. Волейбольная сетка имеет вид прямоугольника 50 х 600 клеток. Какое наибольшее количество веревочек можно перерезать так, чтобы сетка не распалась на куски? 49. Доказать, что каждое дерево является двудольным графом. Какие деревья являются полными двудольными графами?

50. Если в дереве не менее двух ребер, то его радиус меньше диаметра. Доказать. 51. Доказать, что центр дерева состоит из одной вершины, если диаметр дерева есть четное число, и двух вершин в противном случае. 52. Верно ли, что в дереве с нечетным диаметром любые две простые цепи наибольшей длины имеют хотя бы одно общее ребро? 53.

Выразите радиус дерева через его диаметр. 54. Пусть п — количество вершин дерева, г — его радиус. Доказать, что n ^ 2г. 55. Верно ли, что если диаметр графа равен к > 2. то граф имеет стягивающее дерево диаметра к? 56. Для каждого из указанных ниже графов найти какое-нибудь стягивающее дерево и фундаментальную систему циклов относительно него. Примеры решения граф Петерсена. 57. Пусть Г, и Т2 — стягивающие деревья связного графа G.

Показать, что для любого ребра е из Т, существует ребро / из Т2 такое, что после «замены» в Т, ребра е на ребро / вновь получится стягивающее дерево. (С помощью подобной процедуры можно построить последовательность стягивающих деревьев Т]г... ,Т2. в которой каждое дерево получается из предыдущего заменой одного ребра). Доказать, что число реберно-помеченных деревьев с n ^ 3 вершинами (в которых помечены не вершины, а ребра) равно п"~3.

59. Показать, что при больших п вероятность того, что случайным образом выбранная вершина дерева с п вершинами является висячей, приближенно равна 1/е. 60. Найти стягивающее дерево минимального веса для каждого графа на рис. 37. Рис. 37 61. Необходимо построить систему нефтепроводов, которые должны соединять семь нефтеочистительных заводов, принадлежащих некоторой компании, с портом (П), куда поступает сырая нефть.

Известны (табл. 7) предполагаемые ежегодные затраты на эксплуатацию нефтепровода между соответствующими пунктами. Таблиц* 7 Найти систему нефтепроводов, позволяюи^ю осуществлять переброску нефти от порта ко всем заводам с минимальными годовыми эксплуатационными затратами. Корнежые деревья Дерево с выделенной вершиной (корнем) называют корневым деревом. 62. Найти число помеченных корневых деревьев с п вершинами. В книгах, посвященных исследованию структур данных, корневое дерево определяют рекурсивно следующим образом.

Корневое дерево Т — это непустое конечное множество Т с элементами, называемыми вершинами, такими, что 1) имеется выделенная вершина, называемая корнем данного дерева; 2) если множество остальных вершин непусто, то оно разбивается на т множеств Ti,... ,ТК, каждое из которых в свою очередь является корневым деревам. Ориентированные графы. Алгоритмы 73. Пусть А — матрица смежности орграфа с множеством вершин {«,,...,»„}• Какой смысл имеют суммы строк и суммы столбцов матрицы А?

Доказать, что (i,j)-й элемент матрицы Ак равен числу путей длины к из в Vj. 74. В дереве с п вершинами ребра ориентируются случайным образом. Какова вероятность того, что найдется вершина, из которой ведут пути ко всем остальным вершинам? 75. Пусть G — связный граф. Зафиксируем некоторую его вершину v. Доказать, что можно так ориентировать ребра графа, что в получившемся орграфе существует путь от v до любой другой вершины. Ориентированный граф называют сильно связным, если для любых его вершин и и v существует путь,из и в v.

76. В связном графе степени всех вершин четны. Доказать, что можно так ориентировать ребра графа, чтобы 1) получившийся орграф был сильно связным; 2) для каждой вершины полустепень исхода была равна полустепени захода. 77. В ориентированном графе со связным основанием для каждой вершины полустепень исхода равна полустепени захода.

Доказать, что орграф эйлеров. 78. Найти кратчайший путь от 1-й вершины до всех остальных (рис. 38а, б). структурно-временная таблица работ по организации выстав»-продажи товаров (табл. 8). Требуется построить сетевой график, найти наименьшее время выполнения проекта, определить критический путь, вычислить резервы времени для выполнения каждой операции. Таблица 8 Этап проекта Обозначение Опорные Время (элементарная работа) работы выполнения Заказ на оборудование и товары.

Разработка системы учета спроса Отбор товаров и выписка счетов Завоз товаров Завоз оборудования Установка оборудования Выкладка товара Учет наличия товара Оформление зала и ви!рины Изготовление документов учета Репетиция выставии-продажи 80. Пусть проекты описываются взвешенными графами (рис. 39 а, б), где дуги соответствуют операциям (этапам) проекта, а вес дуги обозначает время выполнения соответствующей операдаи.

Найти наименьшее время выполнения проектов, критические пути и резервы времени для выполнения каждой операции. Найти максимальные гтото»» и минимальные разрезы в транспортных сетях (рис. 40а, б). Число рядом с дугой есть ее пропускная способность. . Пусть имеется m неженатых мужчин, п незамужних женщин и к свах. У каждой свахи есть список своих клиентов; между любыми мужчиной и женщиной из этого списка сваха может устроить брак.

Для »-й сва»1 число устроенных ею за год браков не превосходит числа Ь,. Перевести задачу нахождения наибольшего числа браков, которые могут устроить свахи за год, в задачу нахождения максимального потока в некоторой сети. вершину, смежную с концом самой длинной цепи. 5 общего количества вершин нужновычесть количество внутренних вершин. . Нет. 71.

Если у пленарного графа п вершин и m ребер, то выполняется неравенство m ^ Зп - 6. 72. Индукция по числу вершин. 74. п/2я~'. 78. В исходном графе существует эйлеров цикл. 77. Перенеся доказательство теоремы Эйлера на случай графа из условия задачи, можно построить замкнутый путь, содержащий все дуги орграфа.