Жазық графиктердің қос графигі

Кіріспе

График, басқа графтың жақтарын көрсететін

Граф теориясының математикалық саласында, жазық граф G-нің дуал графы – G-нің әр жағы үшін түйіні бар граф. Дуал граф G-де бір-бірінен қабырғамен бөлінген жақтардың әр жұбы үшін қабырғаға ие, және бір қабырғаның екі жағында да бірдей жақ пайда болған кезде өзіндік циклға ие болады. Осылайша, G-нің әр қабырғасының сәйкес дуал қабырғасы болады, оның соңғы нүктелері e қабырғасының екі жағындағы жақтарға сәйкес келетін дуал түйіндері болып табылады. Дуалдың анықтамасы граф G-нің енгізілу таңдауына байланысты, сондықтан ол жазық графиктерге (жазықтықта енгізілген графиктерге) емес, жазық графиктерге (енгізілуі мүмкін, бірақ енгізілуі әлі белгісіз) қатысты қасиет болып табылады. Жалпы жазық графиктер үшін, графиктердің жазық енгізілуін таңдауға байланысты бірнеше дуал графиктер болуы мүмкін. Тарихи тұрғыдан алғанда, графтың дуалдығының алғашқы танылған түрі – Платон денелерінің дуал полиэдрлер жұптарына бірігуі болды. Графтың дуалдығы – дуал полиэдрлер мен дуал мозаикалардың геометриялық ұғымдарының топологиялық жалпыламасы, және өз кезегінде дуал матрица ұғымы арқылы комбинаторлық түрде жалпыланады. Жазық графтың дуалдығының нұсқаларына бағытталған графтар үшін дуалдық нұсқасы және жазық емес екі өлшемді беттерге енгізілген графтар үшін дуалдық кіреді. Бұл дуал граф ұғымдарын графтың қабырғасынан түйінге дейінгі дуалымен немесе сызықтық графымен шатастыруға болмайды. "Дуал" термині дуал граф болу қасиетінің симметриялық болғандықтан қолданылады, яғни егер H байланысқан граф G-нің дуалы болса, онда G H-нің дуалы болып табылады. G графтың дуалы туралы сөйлескенде, G графтың өзі "бастапқы граф" деп аталуы мүмкін. Графтың көптеген басқа қасиеттері мен құрылымдары дуалдың басқа табиғи қасиеттері мен құрылымдарына ауыстырылуы мүмкін. Мысалы, циклдар кесімдерге дуал, аралық ағаштар аралық ағаштардың толықтыруларына дуал, ал қарапайым графтар (параллель қабырғалары немесе өзіндік циклдары жоқ) 3 қабырғамен байланысқан графтарға дуал. Графтың дуалдығы лабиринттер мен су жиналатын алаптардың құрылымын түсіндіруге көмектеседі. Дуал графтар компьютерлік көру, есептеу геометриясы, тор жасау және интегралдық схемаларды жобалау салаларында да қолданылған.

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph. Historically, the first form of graph duality to be recognized was the association of the Platonic solids into pairs of dual polyhedra. Graph duality is a topological generalization of the geometric concepts of dual polyhedra and dual tessellations, and is in turn generalized combinatorially by the concept of a dual matroid. Variations of planar graph duality include a version of duality for directed graphs, and duality for graphs embedded onto non planar two dimensional surfaces. These notions of dual graphs should not be confused with a different notion, the edge to vertex dual or line graph of a graph. The term dual is used because the property of being a dual graph is symmetric, meaning that if H is a dual of a connected graph G, then G is a dual of H. When discussing the dual of a graph G, the graph G itself may be referred to as the "primal graph". Many other graph properties and structures may be translated into other natural properties and structures of the dual. For instance, cycles are dual to cuts, spanning trees are dual to the complements of spanning trees, and simple graphs (without parallel edges or self loops) are dual to 3 edge connected graphs. Graph duality can help explain the structure of mazes and of drainage basins. Dual graphs have also been applied in computer vision, computational geometry, mesh generation, and the design of integrated circuits.

Циклдер мен диполдар

Циклдік графиктің бірегей жазылуы Джордан қисық теоремасы бойынша жазықтықты тек екі аймаққа – циклдің ішкі және сыртқы бөліктеріне – бөледі. Дегенмен, n циклда осы екі аймақ n түрлі қабырғалармен бөлінген. Сондықтан, n циклдің дуалды графы – екі төбесі бар (аймақтарға дуалды), бір-бірімен n дуалды қабырғалармен байланысқан көп қабырғалы граф. Мұндай граф көп қабырғалы, байланыс немесе кейде дипольдық граф деп аталады. Керісінше, n қабырғалы дипольдық графтың дуалы n цикл болып табылады.

Екі көпбұрышты

Штайниц теоремасы бойынша, әрбір көпжақты график (үш өлшемді дөңгелек көпжақтың төбелері мен қабырғаларынан құралған график) жазық және 3 төбесі байланысқан болуы керек, ал әрбір 3 төбесі байланысқан жазық график осылайша дөңгелек көпжақтыдан туындайды. Кез келген үш өлшемді дөңгелек көпжақтының қос көпжақтысы болады; қос көпжақтың бастапқы көпжақтың әрбір жағына сәйкес төбесі болады, егер сәйкес екі жақ қабырғаны ортақтасса, онда олардың қос төбелері жанындас болады. Егер екі көпжақты қос болса, олардың графиктері де қос болады. Мысалы, Платон денелері қос жұптар түрінде келеді, октаэдр текшеге қос, додекаэдр икосаэдрге қос, ал тетраэдр өзіне қос. Көпжақты дуалдықты жоғары өлшемді политоптардың дуалдығына да кеңейтуге болады, бірақ геометриялық дуалдықтың бұл кеңейтімі график теориясының дуалдығымен тікелей байланысты емес.

Өзін-өзі екілік графиктер

Егер жазықтық графигі өзінің қос графигіне изоморф болса, онда ол өзіндік қос графигі деп аталады. Дөңгелек графиктері өзіндік қос көпжақтардан (пирамидалардан) туындайтын өзіндік қос графиктердің шексіз отбасын ұсынады. Ойлер формуласынан, n төбесі бар әрбір өзіндік қос графиктің дәл 2n - 2 қабырғасы болады. Кез келген қарапайым өзіндік қос жазықтық графигінде кем дегенде үшінші дәрежелі төрт төбе болады, ал кез келген өзіндік қос кіріктіруде кем дегенде төрт үшбұрышты жақ болады.

Қасиеттері

Граф теориясындағы көптеген табиғи және маңызды түсініктер екілік графтағы басқа, сондай-ақ табиғи, бірақ әртүрлі түсініктерге сәйкес келеді. Қосылған жазық графтың екі рет қос графигі бастапқы графқа изоморфты болғандықтан, осы жұптасулардың әрқайсысы екі жақты: егер жазық графтағы X түсінігі екілік графтағы Y түсінігімен сәйкес келсе, онда жазық графтағы Y түсінігі екілік графтағы X түсінігімен сәйкес келеді.

Қарапайым графиктер мен мультиграфиктер

Қарапайым графтың дуалы қарапайым болуы міндетті емес: оның өзіне циклдары (екі ұшы бір нүктеде болатын қабырғалары) немесе бір екі нүктені жалғайтын бірнеше қабырғалары болуы мүмкін, мысалы, дипольдік мультиграфтар циклдық графтарға дуалды болуында көрініп тұр. Төменде талқыланатын кесу циклының екілігінің арнайы жағдайы ретінде, жазық граф G-нің көпірлері дуал графтың өзіне циклдарымен бір-бірге сәйкес келеді. Осы себепті, дуал мультиграфтағы параллель қабырғалар жұбы (яғни ұзындығы 2 цикл) бастапқы графтағы 2 қабырғадан тұратын кесу жиынына (графты ажыратып тастайтын қабырғалар жұбы) сәйкес келеді. Сондықтан, жазық граф қарапайым болады, егер оның дуалында 1 немесе 2 қабырғадан тұратын кесу жиындары болмаса; яғни, егер ол 3 қабырғамен байланысқан болса. Дуалы қарапайым болатын қарапайым жазық графтар – дәл 3 қабырғамен байланысқан қарапайым жазық графтар. Бұл графтар класына 3 төбемен байланысқан қарапайым жазық графтар класы кіреді, бірақ олар бірдей емес. Мысалы, өзіне дуал графты көрсететін сурет 3 қабырғамен байланысқан (демек, оның дуалы қарапайым), бірақ 3 төбесімен байланысқан емес.

Бірегейлігі

Екілік график белгілі бір кіріктіруге байланысты болғандықтан, жазық графиктердің екілік графигі бірегей емес, яғни бір жазық график үшін изоморфты емес екілік графиктер болуы мүмкін. Суретте көк графиктер изоморфты, бірақ олардың қызыл екілік графиктері изоморфты емес. Жоғарғы қызыл екілік графикте 6 дәрежелі төбе бар (бұл көк графиктің сыртқы бетіне сәйкес келеді), ал төменгі қызыл графикте барлық дәрежелер 6-дан төмен. Хасслер Уитни көрсеткендей, егер график 3-байланысты болса, кіріктіру, демек екілік график бірегей болады. Штайниц теоремасы бойынша, бұл графиктер дәл көпбұрышты графиктер, яғни дөңес көпжақтардың графиктері. Жазық график 3-төбелі байланысты болса және тек оның екілік графигі 3-төбелі байланысты болса ғана. Жалпы алғанда, жазық графиктің бірегей кіріктіруі және, демек, бірегей екілігі болады, егер және тек ол 3-төбелі байланысты жазық графиктің бөлігі болса (яғни 3-төбелі байланысты жазық графиктің кейбір қабырғаларын жолдармен алмастыру арқылы құрылған график). Кейбір жазық графиктер, мысалы, толық екі бөлікті K2,4 графигі 3-төбелі байланысты емес, сондықтан кіріктіру бірегей емес, бірақ барлық кіріктірулер изоморфты. Осы жағдайда, сәйкесінше, барлық екілік графиктер де изоморфты болады. Әртүрлі кіріктірулер әртүрлі екілік графиктерге алып келуі мүмкін болғандықтан, бір графиктің екіншісінің екілігі екенін тексеру (олардың кіріктірулерін білмей) емес тривиалды алгоритмдік мәселе болып табылады. Бұл мәселені бконекстік графиктер үшін графиктердің SPQR ағаштарын пайдалану арқылы полиномиалдық уақытта шешуге болады. Мысалы, суреттегі екі қызыл график осы қатынас бойынша эквивалентті. Алайда, екі жақты байланысы жоқ жазық графиктер үшін бұл қатынас эквиваленттілік қатынасы емес және өзара екілік болуын тексеру мәселесі NP-толық.

Кесулер мен циклдер

Кез келген байланысқан графтың кескіші – бұл төбелерді екі топқа бөлу арқылы анықталатын қабырғалардың жиынтығы, егер қабырғаның бір ұшы бөлістің әр жағында болса, онда ол қабырға жиынтыққа қосылады. Кескіштің қабырғаларын жою графикті кем дегенде екі байланысқан компонентке бөледі. Минималды кескіш (немесе байланыс) – бұл кескіштің кез келген дұрыс ішкі жиынтығы өзі кескіш болмайтын кескіш. Байланысқан графтың минималды кескіші осы графты міндетті түрде екі компонентке бөледі және әр компонентте бір ұшы бар қабырғалар жиынтығынан тұрады. Жабық цикл – циклдегі әр төбе циклдің дәл екі қабырғасына іргелес болатын байланысқан кішіграф. Егер G байланысқан жазық граф болса, онда G-нің кез келген жабық циклы G-нің дуалындағы минималды кескішке сәйкес келеді, және керісінше. Бұл Джордан қисығы теоремасының бір түрі ретінде қарастырылуы мүмкін: әр жабық цикл G-нің беттерін циклдің ішкі және сыртқы беттеріне бөледі, ал циклдің қабырғаларының дуалдары – циклдің ішкі жағынан сыртқы жағына өтетін қабырғалар болып табылады. Кез келген жазық графтың айналымы (оның ең кішкентай циклының өлшемі) оның дуал графының қабырғалық байланысына тең (оның ең кішкентай кескішінің өлшемі). Бағытталған жазық графтарда жабық бағытталған циклдар бағытталған кескіштерге дуалды болады (төбелерді екі топқа бөлу, барлық қабырғалар бір бағытта, бір топтан екіншісіне жүреді). Қатты бағытталған жазық графтар (бағытталмаған графы байланысқан және әр қабырғасы циклге жататын графтар) – циклге жатпайтын бағытталған ациклді графтарға дуалды. Басқаша айтқанда, байланысқан жазық графтың күшті бағыттары (графтың қабырғаларына күшті байланысқан графты құратын бағыттарды беру) ациклді бағыттарға (бағытталған ациклді графты құрайтын бағыттарды беру) дуалды. Сол сияқты, диоиндер (әр бағытталған кескіштен бір қабырғаны қамтитын қабырғалар жиынтығы) кері байланыс доғалары жиынтығына (әр циклден бір қабырғаны қамтитын қабырғалар жиынтығы) дуалды.

A cutset in an arbitrary connected graph is a subset of edges defined from a partition of the vertices into two subsets, by including an edge in the subset when it has one endpoint on each side of the partition. Removing the edges of a cutset necessarily splits the graph into at least two connected components. A minimal cutset (also called a bond) is a cutset with the property that every proper subset of the cutset is not itself a cut. A minimal cutset of a connected graph necessarily separates its graph into exactly two components, and consists of the set of edges that have one endpoint in each component. A simple cycle is a connected subgraph in which each vertex of the cycle is incident to exactly two edges of the cycle. In a connected planar graph G, every simple cycle of G corresponds to a minimal cutset in the dual of G, and vice versa. This can be seen as a form of the Jordan curve theorem: each simple cycle separates the faces of G into the faces in the interior of the cycle and the faces of the exterior of the cycle, and the duals of the cycle edges are exactly the edges that cross from the interior to the exterior. The girth of any planar graph (the size of its smallest cycle) equals the edge connectivity of its dual graph (the size of its smallest cutset). In directed planar graphs, simple directed cycles are dual to directed cuts (partitions of the vertices into two subsets such that all edges go in one direction, from one subset to the other). Strongly oriented planar graphs (graphs whose underlying undirected graph is connected, and in which every edge belongs to a cycle) are dual to directed acyclic graphs in which no edge belongs to a cycle. To put this another way, the strong orientations of a connected planar graph (assignments of directions to the edges of the graph that result in a strongly connected graph) are dual to acyclic orientations (assignments of directions that produce a directed acyclic graph). In the same way, dijoins (sets of edges that include an edge from each directed cut) are dual to feedback arc sets (sets of edges that include an edge from each cycle).

Қосымша қасиеттері

Кез келген жазық графтар үшін жарамды, төбелер мен жақтарды қамтитын есептеу формуласы, жазық дуалдылық арқылы төбелер мен жақтардың рөлі ауыстырылған эквивалентті формулаға түрлендіріле алады. Эйлер формуласы, өзіндік дуал болатын, оның бір мысалы. Харари берген тағы бір мысал – қолдасу леммасы, онда кез келген графтың төбелерінің дәрежелерінің қосындысы жиектер санының екі есесіне тең. Дуал түрінде бұл лемма жазық графтың жақтарының қабырғаларының санының қосындысы жиектер санының екі есесіне тең дейді. Жазық графтың медиалдық графигі, оның дуалының медиалдық графигіне изоморфты. Екі жазық графтың медиалдық графиктері изоморфты болуы мүмкін, егер олар бір-біріне дуалды болса ғана. Төрт немесе одан көп төбесі бар жазық граф, жазықтықты сақтай отырып, оған қосымша жиектер қосу мүмкін болмаса (максималды) егер және тек оның дуалды графы 3-төбелік байланысты және 3-ретті болса ғана. Қосылған жазық граф Эйлерлік (әр төбесінде жұп дәрежелі) егер және тек оның дуалды графы екі бөлікті болса ғана. Егер жазық граф G-де TG(x,y) Тютте полиномы болса, онда оның дуалды графының Тютте полиномы x және y-ді ауыстыру арқылы алынады. Сондықтан, егер Тютте полиномының белгілі бір мәні G-дегі белгілі бір құрылымдар туралы ақпарат берсе, онда Тютте полиномының аргументтерін ауыстыру дуалды құрылымдар үшін тиісті ақпаратты береді. Мысалы, күшті бағдарлардың саны TG(0,2), ал ациклді бағдарлардың саны TG(2,0) болып табылады. Көпірсіз жазық графтар үшін k түспен графты бояу, дуалды графтағы k модульге нөлдік ағындарға сәйкес келеді. Мысалы, төрт түс теоремасы (әр жазық граф үшін 4 түстің болуы) әр көпірсіз жазық графтың дуалында нөлдік 4 ағын болмайтынын айту арқылы эквивалентті түрде тұжырымдалады. k түстің саны (оңай есептелетін коэффициентке дейін) Тютте полиномының TG(1 − k,0) мәнімен есептеледі, ал дуалды түрде нөлдік k ағындарының саны TG(0,1 − k) арқылы есептеледі. st жазық графы – бұл графтың биполярлық бағыты бар, оны ациклді ететін, жалғыз бастапқы және жалғыз аяқтау нүктесі бар, олардың екеуі де бір бетте орналасқан. Мұндай графты сыртқы бет арқылы бастапқы нүктеден аяқтау нүктесіне бір жиек қосу арқылы күшті байланысқан графқа айналдыруға болады. Бұл кеңейтілген жазық графтың дуалы өзі басқа st жазық графтың кеңейтілуі болып табылады. Қатаң айтқанда, бұл құрылым бағытталған жазық графтардың дуалдылығы емес, өйткені граф G-ден бастап екі рет дуалдылықты қолданғанда G-ге қайта оралмайсыз, бірақ G-нің транспоз графына изоморфты графты құрастырасыз, яғни G-нің барлық жиектерін кері бұру арқылы құрылған граф. Дуалдылықты төрт рет қолданғанда бастапқы графқа ораласыз.

Any counting formula involving vertices and faces that is valid for all planar graphs may be transformed by planar duality into an equivalent formula in which the roles of the vertices and faces have been swapped. Euler's formula, which is self dual, is one example. Another given by Harary involves the handshaking lemma, according to which the sum of the degrees of the vertices of any graph equals twice the number of edges. In its dual form, this lemma states that in a plane graph, the sum of the numbers of sides of the faces of the graph equals twice the number of edges. The medial graph of a plane graph is isomorphic to the medial graph of its dual. Two planar graphs can have isomorphic medial graphs only if they are dual to each other. A planar graph with four or more vertices is maximal (no more edges can be added while preserving planarity) if and only if its dual graph is both 3 vertex connected and 3 regular. A connected planar graph is Eulerian (has even degree at every vertex) if and only if its dual graph is bipartite. If a planar graph G has Tutte polynomial TG(x,y), then the Tutte polynomial of its dual graph is obtained by swapping x and y. For this reason, if some particular value of the Tutte polynomial provides information about certain types of structures in G, then swapping the arguments to the Tutte polynomial will give the corresponding information for the dual structures. For instance, the number of strong orientations is TG(0,2) and the number of acyclic orientations is TG(2,0). For bridgeless planar graphs, graph colorings with k colors correspond to nowhere zero flows modulo k on the dual graph. For instance, the four color theorem (the existence of a 4 coloring for every planar graph) can be expressed equivalently as stating that the dual of every bridgeless planar graph has a nowhere zero 4 flow. The number of k colorings is counted (up to an easily computed factor) by the Tutte polynomial value TG(1 − k,0) and dually the number of nowhere zero k flows is counted by TG(0,1 − k). An st planar graph is a connected planar graph together with a bipolar orientation of that graph, an orientation that makes it acyclic with a single source and a single sink, both of which are required to be on the same face as each other. Such a graph may be made into a strongly connected graph by adding one more edge, from the sink back to the source, through the outer face. The dual of this augmented planar graph is itself the augmentation of another st planar graph. Strictly speaking, this construction is not a duality of directed planar graphs, because starting from a graph G and taking the dual twice does not return to G itself, but instead constructs a graph isomorphic to the transpose graph of G, the graph formed from G by reversing all of its edges. Taking the dual four times returns to the original graph.

Қиын қос

Жазық графиктердің әлсіз дуалы – бастапқы графиктің шектеулі беттеріне сәйкес келетін дуалды графиктің ішкі графигі. Жазық график сыртқы жазықтық болады, егер және ғана егер оның әлсіз дуалы орман болса. Кез келген жазық график G үшін, G^(+) – G графигінің шексіз бетіне бір жаңа төбе v қосылып, v төбесі сыртқы беттің әрбір төбесіне (сыртқы беттің шекарасында бірнеше рет пайда болса, сол рет санымен) қосылған жазық көп графигі болсын. Онда G, G^(+) графигінің (жазық) дуалының әлсіз дуалы болады.

Шексіз графиктер мен теселяциялар

Дуальділік ұғымы шексіз жазықтық графиктерге де, сондай-ақ шекті графиктерге де қолданылады. Дегенмен, графиктан бөлінген ашық аймақтың бөлігі емес, сонымен қатар графиктің қабырғасы немесе төбесі емес жазықтықтың нүктелері сияқты топологиялық қиындықтарды болдырмау үшін сақ болу қажет. Егер барлық жақтары графиктің циклмен шектелген аймақтар болса, онда шексіз жазықтық графиктің ендірілуін жазықтықтың мозаикасы ретінде қарастыруға болады, яғни жабық дискілермен (мозаиканың элементтері) жазықтықты жабу, олардың ішкі бөліктері (ендірілу жақтары) бір-бірімен қиылыспайтын ашық дискілер болып табылады. Жазықтық дуальдігі дуальді мозаика түсінігіне әкеледі, ол әрбір элементтің ортасына төбе орналастыру және көршілес элементтердің орталарын қосу арқылы құрастырылады. Дуальді мозаика ұғымын жазықтықты шекті көптеген аймақтарға бөлуге де қолдануға болады. Бұл жағдайда ол жазықтық графигінің дуальдігімен тығыз байланысты, бірақ толығымен сәйкес келмейді. Мысалы, шекті нүктелер жинағының Вороной диаграммасы – бұл жазықтықты көпбұрыштарға бөлу, онда әрбір нүкте басқа нүктелерге қарағанда жақын орналасқан. Кірістің дөңгелек қабығындағы нүктелер шексіз Вороной көпбұрыштарын тудырады, олардың екі қабырғасы шекті сызық сегменттері емес, шексіз сәулелер болып табылады. Бұл диаграмманың дуалы – кірістің Делоне үшбұрыштамасы, егер осы екі нүктені және басқа нүктелерді қамтитын шеңбер болса, онда екі нүктені қабырғамен байланыстыратын жазықтық графигі. Кірістің дөңгелек қабығының қабырғалары да Делоне үшбұрыштамасының қабырғалары болып табылады, бірақ олар Вороной диаграммасының сызық сегменттеріне емес, сәулелерге сәйкес келеді. Вороной диаграммасы мен Делоне үшбұрыштамасы арасындағы бұл дуальділік екі жолмен шекті графиктер арасындағы дуальділікке айналуы мүмкін: Вороной диаграммасына барлық сәулелері үшін екінші нүкте ретінде қызмет ететін шексіз жасанды нүкте қосу арқылы немесе Вороной диаграммасының шектелген бөлігін Делоне үшбұрыштамасының әлсіз дуалы ретінде қарастыру арқылы. Вороной диаграммасы мен Делоне үшбұрыштамасы дуальді болғанымен, олардың жазықтықтағы ендірілуінде дуальді қабырғалардың қиылысынан басқа қосымша қиылыстар болуы мүмкін. Делоне үшбұрышының әрбір нүктесі Вороной диаграммасының сәйкес жағының ішінде орналасқан. Вороной диаграммасының әрбір нүктесі Делоне үшбұрышының сәйкес үшбұрышының ортасында орналасқан, бірақ бұл нүкте оның үшбұрышының сыртында болуы мүмкін.

The concept of duality applies as well to infinite graphs embedded in the plane as it does to finite graphs. However, care is needed to avoid topological complications such as points of the plane that are neither part of an open region disjoint from the graph nor part of an edge or vertex of the graph. When all faces are bounded regions surrounded by a cycle of the graph, an infinite planar graph embedding can also be viewed as a tessellation of the plane, a covering of the plane by closed disks (the tiles of the tessellation) whose interiors (the faces of the embedding) are disjoint open disks. Planar duality gives rise to the notion of a dual tessellation, a tessellation formed by placing a vertex at the center of each tile and connecting the centers of adjacent tiles. The concept of a dual tessellation can also be applied to partitions of the plane into finitely many regions. It is closely related to but not quite the same as planar graph duality in this case. For instance, the Voronoi diagram of a finite set of point sites is a partition of the plane into polygons within which one site is closer than any other. The sites on the convex hull of the input give rise to unbounded Voronoi polygons, two of whose sides are infinite rays rather than finite line segments. The dual of this diagram is the Delaunay triangulation of the input, a planar graph that connects two sites by an edge whenever there exists a circle that contains those two sites and no other sites. The edges of the convex hull of the input are also edges of the Delaunay triangulation, but they correspond to rays rather than line segments of the Voronoi diagram. This duality between Voronoi diagrams and Delaunay triangulations can be turned into a duality between finite graphs in either of two ways: by adding an artificial vertex at infinity to the Voronoi diagram, to serve as the other endpoint for all of its rays, or by treating the bounded part of the Voronoi diagram as the weak dual of the Delaunay triangulation. Although the Voronoi diagram and Delaunay triangulation are dual, their embedding in the plane may have additional crossings beyond the crossings of dual pairs of edges. Each vertex of the Delaunay triangle is positioned within its corresponding face of the Voronoi diagram. Each vertex of the Voronoi diagram is positioned at the circumcenter of the corresponding triangle of the Delaunay triangulation, but this point may lie outside its triangle.

Жазық емес кіріктірулер

Дуальділік ұғымы жазықтықтан басқа екі өлшемді манифольдтағы графтарды енгізуге де қолданылуы мүмкін. Анықтамасы бірдей: манифольдтағы графтың толықтырылымының әрбір байланысқан компоненті үшін дуальді төбе бар, ал графтың әрбір қабырғасы үшін екі дуальді қабырға бар. Бұл ұғымның көптеген қолданылуларында, ол әрбір жақ топологиялық дискі болып табылатын енгізілімдермен шектеледі; бұл шектеу жазық графтар үшін графтың байланысты болуы қажеттілігін кеңейтеді. Бұл шектеумен, кез келген бетке енгізілген графтың дуалы сол бетке табиғи түрде енгізіледі, яғни дуалдың дуалы бастапқы графқа изоморфты және изоморфты түрде енгізілген. Мысалы, K7 толық графы – тороидты граф: ол жазық емес, бірақ торға енгізілуі мүмкін, енгізілімнің әрбір жағы үшбұрыш болады. Бұл енгізілімде Хьювуд графы оның дуальді графы болып табылады. Бұл ұғым бағдарланбаған беттер үшін де жақсы жұмыс істейді. Мысалы, K6 проекциялық жазықтықта он үшбұрышты жақтары бар геми-икосаэдр ретінде енгізілуі мүмкін, оның дуалы геми-додекаэдр ретінде енгізілген Петерсен графы болып табылады. Тіпті жазық графтардың да жазық емес енгізілімдері болуы мүмкін, олардың жазық дуалдарынан өзгеше дуалдары сол енгізілімдерден алынған. Мысалы, кубтың төрт Петри көпбұрышы (кубтың екі қарама-қарсы төбесін алып тастау арқылы қалыптасқан алтыбұрыштар) кубтың торға енгізілімінің алтыбұрышты жақтарын құрайды. Бұл енгізілімнің дуальді графында төрт төбесі бар, олар қос қабырғалары бар толық K4 графы құрайды. Бұл дуальді графтың торлы енгізілімінде әр төбеге келетін алты қабырға, сол төбеге айналып, басқа үш төбе арқылы екі рет өтеді. Жазық жағдайдан айырмашылығы, бұл куб пен оның дуалының енгізілімі бірегей емес; куб графында әртүрлі дуалдары бар бірнеше басқа торлы енгізілімдер бар. Беттік дуальділік және Петри дуальдігі – алты Уилсон операциясының екеуі, және олар бірге осы операциялардың тобын құрайды.

The concept of duality can be extended to graph embeddings on two dimensional manifolds other than the plane. The definition is the same: there is a dual vertex for each connected component of the complement of the graph in the manifold, and a dual edge for each graph edge connecting the two dual vertices on either side of the edge. In most applications of this concept, it is restricted to embeddings with the property that each face is a topological disk; this constraint generalizes the requirement for planar graphs that the graph be connected. With this constraint, the dual of any surface embedded graph has a natural embedding on the same surface, such that the dual of the dual is isomorphic to and isomorphically embedded to the original graph. For instance, the complete graph K7 is a toroidal graph: it is not planar but can be embedded in a torus, with each face of the embedding being a triangle. This embedding has the Heawood graph as its dual graph. The same concept works equally well for non orientable surfaces. For instance, K6 can be embedded in the projective plane with ten triangular faces as the hemi icosahedron, whose dual is the Petersen graph embedded as the hemi dodecahedron. Even planar graphs may have nonplanar embeddings, with duals derived from those embeddings that differ from their planar duals. For instance, the four Petrie polygons of a cube (hexagons formed by removing two opposite vertices of the cube) form the hexagonal faces of an embedding of the cube in a torus. The dual graph of this embedding has four vertices forming a complete graph K4 with doubled edges. In the torus embedding of this dual graph, the six edges incident to each vertex, in cyclic order around that vertex, cycle twice through the three other vertices. In contrast to the situation in the plane, this embedding of the cube and its dual is not unique; the cube graph has several other torus embeddings, with different duals. Surface duality and Petrie duality are two of the six Wilson operations, and together generate the group of these operations.

Матроидтар мен алгебралық дуалдар

G байланысқан графигінің алгебралық дуалы G^(*) графигі болып табылады, G және G^(*) жиектерінің жиынтығы бірдей, G-нің кез келген циклі G^(*) кесіндісі, ал G-нің кез келген кесіндісі G^(*) циклі болып табылады. Кез келген жазық график алгебралық дуалға ие, ол әдетте бірегей емес (жазықтықты ендіру арқылы анықталған кез келген дуал жарайды). Шындығында, керісінше де дұрыс, Хесслер Уитни өзінің жазықтық критерийінде көрсеткендей: байланысқан график G жазық, егер және тек егер ол алгебралық дуалға ие болса. Бұл фактіні матроидтар теориясында да көрсетуге болады. Егер M – G графигінің графикалық матроиды болса, онда G^(*) графигі G-нің алгебралық дуалы болып табылады, егер және тек егер G^(*) графигінің графикалық матроиды M-нің дуалдық матроиды болса. Онда Уитнидің жазықтық критерийін графикалық матроид M-нің дуалдық матроиды өзі графикалық матроид болып табылады, егер және тек егер M-нің негізгі графигі G жазық болса деп қайта формулиреуге болады. Егер G жазық болса, онда дуалдық матроид G-нің дуалдық графигінің графикалық матроиды болып табылады. Атап айтқанда, G-нің барлық түрлі жазықтық ендірулері үшін барлық дуалдық графиктерде изоморфты графикалық матроидтар бар. Жазық емес беттік ендірулер үшін, жазық дуалдардан айырмашылығы, дуалдық график әдетте бастапқы графиктің алгебралық дуалы емес. Жоспарлы емес G графигі үшін G графикалық матроидының дуалдық матроиды графикалық матроид емес. Дегенмен, ол әлі де матроид болып табылады, оның тізбектері G-дегі кесулерге сәйкес келеді, және осы мағынада оны G-нің комбинаторлық түрде жалпыланған алгебралық дуалы деп қарастыруға болады. Эйлерлік және екі бөлікті жазық графиктер арасындағы дуалдықты бинарлық матроидтарға (оларға жазық графиктерден алынған графикалық матроидтар кіреді) кеңейтуге болады: бинарлық матроид Эйлерлік, егер және тек егер оның дуалдық матроиды екі бөлікті болса. Матроид теориясында айналым және жиек байланысты екі дуал ұғымдар біріктіріледі: жазық графиктің графикалық матроидының айналымы графиктің айналымымен бірдей, ал дуалдық матроидтың айналымы (дуалдық графиктің графикалық матроиды) графиктің жиек байланысы болып табылады.

Қолданбалар

Графтар теориясында қолданылысымен қатар, жазық графтардың дуалдығы математикалық және есептеу зерттеулерінің бірнеше басқа да салаларында қолданылады. Географиялық ақпараттық жүйелерде ағын желілері (мысалы, өзендер мен ағындар жүйесінде судың қалай ағатынын көрсететін желілер) дренаж бөліністерін сипаттайтын ұяшықтық желілерге дуалды болып келеді. Бұл дуалдықты ағын желісін тиісті масштабтағы тор графтарында жайылмалы ағаш ретінде модельдеу арқылы, ал дренаж бөлінісін дуалды тор графтарындағы қырлы жоталардың толықтырғыш ағашы ретінде модельдеу арқылы түсіндіруге болады. Компьютерлік көруде цифрлық кескіндер кішкентай шаршы пиксельдерге бөлінеді, олардың әрқайсысының өзіндік түсі болады. Бұл шаршыларға бөлінген бөлімшелердің дуалды графында әр пиксельге бір төбе және қабырғалары ортақ пиксельдер жұптары арасында болады; ол пикселдерді ұқсас түстердің байланысты аймақтарына топтастыруды қамтитын қолданулар үшін пайдалы. Есептеу геометриясында Вороной диаграммалары мен Делонай триангуляциялары арасындағы дуалдылық Вороной диаграммасын құруға арналған кез келген алгоритмді Делонай триангуляциясы үшін алгоритмге бірден түрлендіруге мүмкіндік береді, және керісінше. Осы дуалдылық шекті элементтер торларын жасауда да қолданылуы мүмкін. Ллойд алгоритмі, Вороной диаграммаларына негізделген және беттегі нүктелер жиынтығын біркелкі орналасқан орындарға жылжытуға арналған әдіс, екілік Делонай триангуляциясымен сипатталған шекті элементтер торларын тегістеудің әдеттегі тәсілі ретінде қолданылады. Бұл әдіс үшбұрыштардың мөлшері мен пішінін біркелкі ету арқылы тордың сапасын жақсартады. CMOS тізбектерін синтездеу кезінде синтезделетін функция Буль алгебрасындағы формула түрінде ұсынылады. Содан кейін бұл формула екі тізбекті-параллель көпграфтарға түрлендіріледі. Бұл графтарды тізбек диаграммалары ретінде қарастыруға болады, онда графтардың қабырғалары функцияның кірістерімен басқарылатын транзисторларды білдіреді. Бір тізбек функцияның өзін есептейді, ал екіншісі оның толықтыруын есептейді. Екі тізбектің бірі формуланың конъюнкцияларын және дизъюнкцияларын тиісінше тізбекті және параллель графтардың композициясына түрлендіру арқылы алынады. Екінші тізбек бұл құрылымды кері қайтарады, формуланың конъюнкцияларын және дизъюнкцияларын графтардың параллель және тізбекті композицияларына түрлендіреді. Бұл екі тізбек, әрбір тізбектің кірісін оның шығысына қосатын қосымша қабырғамен толықтырылған, жазық дуалды графтар болып табылады.

Along with its use in graph theory, the duality of planar graphs has applications in several other areas of mathematical and computational study. In geographic information systems, flow networks (such as the networks showing how water flows in a system of streams and rivers) are dual to cellular networks describing drainage divides. This duality can be explained by modeling the flow network as a spanning tree on a grid graph of an appropriate scale, and modeling the drainage divide as the complementary spanning tree of ridgelines on the dual grid graph. In computer vision, digital images are partitioned into small square pixels, each of which has its own color. The dual graph of this subdivision into squares has a vertex per pixel and an edge between pairs of pixels that share an edge; it is useful for applications including clustering of pixels into connected regions of similar colors. In computational geometry, the duality between Voronoi diagrams and Delaunay triangulations implies that any algorithm for constructing a Voronoi diagram can be immediately converted into an algorithm for the Delaunay triangulation, and vice versa. The same duality can also be used in finite element mesh generation. Lloyd's algorithm, a method based on Voronoi diagrams for moving a set of points on a surface to more evenly spaced positions, is commonly used as a way to smooth a finite element mesh described by the dual Delaunay triangulation. This method improves the mesh by making its triangles more uniformly sized and shaped. In the synthesis of CMOS circuits, the function to be synthesized is represented as a formula in Boolean algebra. Then this formula is translated into two series–parallel multigraphs. These graphs can be interpreted as circuit diagrams in which the edges of the graphs represent transistors, gated by the inputs to the function. One circuit computes the function itself, and the other computes its complement. One of the two circuits is derived by converting the conjunctions and disjunctions of the formula into series and parallel compositions of graphs, respectively. The other circuit reverses this construction, converting the conjunctions and disjunctions of the formula into parallel and series compositions of graphs. These two circuits, augmented by an additional edge connecting the input of each circuit to its output, are planar dual graphs.

Тарих

Қиыршық көпбұрыштардың екілік қасиетін Иоганн Кеплер өзінің 1619 жылғы "Harmonices Mundi" кітабында таныған. Көпбұрыштар контексінен тыс, танымал жазықтық қос графиктер 1725 жылы Пьер Вариньонның қайтыс болғаннан кейін жарияланған "Nouvelle Méchanique ou Statique" еңбегінде пайда болды. Бұл Леонхард Эйлердің 1736 жылы Кенигсбергтің жеті көпірі туралы жазған жұмысынан бұрын болған, ол көбінесе граф теориясының алғашқы жұмысы деп саналады. Вариньон статикалық тірек жүйелеріндегі күштерді тіректерге дүйім график салу арқылы талдады, мұнда қабырғаларының ұзындығы тіректерге түсетін күштерге пропорционал. Бұл қос график – Кремона диаграммасының бір түрі. Төрт түс теоремасымен байланысты, карталардың (жазықтықты аймақтарға бөлу) қос графиктері Альфред Кемпе 1879 жылы айтылды және 1891 жылы жазық емес беттердегі карталарға дейін кеңейтілді. Дүйімділік абстрактілі жазықтық графиктердегі операция ретінде Хаслер Уитни 1931 жылы енгізді.