Дискретно-непрерывная математика (стр. 81 )

Допустим, что требуется объединить несколько элек­тростанций vi

(i=l, 2, ..., п) в систему так, чтобы при необходимости в моменты перегрузок можно было поль­зоваться энергетическими запасами любой из них. Пусть каждая станция vi (i= I,..., п) в зависимости от ее раз­мера и потенциальных возможностей должна быть непосредственно связана, по крайней мере, с di дру­гими станциями. Стоимость прямого соединения раз­личных станций vi и vj выражается действительным числом cij.

Задача объединения электростанций состоит в том, чтобы спроектировать систему связей, имеющую мини­мальную общую стоимость и удовлетворяющую требо­ваниям по di для всех станций. Очевидно, она эквива­лентна следующей задаче теории графов. Дан полный граф с вершинами vi (i= 1.....п) и весами cij, приписан­ными каждому ребру eij, соединяющему vi и vj. Требу­ется найти подграф, имеющий минимальную взвешен­ную сумму ребер, степень вершины vi которого, по край­ней мере, di. Можно также искать подграф, имеющий максимальную взвешенную сумму ребер, каждая вер­шина которого имеет степень не больше п—di—1, а за­тем взять дополнительный граф. Видно, что при таком подходе исходная задача требует использования обоих обобщений задачи о максимальном паросочетании, рас­смотренных в конце раздела 5.14.

В частном случае, когда вершины раделены на два класса так, что каждое ребро, соединяющее пару вершин одного и того же класса, имеет вес, равный нулю, зада­ча объединения станций сводится к транспортной задаче. В общем случае, теория решения этой задачи значитель­но сложнее, чем транспортной.

Задача объединения электростанций или общая задача определения оптимального подграфа с ограничен­ными степенями вершин по существу связана с боль­шинством экстремальных комбинаторных задач, для ко­торых известны хорошие алгоритмы решения. Эти алго­ритмы хороши в том смысле, что объемы вычислений при их применении растут как степенные функции при увеличении размерности задачи. В случае, когда все di=2, мы получаем задачу, очень близкую к задаче коммивояжера. Действительно, небольшая модификация алгоритма объединения станций дает минимальный взве­шенный подграф со степенями вершин, равными 2. Если этот подграф связен, то мы получим минимальный мар­шрут коммивояжера при длинах ребер cij.

5.20. Печатные схемы

Печатная схема представляет собой электрическую сеть, образованную соединительными проводами, нане­сенными печатным способом на одной или нескольких плоских поверхностях изоляционного материала. Чаще всего она наносится с двух сторон пластмассовой платы. Соответствующие соединения между проводниками, рас­положенными с разных сторон платы, делаются с по­мощью проволочных перемычек, проходящих через от­верстия в плате. Так как печатные проводники не изо­лированы, то они не должны пересекать друг друга (кроме специально заданных точек).

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

При таких ограничениях не всякая сеть может быть отпечатана на двух сторонах платы. Ранее было показано, что обыкновенный граф G и его дополнения не являются плоскими графами, если G имеет девять или более вершин. Таким образом, полный (обыкновенный) граф, имеющий девять вершин, нельзя отпечатать, на заданной плате, так как это означало бы, что некоторый подграф G (часть сети, отпечатанная на одной стороне) и его дополнение (часть, отпечатанная на другой сто­роне) являются плоскими.

Если допускаются дополнительные отверстия и любые перемычки через плату, то в этом случае можно отпеча­тать любую сеть. Можно, например, начать с вычерчи­вания сети на плоскости таким образом, чтобы самое большее два провода пересекались в любой точке, ко­торая не является заранее заданным узлом. После этого сеть почти полностью можно отпечатать на одной сто­роне платы, а в каждом месте пересечения, где не должно быть соединения проводов, один из проводов с по­мощью двух отверстий и перемычек должен быть про­пущен на другую сторону и частично отпечатан на этой стороне. Таким образом, на одной из сторон платы от­печатываются только небольшие участки проводов. Граничные оценки на число такого типа пересечений проводов даны в разделе 5.7.

Предположим теперь, что требуется отпечатать данную сеть при минимально возможном числе дополни­тельных отверстий в плате (не считая отверстий в вер­шинах). Любой способ печати схемы можно изобразить, вычертив есть на плоскости, используя для этого два типа дуг. Жирными линиями можно показывать, на­пример, дуги, располагаемые на одной стороне платы, а тонкими линиями — дуги, располагаемые на другой стороне.

Задача может быть теперь переформулирована та­ким образом: найти наименьшее число дополнительных вершин степени 2 (соответствующих точкам, в которых провод перейдет с одной стороны платы на другую) и изобразить граф таким образом, чтобы в любой точке, отличной от узла, пересекалось самое большее два ребра и эти ребра были различных типов. Естественно каждое ребро должно изображаться линией одного типа (жир­ной или тонкой),

ЕСТЕСТВЕННЫЕ НАУКИ

5.21. Идентификация в химии

Одна из основных задач теории графов состоит в нахождении хорошего алгоритма для определения того, являются ли два конечных графа одинаковыми в абст­рактном смысле или, в более общем случае, является ли один граф подграфом другого. Первая задача называ­ется задачей идентификации графа, а вторая — задачей идентификации подграфа. Чтобы формулировка задачи была более четкой, слову «хороший» нужно придать некоторый математический смысл. Будем считать, что алгоритм является «хорошим», если объем вычислений связанных с его применением для любой пары графов, растет в худшем случае как степенная функция, а не экспоненциально с ростом числа ребер в выбранной па­ре графов.

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

Существование нескольких видов атомов не вносит серьезных трудностей в задачу идентификации. В на­стоящее время много внимания уделяется разработке «эвристических» алгоритмов химической идентифика­ции — алгоритмов, не являющихся «хорошими» в нашем смысле, но хорошо работающих на практике. Для хи­миков важно не только решить задачу идентификации структур, но гораздо более интересно найти удобную систему каталогизации химических препаратов так, что­бы любой препарат можно было легко найти в каталоге или внести туда.

Алгоритм идентификации деревьев использует ката­ложную систему, построенную на основе линейного упо­рядочения множества всех конечных деревьев. Однако наличие такой системы совершенно не обязательно. Например, существует хороший алгоритм для опреде­ления идентичности (в комбинаторном смысле) любых двух поверхностных карт. Карты обладают свойством комбинаторной «жесткости» — так, что если карты M1 и М2 идентичны и установлено, что ребро е1 в М1 иден­тично ребру е2 в М2, конечная точка v1 ребра е1 иден­тична с конечной точкой v2 ребра е2 и грань f1, содержа­щая е1, идентична с гранью f2, содержащей е2, иденти­фикация оставшихся частей M1 и М2 однозначна и легко устанавливается. Таким образом, для того чтобы уста­новить идентичность карт М1 и М2, необходимо только идентифицировать ребро е1 в М1 с каждым ребром М2 четырьмя способами, соответствующими каждому воз­можному способу идентификации вершины v1 и грани f1 в М2. Из такой процедуры, конечно, непосредственно не следует система каталогизации карт.

Упомянутое выше свойство «жесткости» можно ис­пользовать для определения идентичности деревьев Т1 и Т2, а также идентичности их способа изображения на пло­скости. Под идентичностью способа изображения мы бу­дем понимать, что для каждой пары взаимно идентич­ных вершин v1 в Т1 и v2 в Т2 ребра, которые пере­секаются в v1 в изображении T1, располагаются вокруг v1 в том же самом порядке, в каком идентичные ребра расположены вокруг v2 в изображении дерева Т2. Раз­личные способы изображения одинаковых деревьев Т1 и Т2 обычно усложняют проверку на идентичность, а число различных способов изображения дерева, вообще гово­ря, растет экспоненциально с числом ребер в дереве.

Можно считать, что алгоритм идентификации деревьев есть процедура приведения деревьев к канони­ческому виду.

Напомним, что корневым деревом является дерево, в котором одна из вершин, в отличие от других, назы­вается корнем. Алгоритм идентификации фактически применяется к корневым деревьям. Поэтому опишем сначала хороший алгоритм приведения любого дерева Т к канонической корневой форме. Пусть Т0 есть дерево Т. Будем формировать Ti+1 из Тi вычеркивая из Тi все вершины степени 1 и инцидентные им ребра. Такой про­цесс продолжим до тех пор, пока не получим Тi, которое состоит только из одной вершины или одного ребра и его конечных точек. Процесс оказывается конечным для любого исходного дерева Т. Вершина или ребро, получаемые по окончании процесса, называются центром Т.