Interested Article - Срединный граф
![](/images/004/197/4197719/1.jpg?rand=653484)
![](https://cdn.wafarin.com/avatars/eb62af7492157c676fb8fc9692e83447.gif)
- 2020-03-09
- 2
![](/images/004/197/4197719/1.jpg?rand=23650)
Срединный граф — граф , представляющий рёбра смежности внутри граней заданного планарного графа .
Формальное определение
Если задан связный планарный граф , его срединный граф содержит:
- вершину для каждого ребра ,
- ребро между двумя вершинами для каждой грани , если на ней рёбра графа идут подряд.
Срединный граф несвязного графа является несвязным объединением срединных графов компонент связности.
Свойства
![](/images/004/197/4197719/7.jpg?rand=217581)
Поскольку срединный граф зависит от способа вложения, срединный граф не единственен в том смысле, что один и тот же планарный граф может иметь несколько неизоморфных срединных графов. И обратно, неизоморфные графы могут иметь тот же самый срединный граф. В частности, планарный граф и его двойственный граф имеют один срединный граф.
Срединные графы являются 4- регулярными графами . При этом любой 4-регулярный планарный граф является срединным графом некоторого планарного графа. Для связного 4-регулярного планарного графа планарный граф , для которого является срединным, можно построить следующим образом: раскрашиваются грани в два цвета (что возможно, поскольку является эйлеровым, и поскольку двойственный графу является двудольным); вершины в соответствуют граням одного цвета в . Эти вершины соединены ребром для каждой общей (для двух граней) вершины в . Заметим, что проделывая данное построение с гранями другого цвета, получим двойственный граф.
Если два графа имеют один срединный граф, они двойственны .
Ориентированный срединный граф
![](/images/004/197/4197719/18.jpg?rand=678911)
В серединный граф может быть введена ориентация : для этого осуществляется раскраска срединного графа в два цвета в зависимости от того, содержит ли грань срединного графа вершины исходного графа или нет, а ориентация вводится таким образом, чтобы грани какого-либо из цветов оказывались слева от рёбер.
Планарный граф и его двойственный имеют разные ориентированные срединные графы, которые являются обратными друг другу.
Многочлен Татта
Для планарного графа удвоенное значение многочлена Татта в точке (3,3) равно сумме по взвешенным в срединном графе , где вес ориентации равен ( — число седловых вершин ориентации, то есть число вершин, у которых инцидентные дуги упорядочены по циклу «входящая — исходящая — входящая — исходящая») . Поскольку многочлен Татта является инвариантом при вложениях, результат показывает, что для заданного графа любой срединный граф имеет одну и ту же взвешенную сумму эйлеровых ориентаций.
Используя ориентированный срединный граф можно эффективно обобщить результат вычисления многочлена Татта в точке (3,3). Для планарного графа , умноженное на значение многочлена Татта в точке равно взвешенной сумме всех раскрасок дуг в цвета в ориентированном срединном графе графа , так что каждое (возможно пустое) множество дуг одного цвета образует ориентированный эйлеров граф, где вес эйлеровой ориентации равен ( — количество одноцветных вершин, то есть вершин, все четыре ребра, инцидентные которой, имеют один цвет) .
Примечания
- Handbook of Graph Theory / Jonathan L. Gross, Jay Yellen. — CRC Press, 2003. — С. 724. — ISBN 978-1584880905 .
- Michel Las Vergnas. On the evaluation at (3, 3) of the Tutte polynomial of a graph // Journal of Combinatorial Theory, Series B. — 1988. — Т. 35 , вып. 3 . — С. 367–372 . — ISSN . — doi : .
- Joanna A. Ellis-Monaghan. Identities for circuit partition polynomials, with applications to the Tutte polynomial // Advances in Applied Mathematics. — 2004. — Т. 32 , вып. 1-2 . — С. 188-197 . — ISSN . — doi : .
- Michael Korn, Igor Pak. Combinatorial evaluations of the Tutte polyno. — 2003, препринт. — С. 4, Coloring edges of the medial graph .
Литература
- Thomas Brylawski, James Oxley. Matriod Applications / Neil White. — Cambridge University Press, 1992. — С. 123–225.
![](https://cdn.wafarin.com/avatars/eb62af7492157c676fb8fc9692e83447.gif)
- 2020-03-09
- 2