Параллельно-последовательный граф.svg) В теории графов параллельно-последовательные графы — это графы с двумя различными вершинами, которые называются терминальными, образованные рекурсивно с помощью двух простых операций[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. Параллельно-последовательный граф с одной терминальной парой (ППОТП граф) — это граф, который может быть получен в результате последовательных и параллельных соединений множества копий однорёберных графов K2 с назначенными терминальными вершинами. Определение 1. Граф называется последовательно-параллельным, если он ППОТП и две его вершины помечены как источник и сток. Аналогичным образом можно определить последовательно-параллельные орграфы, которые строятся из копий ориентированных графов с одной дугой, и в этом случае дуга направлена из источника в сток. Альтернативное определениеСледующее определение даёт тот же класс графов[3]. Определение 2. Граф является последовательно-параллельным, если он может быть преобразован в граф K2 с помощью последовательности следующих операций:
СвойстваЛюбой параллельно-последовательный граф имеет древесную ширину и ширину ветвления, не превосходящие 2[4]. В действительности граф имеет древесную ширину не более 2 тогда и только тогда, когда он имеет ширину ветвления максимум 2, а также тогда и только тогда, когда любая двусвязная компонента является параллельно-последовательным графом[5][6]. Максимальные параллельно-последовательные графы, графы, к которым нельзя добавить дополнительные рёбра без разрушения последовательно-параллельной структуры, — это в точности 2-деревья[англ.]. Параллельно-последовательные графы характеризуются отсутствием подграфа, гомеоморфного графу K4[4]. Параллельно-последовательные графы могут быть охарактеризованы их ушным разложением[2]. Исследования, вовлекающие параллельно-последовательные графыПараллельно-последовательные графы могут быть распознаны за линейное время[7] и их параллельно-последовательные разложения могут быть построены также за линейное время. Кроме моделирования некоторых типов электрических цепей, эти графы представляют интерес в теории вычислительной сложности, поскольку много стандартных задач на графах решаются в линейное время на ОТП-графах[8], включая поиск максимального паросочетания, максимального независимого множества, минимального доминирующего множества и гамильтонова дополнения. Некоторые из этих задач для графов общего вида NP-полны. Причиной этого является факт, что если ответы для этих задач известны для двух параллельно-последовательных графов, то можно быстро найти ответ для их последовательных и параллельных соединений. Задача о последовательно-параллельных графах[англ.] относится к вопросу перечисления графов и спрашивает о числе параллельно-последовательных графов, которые могут быть образованы из заданного числа рёбер. ОбобщенияОбобщённые параллельно-последовательные графы (ОПП-графы) — это обобщение параллельно-последовательных графов[9], при котором графы имеют ту же алгоритмическую эффективность для упомянутых задач. Класс ОПП-графов включает параллельно-последовательные графы и внешнепланарные графы. ОПП-графы могут быть определены добавлением в Определение 2 третьей операции удаления висящих вершин (вершин степени 1). Таким же образом к Определению 1 можно добавить следующую операциию.
SPQR дерево — это структура, которая может быть определена для произвольного вершинно 2-связного графа. Структура имеет S узлов, аналогичных последовательному соединению в параллельно-последовательных графах, P узлов, аналогичных параллельному соединению параллельно-последовательных графов и R узлов, которые не соответствуют операциям параллельно-последовательных графов. 2-связный граф является параллельно-последовательным тогда и только тогда, когда нет R узлов в дереве SPQR. См. такжеПримечания
Литература
|
Portal di Ensiklopedia Dunia
