Параллельно-последовательный граф (Hgjgllyl,uk-hkvly;kfgmyl,udw ijgs)

В теории графов параллельно-последовательные графы — это графы с двумя различными вершинами, которые называются терминальными, образованные рекурсивно с помощью двух простых операций^[1]. Эти графы могут быть использованы для моделирования последовательного и параллельного соединения электрических цепей.

Определение и терминология

В данном контексте понятие граф подразумевает мультиграф.

Существует несколько способов определения параллельно-последовательных графов. Следующее определение, в основном, базируется на определении Дэвида Эппштейна^[англ.]^[2].

Графом с одной терминальной парой (ОТП) называется граф, у которого помечены две различные вершины s и t, называемые источником и стоком соответственно.

Параллельное соединение Pc = Pc(X,Y) двух непересекающихся ОТП графов X и Y — это граф с одной терминальной парой, созданный объединением графов X и Y при помощи слияния источников X и Y с образованием источника Pc и слиянием стоков X и Y с образованием стока графа Pc.

Последовательное соединение Sc = Sc(X,Y) двух непересекающихся ОТП графов X и Y — это ОТП-граф, созданный объединением графов X и Y путём слияния стока X с источником Y. Источник графа X становится источником Sc, а сток графа Y становится стоком Sc.

Параллельно-последовательный граф с одной терминальной парой (ППОТП граф) — это граф, который может быть получен в результате последовательных и параллельных соединений множества копий однорёберных графов K₂ с назначенными терминальными вершинами.

Определение 1. Граф называется последовательно-параллельным, если он ППОТП и две его вершины помечены как источник и сток.

Аналогичным образом можно определить последовательно-параллельные орграфы, которые строятся из копий ориентированных графов с одной дугой, и в этом случае дуга направлена из источника в сток.

Альтернативное определение

Следующее определение даёт тот же класс графов^[3].

Определение 2. Граф является последовательно-параллельным, если он может быть преобразован в граф K₂ с помощью последовательности следующих операций:

Заменяем пару параллельных рёбер одним ребром, сохраняя общие конечные вершины
Заменяем пару рёбер, инцидентных ребру степени 2 одним ребром.

Свойства

Любой параллельно-последовательный граф имеет древесную ширину и ширину ветвления, не превосходящие 2^[4]. В действительности граф имеет древесную ширину не более 2 тогда и только тогда, когда он имеет ширину ветвления максимум 2, а также тогда и только тогда, когда любая двусвязная компонента является параллельно-последовательным графом^[5]^[6]. Максимальные параллельно-последовательные графы, графы, к которым нельзя добавить дополнительные рёбра без разрушения последовательно-параллельной структуры, — это в точности 2-деревья^[англ.].

Параллельно-последовательные графы характеризуются отсутствием подграфа, гомеоморфного графу K₄^[4].

Параллельно-последовательные графы могут быть охарактеризованы их ушным разложением^[2].

Исследования, вовлекающие параллельно-последовательные графы

Параллельно-последовательные графы могут быть распознаны за линейное время^[7] и их параллельно-последовательные разложения могут быть построены также за линейное время.

Кроме моделирования некоторых типов электрических цепей, эти графы представляют интерес в теории вычислительной сложности, поскольку много стандартных задач на графах решаются в линейное время на ОТП-графах^[8], включая поиск максимального паросочетания, максимального независимого множества, минимального доминирующего множества и гамильтонова дополнения. Некоторые из этих задач для графов общего вида NP-полны. Причиной этого является факт, что если ответы для этих задач известны для двух параллельно-последовательных графов, то можно быстро найти ответ для их последовательных и параллельных соединений.

Задача о последовательно-параллельных графах^[англ.] относится к вопросу перечисления графов и спрашивает о числе параллельно-последовательных графов, которые могут быть образованы из заданного числа рёбер.

Обобщения

Обобщённые параллельно-последовательные графы (ОПП-графы) — это обобщение параллельно-последовательных графов^[9], при котором графы имеют ту же алгоритмическую эффективность для упомянутых задач. Класс ОПП-графов включает параллельно-последовательные графы и внешнепланарные графы.

ОПП-графы могут быть определены добавлением в Определение 2 третьей операции удаления висящих вершин (вершин степени 1). Таким же образом к Определению 1 можно добавить следующую операциию.

Слияние источников S = M(X,Y) двух ОТП-графов X и Y — это ОТП-граф, созданный из непересекающихся графов X и Y путём слияния источника X с источником Y. Источник и сток графа X становится источником и стоком P соответственно.

SPQR дерево — это структура, которая может быть определена для произвольного вершинно 2-связного графа. Структура имеет S узлов, аналогичных последовательному соединению в параллельно-последовательных графах, P узлов, аналогичных параллельному соединению параллельно-последовательных графов и R узлов, которые не соответствуют операциям параллельно-последовательных графов. 2-связный граф является параллельно-последовательным тогда и только тогда, когда нет R узлов в дереве SPQR.

См. также

Примечания

↑ Свами, Тхуласираман, 1984, с. 150, Упражнение 7.10.
↑ ¹ ² Eppstein, 1992, с. 41–55.
↑ Duffin, 1965, с. 303–313.
↑ ¹ ² Brandstädt, Le, Spinrad, 1999, с. 172-174.
↑ Bodlaender, 1998, с. 1–45.
↑ Hall, Oxley, Semple, Whittle, 2002, с. 148–171.
↑ Valdes, Tarjan, Lawler, 1982, с. 289–313.
↑ Takamizawa, Nishizeki, Saito, 1982, с. 623–641.
↑ Корниенко, 1984, с. 109-111.

Литература

М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. — М.: «Мир», 1984.
Jacobo Valdes, Robert E. Tarjan, Eugene L. Lawler^[англ.]. The recognition of series parallel digraphs // SIAM Journal on Computing. — 1982. — Т. 11, вып. 2. — doi:10.1137/0211023.
Н.М. Корниенко. Комбинаторные алгоритмы на классе графов // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 1984. — Вып. 3. — С. 109-111.
David Eppstein. Parallel recognition of series-parallel graphs // Information and Computation. — 1992. — Т. 98, вып. 1. — С. 41–55. — doi:10.1016/0890-5401(92)90041-D.
R. J. Duffin. Topology of Series-Parallel Networks // Journal of Mathematical Analysis and Applications. — 1965. — Т. 10, вып. 2. — С. 303–313. — doi:10.1016/0022-247X(65)90125-3.
Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Graph classes: a survey. — Philadelphia, PA: Society for Industrial and Applied Mathematics, 1999. — Т. 3. — С. 172-174. — (SIAM Monographs on Discrete Mathematics. and Applications). — ISBN 978-0-898714-32-6.
H. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вып. 1–2. — С. 1–45. — doi:10.1016/S0304-3975(97)00228-4.
Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle. On matroids of branch-width three // Journal of Combinatorial Theory, Series B. — 2002. — Т. 86, вып. 1. — С. 148–171. — doi:10.1006/jctb.2002.2120.
K. Takamizawa, T. Nishizeki, N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs // Journal of the ACM. — 1982. — Т. 29, вып. 3. — С. 623–641. — doi:10.1145/322326.322328.

[_85411a8fad2caf3a-1] Свами, Тхуласираман, 1984, с. 150, Упражнение 7.10.

[_9550a0825be9d06a-2] ¹ ² Eppstein, 1992, с. 41–55.

[_ce1e28e15fa99d08-3] Duffin, 1965, с. 303–313.

[_f03633038bc50671-4] ¹ ² Brandstädt, Le, Spinrad, 1999, с. 172-174.

[_93137e77b70d4143-5] Bodlaender, 1998, с. 1–45.

[_dc9da5a5ef8b5bef-6] Hall, Oxley, Semple, Whittle, 2002, с. 148–171.

[_cb40642cb9b35656-7] Valdes, Tarjan, Lawler, 1982, с. 289–313.

[_cc1d735d032b338a-8] Takamizawa, Nishizeki, Saito, 1982, с. 623–641.

[_13561582022e07f7-9] Корниенко, 1984, с. 109-111.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]