Сжатый граф (V'gmdw ijgs)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Strangulated_graph.svg/330px-Strangulated_graph.svg.png)
Сжатый граф — граф, в котором удаление рёбер любого порождённого цикла с длиной, большей трёх, даёт несвязный граф. То есть это графы, в которых каждый периферийный цикл является треугольником.
Примеры
[править | править код]В максимальном планарном графе, или более обще, в любом полиэдральном графе, периферийные циклы в точности грани планарного вложения графа, так что полиэдральный граф сжат тогда и только тогда, когда все грани являются треугольниками, или, эквивалентно, он является максимально планарным. Любой хордальный граф является сжатым, поскольку лишь порождённые циклы в хордальных графах являются треугольниками, так что нет больше циклов для удаления.
Описание
[править | править код]Сумма по клике двух графов образуется путём отождествления двух клик одинакового размера в каждом графе, а затем часть рёбер клики удаляется. Для версии сумм по клике для сжатых графов шаг удаления рёбер опускается. Сумма по клике такого типа двух сжатых графов приводит к другому сжатому графу, в котором любой длинный порождённый цикл в сумме должен быть ограничен одной стороной или другой (в противном случае была бы хорда между вершинами, которая проходит от одной стороны суммы в другую), а несвязные части на этой стороне, образованные путём удаления цикла, должны остаться несвязными в сумме по клике. Любой хордальный граф может быть разложен таким образом на сумму по клике полных графов, и любой максимальный планарный граф может быть разложен на сумму по клике вершинно 4-связного графа максимальных планарных графов.
Как показали Сеймур и Вивер[1], это единственно возможные строительные блоки для сжатых графов — сжатые графы, это в точности графы, которые могут быть образованы как суммы по клике полных графов и максимальных планарных графов.
См. также
[править | править код]- Рёберно совершенный граф, в котором любой нечётный цикл является треугольником
Примечания
[править | править код]Литература
[править | править код]- Seymour P. D., Weaver R. W. A generalization of chordal graphs // Journal of Graph Theory. — 1984. — Т. 8, вып. 2. — С. 241–251. — doi:10.1002/jgt.3190080206..
Для улучшения этой статьи желательно:
|