Последовательно-параллельный граф - Series-parallel graph

Последовательные и параллельные операции композиции для последовательно-параллельных графов.

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

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

В этом контексте термин граф означает мультиграф.

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

А двухтерминальный граф (TTG) - граф с двумя выделенными вершинами, s и т называется источник и раковина, соответственно.

В параллельная композиция Pc = Pc (X, Y) двух ТТГ Икс и Y это TTG, созданный из несвязное объединение графов Икс и Y к слияние источники Икс и Y создать источник ПК и слияние раковин Икс и Y создать раковину ПК.

В состав серии Sc = Sc (X, Y) двух ТТГ Икс и Y является ТТГ, созданным из несвязного объединения графов Икс и Y путем слияния раковины Икс с источником Y. Источник Икс становится источником Sc и раковина Y становится раковиной Sc.

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

Определение 1. Наконец, граф называется последовательно-параллельный (SP-график), если это TTSPG, когда некоторые две его вершины считаются источником и приемником.

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

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

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

Определение 2. Граф - это SP-граф, если его можно превратить в K2 последовательностью следующих операций:

  • Замена пары параллельных ребер одним ребром, соединяющим их общие конечные точки
  • Замена пары ребер, инцидентных вершине степени 2, отличной от s или же т с одинарным краем.

Характеристики

Каждый последовательно-параллельный граф имеет ширина дерева не более 2 и ширина ответвления максимум 2.[3] Действительно, граф имеет ширину дерева не более 2 тогда и только тогда, когда он имеет ширину ветвления не более 2, тогда и только тогда, когда каждый двусвязный компонент - последовательно-параллельный граф.[4][5] В максимальный последовательно-параллельные графы, графы, к которым нельзя добавить никаких дополнительных ребер, не разрушая их последовательно-параллельную структуру, являются именно 2-деревья.

Двухсвязные последовательно-параллельные графы характеризуются отсутствием подграфа гомеоморфный к K4.[3]

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

Вычислительная сложность

SP-графики распознаются за линейное время[6] и их последовательно-параллельное разложение можно построить и за линейное время.

Эти графики не только являются моделью определенных типов электрических сетей, но и представляют интерес для теория сложности вычислений, поскольку ряд стандартных графовых задач решается за линейное время на SP-графах,[7] включая нахождение максимальное соответствие, максимальный независимый набор, минимальный доминирующий набор и Гамильтоново пополнение. Некоторые из этих проблем НП-полный для общих графиков. Решение основано на том факте, что если ответы на одну из этих проблем известны для двух SP-графов, то можно быстро найти ответ для их последовательной и параллельной композиции.

Обобщение

В обобщенные последовательно-параллельные графы (GSP-графы) являются расширением SP-графов[8] с тем же алгоритмическая эффективность для упомянутых проблем. К классу GSP-графов относятся классы SP-графов и внешнепланарные графы.

Графики GSP могут быть указаны Определение 2 дополнен третьей операцией удаление висячей вершины (вершина степени 1). В качестве альтернативы, Определение 1 можно дополнить следующей операцией.

  • В исходное слияние S = M (X, Y) двух ТТГ Икс и Y является ТТГ, созданным из непересекающегося объединения графов Икс и Y путем слияния источника Икс с источником Y. Источник и сток Икс стать источником и поглотителем п соответственно.

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

Смотрите также

Рекомендации

  1. ^ а б Эппштейн, Дэвид (1992). «Параллельное распознавание последовательно-параллельных графов» (PDF). Информация и вычисления. 98 (1): 41–55. Дои:10.1016 / 0890-5401 (92) 90041-Д.
  2. ^ Даффин, Р. Дж. (1965). «Топология последовательно-параллельных сетей». Журнал математического анализа и приложений. 10 (2): 303–313. Дои:10.1016 / 0022-247X (65) 90125-3.
  3. ^ а б Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми П. (1999). Классы графов: обзор. Монографии SIAM по дискретной математике. и приложения. 3. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. стр.172–174. ISBN  978-0-898714-32-6. Zbl  0919.05001.
  4. ^ Бодландер, Х. (1998). "Частичный k-арборетум графов с ограниченной шириной дерева ». Теоретическая информатика. 209 (1–2): 1–45. Дои:10.1016 / S0304-3975 (97) 00228-4. HDL:1874/18312.
  5. ^ Холл, Рианнон; Оксли, Джеймс; Семпл, Чарльз; Уиттл, Джефф (2002). «О матроидах ширины ветки три». Журнал комбинаторной теории, серия B. 86 (1): 148–171. Дои:10.1006 / jctb.2002.2120.
  6. ^ Вальдес, Якобо; Тарджан, Роберт Э.; Лоулер, Юджин Л. (1982). «Распознавание серий параллельных орграфов». SIAM Журнал по вычислениям. 11 (2): 289–313. Дои:10.1137/0211023.
  7. ^ Takamizawa, K .; Нишизеки, Т.; Сайто, Н. (1982). «Линейная вычислимость комбинаторных задач на последовательно-параллельных графах». Журнал ACM. 29 (3): 623–641. Дои:10.1145/322326.322328. S2CID  16082154.
  8. ^ Корнеенко, Н. М. (1994). «Комбинаторные алгоритмы на одном классе графов». Дискретная прикладная математика. 54 (2–3): 215–217. Дои:10.1016 / 0166-218X (94) 90022-1. Переведено с Извещения АН БССР, сер. Физ.-мат. Sci., (1984) нет. 3. С. 109–111. (на русском)