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