Введение в прикладную комбинаторику, Кофман А. (984071), страница 34
Текст из файла (страница 34)
В зт С ° и ! '-Ф'-'"- -- ' Р Рис. 222. ге Р Рис. 228. Например, с графом на рнс. 222 можно связать груды (Л, гз гзз', гз!!', гз!!Ь, гз!)', гзз гз гза, гз Л гв, гв!', гв, Л) (48. 12) (на рис. 223 изображены ее состояния), (Л, гв гвз! гв гв! гв!е, гв! гв!Ь, гв!Ье, гв!Ь, гв1, гв, Л), (48.13) (Л, гз, гзЬ, гзЬ1, гвЫ1, гвйз', гзЬ, гм Л), (48.14) (Л, г„г,с, гп гзЬ, гн Л, гз, гзд, г„Л, гв, гв1, гв, Л), (48,15) Запись (48.12) с помощью вершин такова: (Л, РАДА АС, ЯА АС СН, ЯА АС СН НА, НА АС СН, НА АС, ЯА, НА АЕ, ИА, Л, НР, КР РО, НР, Л). (48 16) Груда, построенная на вершинах графа. Такую груду А =(ув, уь ..., у,) на множестве вершин Е графа б =(Е, Г) можно построить последовательно. а) Пусть уз з = Л. Тогда либо уз ~ — последнее состояние груды, либо можно образовать состояние ун используя неко- торую вершину Л со входом, не меньшим з (! будет ее входом).
б) Пусть у; з вь Л и Х вЂ” его пик. Тогда имеем три воз- можности: 1) (! — 1) — выход У~ Е. Если в ГХ наряду с У есть эле- мент Х, не использовавшийся до этого момента при образова- нии нового состояния из состояния с пиком Х, то образуем со- 268 Рис 225 стояние уь либо используя Я (1 будет его входом), либо выбрасывая Х (1 будет выходом Х); если такой вершины Х не существует, то остается последняя возможность, 2) (1 — !) — первый вход Х. Если ГХ = 8, то образуем уь выбрасывая Х (1 будет выходом Х). Если ГХ ~ 8, то образуем уь беря некоторый элемент из ГХ (1 будет входом этого элемента).
Н 3) (1 — 1) — другой вход Х. В этом 1 случае образуем уь выбрасывая Х 3 (1 будет выходом Х), Такую груду можно получить непосредственно из груды, построенной на А ь" дугах графа, если из ее состояний (записанных с помощью вершин) выбросить К Возможен и обратный пере- Е Г ход, если подходящим образом ввести Я в состояния груды, построенной на вершинах.
Например (см. рис. 222 — 224), грудам (48.12) — (48.15) отвечают соответственно (Л, А, АС, АСН, АСНА, АСН, АС, А, АЕ, А, Л, Р, РО, Р, Л), (48.17) (Л, Р, РА, Р, РО, РОС, РО, РОВ, РОВО„РОВ, РО, Р, Л), (48.18) (Л, Н, НА, НАС, НАСН, НАС, НА, Н, Л), (48.19) (Л, 6, ОС, 6, ОВ, 6, Л, 1, (Н, (, Л, Р, РО, Р, Л). (48.20) Приложение понятия груды к изучению прадеревьев. Ветвящаяся структура часто встречается в кодировании, задачах выбора, при анализе, хранении и поиске информации. Г Семейством ветвящегося графа 6 = = (Е, Г) назовем множество его корней или непустое множество ГХ.
Упорядочим и ветвящийся граф, вводя отношение порядка на Е так, чтобы каждое семейство было цепью (в смысле теории структур), а никакие два элемента различ- В ных семейств не были сравнимы. Любому ветвящемуся графу можно сопоставить простые груды. Если фиксировать введенный ранее порядок, то такое сопоставление однозначно. Метод построения груды, указанный выше, в случае прадеревьев упрощается, так как пустыми ее состоя- виями могут быть только первое и последнее. Легко получить из ветвящегося графа прадерево, вводя корень )с и связывая его с корнями этого графа. Рассмотрим пополненный 269 ветвящийся граф на рис. 225.
Упорядочим его следующим образом; у (й') (А, В), у (А) = Я, у (В) = (С, О), у (С) = Я, у(6) =(Е, Р, 6), у(Е) =Я, у(Р) =У, у(6) =Я. (4821) Такому порядку отвечает груда (Л, В, ЛА, Д, РВ, КВС, ЛВ, ЯВВ, КВОЕ, ВВ0, АВВЕ, ЯВВ, КВ06, РВЕ), КВ, Р, Л). Любой элемент из Е обладает одним и только одним входом; порядок появления элементов в груде называют порядком входа в груду. Аналогично определяется порядок выхода из груды. Для графа на рис.
225 имеем порядок входа: А, В, С, 6, Е, Е, 6; порядок выхода: А, С, Е, Р, 6, 6, В. С помощью так введенной груды легко решить следующие задачи. 1) Отыскать точки, предшествующие заданной. 2) Определить семейства ветвящегося графа. 3) Построить таблицу расположения вершин ветвящегося графа. Такая таблица состоит из трех столбцов. В первый помещаются вершины в порядке их входа в груду; во второй— первый элемент Х' из у(Х), если у(Х) Ф И; в третий — элемент Х", следующий за Х в его семействе. Приведем такую таблицу для графа на рис.
225: в с х х' х" 4) Отыскать миноранты заданного элемента; любое состояние а~ груды — путь графа, начинающийся в корне и оканчивающийся в пике аь Понятие груды можно использовать также в некоторых случаях для получения транзитивного замыкания н элементарных путей графа. ГЛАВА Ч ОПТИМИЗАЦИЯ 9 49.
Введение Комбинаторные задачи, встречающиеся в различных областях знания, часто приводят к проблеме оптимизации. Пусть дан критерий, позволяющий выделить решения с некоторыми заданными свойствами. Требуется найти множество таких решений, называемых «оптимальными». В большинстве задач этот критерий имеет числовую природу, а множество всех решений разбивается на вполне упорядоченные классы. Мы будем в основном рассматривать задачи на максимум и минимум. В основе почти всех комбинаторных методов оптимизации лежит следующий принцип, Множество всех решений разбивается некоторым образом на два подмножества: подмножество, содержащее все оптимальные решения, и подмножество, не содержащее их.
Если первое из подмножеств не есть оптимальное, то стремятся получать подобные разбиения, в которых подмножества, содержащие все оптимальные решения, имеют все меньшую мощность. Действуют так до тех пор, пока не приходят к оптимальному подмножеству. На этом же принципе основаны также некоторые способы, позволяющие получить по крайней мере одно оптимальное решение.
Вопросами оптимизации стали интенсивно заниматься лишь в последнее время. В педагогических целях мы получаем алгоритмы, позволяющие действовать вручную; некоторые из них непосредственно, а другие — после соответствующей модификации могут быть использованы при вычислениях на ЭВМ. Чтобы решать задачи с большим объемом вычислений в приемлемое время, многие алгоритмы требуют дальнейшего усовершенствования. 9 50.
Числовая функция на графе Числовая функция на вершинах графа. Пусть задан граф О = (Е, Г). Говорят, что на вершинах графа реализуется числовая функция, если каждой вершине Х1 ~ Е ставится в соответствие число Ц = ~р(Х;) из некоторого множества Е. 271 Например, для графа на рис. 226 имеем ф(А)=а, ф(В) = 5, ф(С) =с, ф(Р) =с(, ф(Е) =е, ф(Е) =1. (50.1) Значение пути через вершины. Пусть на 1. задан внутренний бинарный ассоциативный закон и. Значением пути (Хь Хм ..., Х„) через вершины называют число х, «х, * ... » х„, где х; = ф(Х;), и записывают Л(Хп Хм ..., Х„) =х, *х,* ... эх„. (50.2) Например, для графа на рис.
226 и множества 1. = й+, Рис. 22Л Рис. 226. если принять за закон композиции сложение, имеем Л(Р, Е, Е, А) =с(+ е+ 7+ а. (50.3) При рассмотрении значения контура всегда фиксируется начало (во избежание многозначности). Максимальный (минимальный) путь через вершины. Обозначим через Р подмножество путей графа 6= (Е, Г) с некоторым свойством,У. Максимальным (минимальным) путем через вершины, принадлежащим Р, назовем путь с максимальным (минимальным) значением Л. Очевидно, что таких путей может быть несколько. Например, пусть для графа на рис. 227 функция ф такова.
ф(А)=5, ф(В)=3, ф(С)=8, ф(Р)=3, ф(Е)=0, ф(Е)=7; (50.4) закон композиции — сложение, а свойство Р— «быть элементарным путем длины 3 с началом в Вгн В силу (43.3) Л(В, С, Е, А) =3+8+7+5=23, Л(В, Е, Е, А)= — 3+0+7+5=-15, Л (В, Е, Р, С) = 3+0+3+8 = 14, Л (В, С, Е, Е) =3-(-8+7+0=18, Л(В, А, С, Е) =3+5+8+7=23, Л(В, Е, Р, Е) =3+0+3+7=13.
(50.5) 272 Пути (В, С, г, А) и (В, А, С, Е) максимальные, а путь (В, Е, Р, Р) минимальный. Числовая функция на дугах графа. Пусть задан граф 6 =(Е, ()), Говорят, что на дугах графа реализуется числовая функция, если каждой дуге (Х„Х,) ен (3 ставится в соответствие число рп = ((Хь Х~) из некоторого множества М. Рис. 229. Рис. 228. Значение пути через дуги. Пусть на М задан внутренний бинарный ассоциативный закон *.
Значением пути (Х~Р Х~,,..., Х~ ) через дуги называют число о~, » о~ ~ «... * о~ где оп = Г(Хь Х,), и записывают р(Х~ Х~ ... Хс ) о' ~ «о~ ~ «о~ ~ (50,7) Например, для графа па рис. 228 и множества М = К, если принять за закон композиции умножение, имеем р (Л, В, С, Е) = а, аеакь (50.8) Максимальный (минимальный) путь через дуги. Обозначим через Р множество путей графа Р =(Е, П) с некоторым свойством У. Максимальным (минимальным) путем через дуги, принадлежащим Р, назовем путь с максимальным (минимальным) значением р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
