Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 49
Текст из файла (страница 49)
Таку1О сеть будем назь1вать г-Связной, Минимальньпг разрез в такой соти представляет собой множество узлов, которые имеют вид узлов ре1нетки в полосе ширины г, причем общий вес всех узлов равен общему весу полосы. >2.3. потоки в нкпгепьыпк>й сгклк 277 ь Болыио того, при г> ->- О, г — ~ О, — — О пределом этой полосы будет кривая с минималькыи значением ) >а (з, у) Ис. В построенной г-связной соти удаление всех узлов из иекото- рого горизонта:якого ряда пе разобьет соть па две части, так как в сети найдатся пара узлов, лежащих по разпыо стороны от этого горизонтального рида и связапиых дугой.
Чтобы прорвать >г~ поток ив Ь" в Т, нужно, например удалить все узлы пз ) — ! гори> )», >гг г воптальных рядов, где~ — ~ — ближайшео слева к — целое число. Ь Метод расстановки пометок для сети с пропускпыми способ- ностями узлов нозволяот найти ъпю кество узлов, образукицих мппималып>й разрез. Если этот иинпмальиь>й разрез удалить из сети, то сеть будет разбита на дне части. (В силу мипим >льпости разреза пикакоо его собственноо подмножество пе обладает этим свойствои.) Влоиентарпыо квадраты области находятся во взаимно одно- значном соответствии с узлахп> сети, поэтому подобласть, яв:нпо- щаяс» объодииепиом элементарных квадратов, соответствующих мииимальиому разрезу, должпа иметь свойства, апалогичпые свойстваи мпнимальяого разреза.
А имонпо, эта подобласть г-разбивает прямоугольную область иа две части, причем удалоиие хотя бы одного элементарного квадрата из этой области парушает это свойство. Здось под г-разбиепием области попимаотся сле- ду>ощее. Область считается г-разбигаой на дее части, если не существует пары элемектарпых квадратов, лежащих в разных частях области, расстояние между центрами которых мепыпе или равно г.
Возпикаот вопрос: что будет пределом этой подобласти при л л-«- О, — — «-О? Ответ здесь такои:полоса ширины г, заклк>чеп- ная между сторонами Л и В области. Так как г зиачителыю больше, чеи Ь, то квадратов, ложащих целиком внутри полосы ишрины г, будот зпачптельпо больп>е, чом квадратов, лен ащих лишь частично внутри пое.
Квадраты, лежащие цоликон впутри полосы, будем пазывать внутренними, а квадраты, лежащие лишь частпчпо впутри полосы,— граппч- пьы>и. Если весовая функция обладает свойстваии, сформулиро- ваппыии ии>ке в 4 12.4, то общий вес внутренних квадратов на порядок превьппает общий вес гракпчиых квадратов, и при атом общий вес подооласти, соответствувицей узлам миппмальл ного разреза, в предела при — -«. О стремится к несу полосы н>и- рины г. гл. <3. потоки н неп<'игь>виой сок;и< 12.4.
> -разделяющее множество В этом параграфе обсу>кда<отся некоторые свойства пепрерь>нных мипимальнь>х разрезов (Гоморп, Ху (02]). Заметим прежде всего, что мы ограничимся рассмотрением точек двумерной прооктннпой плоскости Ве. Дне точки а и Ь из >шожестна Р будам называть г-соязанными, если существуот конечная последовательность точек рь — — а, р<,..., ро -- Ь, где р; Е Р, а расстояпио р (р Р>з-<) (~ г (' .= О,..., п — 1).
Подробное об этом см. (102). Дне точки а и Ь из мпо>кестна Р будем называть г-раэделеипыми, если опи пе янляются г-связанными. Задача состоит в пахождепии такого множества С, удалепие которого из плоскости Вн сделает точки а и Ь г-разделенными н Вх — С. Ьолее точно будам говорить, что множество С ~ А, янчиется г-ра<>делающим точки а и Ь, если 1) ешожество С за><кнута и огракичепо; 2) точки а и Ь пе прииадлежат С; 3) точки а и Ь являл>тся г-разделепнымп в Ве — С. Лри таком опроделепии любое достаточно больпюе ико>кестно будет г-разделяющим. Однако если потробонать, чтобы мпожоство С было неприеодимим, т.
е, таким, что его собственные подмножества уже не являются г-разделяющими, то мцожество С будет обладать вполне определеппой структурой. В дальнейшем символом С мы будем обозначать пепринодимое г-разделяющео мпо>кество. Заметим, что пеприводимое г-разделяющее множество аналогично разрезу н непрорыв»ой среда, а точки а и Ь аналогичны источнику и стоку. Сформулируем несколько тоорем, касающихся пепринодимых г-разделяющих мш>жеста. Доказательство их можно найти в работе Го><ори и Ху (92). Будем использонать следующио обозначения: С вЂ” попринодимое г-раздели>о>цее множество (опо замкнуто по опроделепи>о); Л вЂ” >п>оя<естн<> точек, г-снязаппых с точкой а (это открытое мно кестно);  — мпожество точек, г-связанных с точкой Ь (это также открытое множество); В --.
Н, — Л вЂ”  — С (это открытоо множество). Тконкмл 12.1. Каждое г-раздеяя>ощее мпожестоо содержит яеприподимое г-разделя<ощее множеппоо. Твоэвма 12,2. 11усть р — точка из С. Тогда р (р, А) ( г по(р, В)(г. 279 ~ л. ы кздклшощкк множество :!кммк 12.1.
Пусть р~рг и о,дг — два отрезка, каждыи из которых илгеет длину, не большую чем г, и пусть р — точка их пересечения. (Другимв словомн, р,рг и ц,с(г — диагонали некоторого четырехугольника.) Тогда найдется вершина четырехугюп ника (р,, рю д, или ц,), у которой обе инцидентные еи стороны ил~еют длину, не большую чем г. !(усть р„ р,, ..., р„ — последовательность таких точек, что р (р;, ры,) ..-', г. Тогда говорят, что последоватольность отрезков 1~~Р~ Ргрг.
. образует г-свягывоюи(ую цепь. Такая г-свнзывак>- щан цеш называется простой, если каждая вершина р; (кроме р, и р„) припад:шжиг двум звеньям — р;,р; н р;рнн а вснкая другая ~очка отрезка принадлежит только одному звену. б!кммк 12.3. Нели существует г-связывающая цепь, то существует и простая г-свягываюи(ая цеш.
'! кои кык 12.3. Вели С вЂ” иеириводимое г-рагделяющее множество, то Нг — С = А О В (другими словами, множество О пусто). Заметим, что теорома 12.3 очень похожа па нзвестнук> теорему )Кордапа о замкнутой кривой, согласно которой всякая простая (не имеющая самоперосеченпй) замкнутая крнван С разделяет точки плоскости Лг, не принадлежащие С, на такие два открытых множества Л и В, что:побая пара точек в каждом из этих мноокеств может быть связана кривой, не пересекающейся с С. Согласно теореме 12.3, всякое неприводимое г-разделяющее множество С г-разделяет плоскость 11, на такие два открытых множества А и В, что любая пара точок в каждом из этих мпо;кеств может быть г-связана попью, не имеющей общих точек с С.
Каждое нэ множеств А, В можот состоять из нескольких односвязных открытых множеств, называемых компонентами множества А или В. Ткогкмк 12А. Каждая компонента множесгпва А или В равномерно локально свяэна, а граница каждой иэ компонент является прошлой кривой Жордана. Таким образом, граница множества С является ооъедипеннем простых кривых Жордана.
в!ожпо показать, что любое множество С состоит пз частей слодуюп!нх двух типов. Части 1-го тнпа— по:нюы ширины г (как полосы С, н С, на рис. 12.6). Части 2-го типа — выпуклые многоугольники с четным числом сторон, д;пена каждой из которых равна г (как у многоугольника Р па рнс. 12.6). Для наглндпостп можно представлнть себе, что пепрнводиыое множество С, частямн которого нвляется С~, Сг„(', имеет вид самопересекахнцейся полосы, а многоугольник р — это как раз гл.
<з. потоки п игпек!'ывиой сеида 2ЯО область самопоросечепия, добав:нише которой (одип раз) к мно;кестваи С, п С. по пару!пас! свойства пеприводизн<сти множества С.,(юбое мпо<кество С является объ<дииоппех! мио<кеств указаппых двух типов. Если весовая функция га (х, у) произвольиа, то;по<бас иепрпводимоо г-разделяющео мпо'коство легко можно сделат! разделяющим мпожоством с минимальным весом, положив ю (х, у): е ° а << ! Р н с. 12Я. в этом иопрпводимом множестве, а за его преде.тами взяв ю (х, у) достаточно болыиим. Заметим, что па рис.
12.6 длина отрозкв ру, мопыпе г. !(сотому ооласти Л! и Л, г-связаиы с точкой а и Л вЂ” — Л,(<<Л . й(по<кество точек В, г-связанных с точкой Ь, состоит из точек, зак:почеппых виутрп палась!. ()олега, изобраи;сипая па рис. !2.6. будет обладать минимальным несом, ес.<и весовая фуикиия достаточпо велика в Л и В, п мала внутри полосы. ))а рис. 12,7 пзоорв;к<по другое <юириводичое мпо кество, г-раз;идяк<ще< точки а и !!. 12.1. РРАЗДКЛНЮЩИЕ МНОЖКСТВО ЗВ1 Возиикаот вопрос: какоо из 2-х множеств, изображеииыл на рис. 12.6 и 12.7, обладает мьмиы»альным весом? ~)то зависит от того, что мс ньшс — Вос полосы иа рис.
12,0, закгпочеииой между отрезками р»р» и рзр;, или вос области р,р,рзр', па рис. 12.7. Обозначим через ()*, площадь пол»»сы, зак:ночеиной между отрезками р»р» 'с рзр» иа рис. 12.6, а через ч),"' — и:и»щадь области р,р»р,р', иа рис. 12.7. Отиоиюпие ()Я", ограпичепо сверху, так ° и .42 Р и с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
