Loading AI tools
Из Википедии, свободной энциклопедии
Двойственный граф к планарному графу — это граф, в котором вершины соответствуют граням графа ; две вершины соединены ребром если и только если соответствующие им грани графа имеют общее ребро. Например, двойственны друг к другу графы куба и октаэдра.
Термин двойственный используется ввиду того, что это свойство симметрично — если H двойственен G, то G двойственен H (при условии, что G связен). То же самое понятие можно использовать для вложения графов в многообразия. Понятие двойственности графов отличается от рёберно-вершинной двойственности (рёберный граф) графа и эти два понятия не следует путать.
Ввиду двойственности, для любого результата, использующего число граней и вершин, можно обменять эти величины.
Самодвойственным называют граф, который изоморфен своему двойственному графу. Например, самодвойственен граф тетраэдра.
Пусть G — связный граф. Алгебраически двойственным графу G называется граф G★ такой, что G и G★ имеют одно и то же множество рёбер, любой цикл в G является разрезом G★ и любой разрез G является циклом в G★. Любой планарный граф имеет алгебраически двойственный граф, в общем случае не единственный (двойственный граф определяется укладкой). Обратное тоже верно — как показал Хасслер в своём критерии планарности[2], связный граф планарен в том и только в том случае, если он имеет алгебраически двойственный граф.
Тот же факт можно выразить в терминах теории матроидов: если M является графовым матроидом[англ.] графа G, то двойственным матроидом[англ.] M является графовый матроид в том и только случае, когда G планарен. Если G планарен, двойственный матроид является графовым матроидом двойственного G графа.
Слабодвойственный планарному графу — это подграф двойственного графа, в котором вершины соответствуют ограниченным граням исходного графа. Планарный граф является внешнепланарным в том и только в том случае, когда двойственный является лесом, и планарный граф является графом Халина в том и только в том случае, когда его слабодвойственный является двусвязным и внешнепланарным. Для любого планарного графа G, пусть G+ — планарный мультиграф, образованный добавлением одной вершины v в неограниченную грань графа G и соединением v со всеми вершинами внешней грани (несколько раз, если вершина появляется несколько раз на границе грани). Теперь G является слабодвойственным (планарного) двойственного G+ графа[3][4].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.