В теории графов , последовательно-параллельная графика представляет собой графики , с двумя отмеченными вершинами называемых терминалами , образованные рекурсивно два простых операциями композиции. Их можно использовать для моделирования последовательных и параллельных электрических цепей .
Определение и терминология
В этом контексте термин граф означает мультиграф .
Есть несколько способов определить последовательно-параллельные графы. Следующее определение в основном следует тому, которое использовал Дэвид Эппштейн . [1]
Два-терминальный граф (ТТГ) представляет собой график с двумя отмеченными вершинами, ев и т называется источником и раковиной , соответственно.
Параллельная композиция , Рс = Рс (X, Y) из двух TTGs X и Y представляет собой ТТГ создан из объединения непересекающихся графов X и Y с помощью объединения источников X и Y , чтобы создать источник Pc и слияние поглотителей X и Y, чтобы создать раковину ПК .
Композиционный ряд Sc = Sc (X, Y) из двух TTGs X и Y представляет собой ТТГ создан из объединения непересекающихся графов X и Y путем слияния мойку X с источником Y . Источник X становится источником Sc, а сток Y становится стоком Sc .
Последовательно -параллельный граф с двумя терминалами (TTSPG) - это граф, который может быть построен последовательностью последовательных и параллельных композиций, начиная с набора копий однореберного графа K 2 с назначенными терминалами.
Определение 1 . Наконец, граф называется последовательно-параллельным (SP-графом) , если он является TTSPG, когда некоторые две его вершины считаются источником и стоком.
Аналогичным образом можно определить последовательно-параллельные орграфы , построенные из копий однодуговых графов, с дугами, направленными от истока к стоку.
Альтернативное определение
Следующее определение определяет тот же класс графов. [2]
Определение 2 . Граф является SP-графом, если его можно превратить в K 2 последовательностью следующих операций:
- Замена пары параллельных ребер одним ребром, соединяющим их общие конечные точки.
- Замена пары ребер, инцидентных вершине степени 2, отличной от s или t, на единственное ребро.
Характеристики
Каждый последовательно-параллельный граф имеет ширину дерева не более 2 и ширину ветвления не более 2. [3] Действительно, граф имеет ширину ветки не более 2 тогда и только тогда, когда он имеет ширину ветвления не более 2, тогда и только тогда, когда каждый двусвязный компонент является последовательностью– параллельный граф. [4] [5] В максимальном последовательно-параллельных графах, графики , к которой никакие дополнительные ребра не могут быть добавлены без разрушения их последовательно-параллельной структуры, в точности 2-дерева .
Двухсвязные последовательно-параллельные графы характеризуются отсутствием подграфа, гомеоморфного K 4 . [3]
Последовательные параллельные графы также могут быть охарактеризованы их разложением на ухо . [1]
Вычислительная сложность
SP-графы можно распознать за линейное время [6], а их последовательно-параллельное разложение можно построить и за линейное время.
Помимо того, что они являются моделью определенных типов электрических сетей, эти графы представляют интерес с точки зрения теории сложности вычислений , потому что ряд стандартных задач графов решается за линейное время на SP-графах [7], включая нахождение максимального соответствия , максимального независимого множество , минимальное доминирующее множество и гамильтоново пополнение . Некоторые из этих задач являются NP-полными для общих графов. Решение основано на том факте, что если ответы на одну из этих проблем известны для двух SP-графов, то можно быстро найти ответ для их последовательной и параллельной композиции.
Обобщение
В обобщенных последовательно-параллельных графах (GSP-графика) являются продолжением SP-графы [8] с той же алгоритмической эффективностью для вышеуказанных проблем. Класс GSP-графов включает классы SP-графов и внешнепланарных графов .
Графы GSP могут быть заданы определением 2, дополненным третьей операцией удаления оборванной вершины (вершина степени 1). В качестве альтернативы определение 1 можно дополнить следующей операцией.
- Источником слияния S = М (Х, Y) из двух TTGs X и Y представляет собой ТТГ создан из объединения непересекающихся графов X и Y путем слияния источника X с источником Y . Источник и сток X стать источником и сток Р соответственно.
SPQR дерево представляет собой структуру дерева , которое может быть определено для произвольной 2-вершинного связного графа . Он имеет S-узлы, которые аналогичны операциям последовательной композиции в последовательно-параллельных графах, P-узлы, которые аналогичны параллельным операциям композиции в последовательно-параллельных графах, и R-узлы, которые не соответствуют последовательным – параллельным графам. параллельные операции композиции. Двухсвязный граф является последовательно-параллельным тогда и только тогда, когда в его SPQR-дереве нет R-узлов.
Смотрите также
Рекомендации
- ^ а б Эппштейн, Дэвид (1992). «Параллельное распознавание последовательно-параллельных графов» (PDF) . Информация и вычисления . 98 (1): 41–55. DOI : 10.1016 / 0890-5401 (92) 90041-D .
- ^ Даффин, Р.Дж. (1965). «Топология последовательно-параллельных сетей». Журнал математического анализа и приложений . 10 (2): 303–313. DOI : 10.1016 / 0022-247X (65) 90125-3 .
- ^ а б Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми П. (1999). Классы графов: обзор . Монографии SIAM по дискретной математике. и приложения. 3 . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики . С. 172–174 . ISBN 978-0-898714-32-6. Zbl 0919.05001 .
- ^ Бодлендер, Х. (1998). «Частичный k- арборетум графов с ограниченной шириной дерева». Теоретическая информатика . 209 (1–2): 1–45. DOI : 10.1016 / S0304-3975 (97) 00228-4 . hdl : 1874/18312 .
- ^ Холл, Рианнон; Оксли, Джеймс; Семпл, Чарльз; Уиттл, Джефф (2002). «О матроидах ширины ветки три». Журнал комбинаторной теории, серии B . 86 (1): 148–171. DOI : 10.1006 / jctb.2002.2120 .
- ^ Вальдес, Якобо; Тарджан, Роберт Э .; Лоулер, Юджин Л. (1982). «Распознавание серий параллельных орграфов». SIAM Journal on Computing . 11 (2): 289–313. DOI : 10,1137 / 0211023 .
- ^ Takamizawa, K .; Нишизеки, Т .; Сайто, Н. (1982). «Линейная вычислимость комбинаторных задач на последовательно-параллельных графах». Журнал ACM . 29 (3): 623–641. DOI : 10,1145 / 322326,322328 . S2CID 16082154 .
- ^ Корнеенко, Н.М. (1994). «Комбинаторные алгоритмы на одном классе графов». Дискретная прикладная математика . 54 (2–3): 215–217. DOI : 10.1016 / 0166-218X (94) 90022-1 .Перевод Извещений АН БССР, сер. Физ.-мат. Sci. , (1984) нет. 3, стр. 109-111 (на русском языке )