Interested Article - Сжатый граф
![](/images/006/660/6660832/1.jpg?rand=123963)
![](https://cdn.wafarin.com/avatars/e97abd871ea2793ffa98f430ed268c35.gif)
- 2021-08-20
- 2
![](/images/006/660/6660832/1.jpg?rand=600658)
Сжатый граф — граф, в котором удаление рёбер любого порождённого цикла с длиной, большей трёх, даёт несвязный граф. То есть это графы, в которых каждый периферийный цикл является треугольником.
Примеры
В максимальном планарном графе , или более обще, в любом полиэдральном графе , периферийные циклы в точности грани планарного вложения графа, так что полиэдральный граф сжат тогда и только тогда, когда все грани являются треугольниками, или, эквивалентно, он является максимально планарным. Любой хордальный граф является сжатым, поскольку лишь порождённые циклы в хордальных графах являются треугольниками, так что нет больше циклов для удаления.
Описание
Сумма по клике двух графов образуется путём отождествления двух клик одинакового размера в каждом графе, а затем часть рёбер клики удаляется. Для версии сумм по клике для сжатых графов шаг удаления рёбер опускается. Сумма по клике такого типа двух сжатых графов приводит к другому сжатому графу, в котором любой длинный порождённый цикл в сумме должен быть ограничен одной стороной или другой (в противном случае была бы хорда между вершинами, которая проходит от одной стороны суммы в другую), а несвязные части на этой стороне, образованные путём удаления цикла, должны остаться несвязными в сумме по клике. Любой хордальный граф может быть разложен таким образом на сумму по клике полных графов , и любой максимальный планарный граф может быть разложен на сумму по клике вершинно 4-связного графа максимальных планарных графов.
Как показали Сеймур и Вивер , это единственно возможные строительные блоки для сжатых графов — сжатые графы, это в точности графы, которые могут быть образованы как суммы по клике полных графов и максимальных планарных графов.
См. также
- Рёберно совершенный граф , в котором любой нечётный цикл является треугольником
Примечания
- .
Литература
- Seymour P. D., Weaver R. W. // Journal of Graph Theory. — 1984. — Т. 8 , вып. 2 . — С. 241–251 . — doi : . .
![](https://cdn.wafarin.com/avatars/e97abd871ea2793ffa98f430ed268c35.gif)
- 2021-08-20
- 2