Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 5
Текст из файла (страница 5)
Терминология и сбоэлачеяая обозначаются гека>од-столбцы, буквой х' (со штрихом) — вектор-строки, Таким образом, матрнчное уравнение Ах=Ь эквнвалентно множеству скалярных авненнй УР а'.х =Ьь 1= 1,, т, > где Ь вЂ” вектор длины т н Ь; — скалярная величина, являющаяся счй кампо. нентой вектора Ь. Матрнца, трапглониаованная по отношенню к матрице А, записывается как Аг, н определитель квадратной мзтрнцы обозначается через де!(А).
Через 1 обозначается единичная квадратная матрица, размерность кото- рой обычно ясна нз контекста. Она определяется следующим образом; [ 1, если 1=/, [ О в протнвном случае, Аналогично, О обозначает нулевой скаляр, нулевой вектор нлн нулевую матрицу в завнснмостн от контенста. Лля задания вектора х длнны п,с-я компонента которого равна хы нспользуется выражение х=.со](с>, ..., х4, нлн, когда это нс может вызвать недоразумений, х=(х,, х„,]. Вектор г длнны л+т, в котором первые л ком. понент совпадают с компонентами вектора х, а последующне т компонент совпадают с компонентами вектора у, задается выражением г=(х[у). П.2 Теория графов Графом 6 называется пара П=(У, Е), где У вЂ” произвольное навечное множество гершия н элементами множества Е являются подмножества мно.
жес>ва У мощностн 2, называемые ребрами. Вершины множества У обычно обозначаются иы о„.... Например, на рнс. П. 1 изображен граф П=((ос ис с>з, сг), ([и>, ие), )иы с'з! [с'з ог) [ос с>с) [ис, оз))). (Заметнм, что для обоэначення ребер используются квадратные скобки,) Иногда полезно рассматривать муяьтиграч>ы, т. е. графы с кратными ребрами (рнс. П. 2). Ориент>гроваяяым графом, нлн оргра4ом, называется граф, в котором каждому ребру приписано направленне.
Формально орграфом Р называется пара 0=(У, А), где снова У вЂ” пронзвольное множество вершнн н А — множество упорядоченных аар вершка, называемых дугами, т. е. А с= У>сУ. На рнс. П. 3 изображен орграф П вЂ” ((ос. оэ из "4) ((ис ое) ("г "з) (ис из) ("с, ис), (иы ог), (ос, оз))). Если П=(У, Е) — яекоторый граф н а=[и„из)ЕЕ, то мы говорим, что вершнна о, смежна с иг (н наоборот) н что е ияцидгятяо ос н о,. Степенью вершины о графа О называется число ребер, ннцндентных о, Таким образом, в графе на рнс, П. 1 степень вершины и, равна 3.
А(ори>рутом в 0 называется последовательность вершин ш=[ос, из, аз, ...,оз], у~1, такая, что оП суэс) ~ Е прк )=1, ..., Ь вЂ” !. Маршрут замкнут, если Ь>! н из=и,. аршрут без повторяющихся вершин называется цепью, нлн путем; замкнутыЙ маршрут, в котором никакие вершнны„кроме первой н последней, не повторяются, нааывается циклом. Например в графе на рнс. П,1 [и,), [о„ из,из, и,, ос, ос), [ис, оя из, ис! н [иг. из, сс! асе суть маршруты; второй н тре. тнй замкнуты, первый н четвертый являются цепями, н третий является цнклом.
Длина цепи [и„, из) равна Ь вЂ” 1, длина цикла [и,, ..., из= и,) равна Ь вЂ” 1. Степенью захода вершнны о в орграфе 0=(У, А) называется число дуг вида (и, о), содержащихся в А; аналогично, степенью исхода вершины о называется число дуг в А вида (и, и) Можно легко расшнрнтьданные выше определенна на орграфы.
Последовательность ш=(и„оз, ..., гь) вершин нз У называется Гл. 1. Задачи оптимизации оРивитиРованиым маРтРУтом в В, если (им иу+,) ~А пРи 1=1, ..., й — 1. Кроме того, если й>1 и из=и„то маршрут и является замкнутым. Ориентированной цепью в О называется маршрут без повторений. Замкнутая ориен. тировапная цепь называется ориентированным циклом. Длина ориентированной в, г в> вг г, Рис.
П.1. Граф. Рис. Плй Мультиграф. Рис. П.З. Орграф, цепи, или цикла, определяется аналогично неориентированному случаю, (Заметим, что мы всегда используеч квадрагные скобки для ребер графа и круглые скобки для дуг орграфа.) Пусть В =(йу, Е) — граф, обладающий следующим свойством. Множество вершин йг можно разбить па два множества, У и У, гак, что каждое ребро в) и О Рио.
П.б. Дерево. Рио. П.б. Лео. ь, Рио. П.4. Двудольный граф. иэ Е будет иметь одну вершину в у и одну вершину в (1 (рис. П. 4). В этом случае В называется дву)альным гра4юм и обычно записывается в виде В=(у, У, Е). Нв все графы обладают таким разбиением. Следующее предложение дает критерий для существования такого разбиения. Предложение 1. Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. Другим интересным классом графов является класа деревьев, Граф пазы. вас гся связным, если между любыми двумя вершинами в нем имеется цепь. Приложение. Терминология и обозначения 27 Дерево 0=(У, Т) — это связный граф без циклов.
Пример дерева показан на рис. П. 5. Лес — это множество верщинно не пересекающихся деревьев Е= =((Уз ТП ., (Ую Та)] (рис. П. 6) Мы часто будезз говорить, что дерево (У, Т) стягивает множество его вершин У или что оно является вставным деревом на У. Аналогично,лес Е=((Уз, Тз), „(Уа, Та)) стягивает Уз(] Уз(]... () Уа Предложение 2. Пусть 6= — (У, Е) — некоторый граф. Тогда следующие условия эквивалентны. 1. 0 является деревом. 2. 0 — свизный граф с ( У ] — 1 ребрами, 3. 6 не содержит циклов, но при добавлении произвольного ребра к 6 в нем появляется единственный цикл.
Мы будем часто рассматривать взвешенные графы, т, е. графы 0 = (У, Е) вместе с функцией гг из Е в Я (обычно только Я+; иногда вместо Я может 7(и, ») (и, ») Рис. П.8. Поток величины 5 для сети, изображенной на рис. П.7. Рис. П.7. Сеть. быть /7+, например, если веса представляют евклидовы расстояния]. В оп. ределенных случгях будут использоваться более мнемонические обозначения для весов, такие, кзк с (для стоимосгей) или й (для расстояний) '). Мы будем обозначать вес ребра (и, о] через щ (и, о] или ю» .
Отметим, что симметричную мазнрнци расстояний (НП] размера лхл (вспомните примеры 1,1 и 1,2) можно также рассматривать как взагзигнный полный гра4 6=((о„..., о„), К„) где К»=((оь о ]; 1~)с /~л]. Сеть Аз=(з, /, У, А, Ь) — это орграф (У, А), в котором выделены исток зЕУ со степенью захода О н сток )ЕУ со степенью исхода О и лля каждой дуги (и, о) ~А задана граница (илн пролускнан способность) Ь(и, г) ~Я+ (рис. П. 7). Потоком / в Аз нааывается вектор в Кчл~ (по одной компоненте ди, о) для каждой дуги (и, г) ц А), такой, что Величина потока /, иногда обозначаемая через ]/], определяется слелующей формулой; ]/]= а)э, »зал / (з, и).
Наприззер, на ркс. П. 8 изображен правиль. ный поток для сети АЗ, величина которого ]/]= 5. '). Сокращения от английских слов соЫ и й)з(апсе,— Прим, лерга. 1. О ~/(и, г)»з Ь (и, о) лля всех (и, г)~А; 2. ~ /(и,о)=хг /(о,и) аля всех гцУ вЂ” (з, /). З», »зеЛ З», »ЗЕЛ (з, »з) (з, »з) (»з, »з) (»з, »з) (»з, »л) (з'4 з) (»з з) 3 2 3 1 1 1 4 28 Гл. !. Задачи оптимизации П.з Упрощенный Алгол»1 Большинство алгоритмов в данной книге мы будем выражать посредством нашей версии Упрощенного Алгола. Чнтатеян, знакомые с языками Паскаль, Алгол или ПЛ!1, смогут легко понять алгоритмы на этом языке.
Для остальных на первых порах достаточно ознакомиться сданным параграфом н проввить усердие. Упрошенный Алгол надо рассматривать скорее как неформальную зались, нежели язык програмчнрованкя высокого уровня. Основной единицей алгоритмов в Упрощенном Алголе является оператор, Операторы бывают нескольких типов. !. Оператор присгаиганит переменная: =выражение Мы допускаем запись вида !)!=(з) н даже такие варианты, как пусть х любой элемент яз Ю ялн присвоить всем меткам значение 0 2.
Условный оператор: И услог»м !Ьеп оператор 1 е1зе оператор 2 Часть «е1»е опгритор 2» не обязательна (мы будем использовать это таким образом, чтобы не возвикалодвусмысленности). Типичными услогиями являются х > граница о = з впд результат = «да» (Замечание. ргзергироганныг слова Упрощенного Алгола мы выделяем жирным шрифтом.) 3. Оператор 1ог: 1ог список до оператор ! Здесь список содержит список параметров, для которых оператор 1 должен выполняться. Прнмеры; !ог (: = 1, 2, ...
и до А ((): = А [(+ Ц и 1ог все» ц 1', такие, что [о, а) ~ Е до гапй [о):=9 4. Оператор пы!е: пы)е ус»огне до оператор 1 Оператор 1 выполняется многократно до тех пор, пока выполняется условие, 5, Оператор лгргходо: йо !о метко Например, йо !о цикл означает, что следующнм должен выполняться (едннственный) оператор, начинающийся о метки «цикл». 6. Бло»«: Ьей1п оператор 1; оператор 2; опгратор й — 1; оператор ! епд Как правило, те, кто впервые столкнулся с языками типа Алгол, рассматривают после»вид оператор как какую-то хитрость, однако на самом деле все очень просто. Напомним, что в условном операторе после Рйеп золх<ен стоять единственный оператор, Но как быть, если мы хотим сделать что-нибудь " Термин Упрощенный Алгол введен в кинге: Ахо А., Хопкрофт Лж., Ульман !(ж.
Построение н анализ вычислительных загорят»юв — Мл Мнр, 1979, Приложение. Терминология и обозначения сложное (т, е. несколько операторов), если выполняется услозие? В таком случае зги операторы ставятся подряд, разделяются точкой с запятой к ограничиваются в начале и конце парой Ьей(п-епд. Чтобы облегчить чтение, соответствующим образом делаются абзацы, 11омните, что все операторы от оператора 1 до операаюра й могут быть операторамк лютого типа, от 1 .до 6. Если зсе они являются операторами присваивания или перехода, то мы иногда будем писать блок без Ьей(п — епд, разделяя операторы запятыми.
Например, (: =(+1, А](]: = й йо 1о цикл обозначает тоже, что Ьей(п (: =(+1; А ((]. '= й йо го цикл; епб 7. Комментарии: зги операторы имеют вид (сопппеп1: это комментарий). 8. Разнообразные операторы: мы будем допускать практически все, что читаемо н недвусмысленно. Например: построить вспомогательную сеть А(т((); увеличить текущее паросочетанне, используя цепь р. Симплекс-алгоритм 2.1 Формы задачи пииайиого программироааиия Определенная в предыдущей главе задача линейного программирования была поставлена не в самом общем виде. В ограничениях наряду с равенствами можно было бы допустить и некоторые неравенства и рассматривать наряду с переменными, которые должны быть неотрицательны, переменные без ограничений н)~ знаки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
