Dual graph (original) (raw)
A teoria de grafs, un graf dual (G) d'un graf planar G és un graf que té un vèrtex per a cada regió de G, i una aresta per cada aresta en G unint a dues regions veïnes.
| Property | Value |
|---|---|
| dbo:abstract | المخطط المزدوج أو الرسم البياني الثنائي (بالإنجليزية: Dual graph) يمثل مخططاً أو رسمة لمخطط مستوٍ G، بحيث تكون لديه عقدة لكل وجه في المستوي G وذلك كما هو موضح في فرع نظرية المخططات من علم الرياضيات. يحتوي المخطط المزدوج على ضلع كلما تم فصل وجهين من المستوي G عن بعضهما البعض بضلع، وحلقة ذاتية عندما يظهر نفس الوجه على جانبي الضلع. وهكذا فإن كل ضلع e من المستوي G له ضلع مزدوج مقابل، ونقاط نهايتها هي العقد المزدوجة المقابلة للأوجه على جانبي الضلع e. يعتمد تعريف الازدواجية على اختيار تضمين المخطط G، لذا فهو خاصية للرسوم البيانية المستوية (الرسوم البيانية المضمنة بالفعل في المستوى) بدلاً من المخططات المستوية (الرسوم البيانية التي قد تكون مضمنة ولكن التضمين لها لم يعرف بعد). وبالنسبة إلى المخططات المستوية بشكل عام، قد يكون هناك العديد من المخططات المزدوجة، وذلك اعتمادًا على اختيار التضمين المستوي للمخطط. تاريخيًا كان أول شكل من أشكال ازدواجية الرسم البياني الذي تم الاعتراف به هو اتحاد المواد الصلبة الأفلاطونية في أزواج من متعددات الوجوه المزدوجة. وازدواجية المخطط البياني هي تعميم طوبولوجي للمفاهيم الهندسية متعددة السطوح والفسيفساء الثنائية، وهي بدورها معممة جبريًا من خلال مفهوم ماترويد المزدوج. وتتضمن الاختلافات في ازدواجية الرسم البياني المستوي نسخة من الازدواجية للرسوم البيانية الموجهة، وازدواجية الرسوم البيانية المضمنة في الأسطح ثنائية الأبعاد غير المستوية. ومع ذلك لا ينبغي الخلط بين هذه المفاهيم للمخططات المزدوجة وبين مفهوم مختلف للرسم البياني المزدوج من الضلع إلى العقدة أو الرسم البياني الخطي للمخطط. يستخدم المصطلح مزدوج لأن خاصية كون المخطط مزدوج متماثلة، مما يعني أنه إذا كانت H زوج ثاني من المخطط المتصل G، فإن G هي ازدواج (ثنائية) لـH. فعند مناقشة ازدواجية المخطط G، يمكن الإشارة إلى الرسم البياني G نفسه باسم «المخطط الأولي». يمكن ترجمة العديد من خصائص وهياكل المخطط الأخرى إلى خصائص وهياكل طبيعية أخرى للثنائي المزدوج. على سبيل المثال الدورات الازدواجية لها هي قطع، والأشجار المتفرعة الازدواجية لها هي مع مكملات الأشجار المتفرعة، والمخططات البسيطة (بدون أضلاع متوازية أو حلقات ذاتية) الازدواجية لها هي مخطط 3 أضلاع متصلة (3-edge-connected graphs). يمكن أن تساعد ازدواجية المخطط البياني في تفسير بنية المتاهات وأحواض الصرف. كما تم تطبيق المخططات المزدوجة في رؤية الحاسوب، والهندسة الحاسوبية، وتوليد الشبكات، وتصميم الدوائر المتكاملة. (ar) A teoria de grafs, un graf dual (G) d'un graf planar G és un graf que té un vèrtex per a cada regió de G, i una aresta per cada aresta en G unint a dues regions veïnes. (ca) Jako duální graf nějakého rovinného grafu G se v teorii grafů označuje takový graf G*, jehož vrcholy odpovídají stěnám grafu G a hrany vedou mezi každou dvojicí stěn, které sdílejí společnou hranu. (cs) In the mathematical discipline of graph theory, the dual graph of a plane 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. (en) En teoría de grafos, un grafo dual G' de un grafo planar G es un grafo que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo a dos regiones vecinas. (es) En théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual. (fr) グラフ理論において平面グラフGの双対グラフ（そうたいグラフ、英: Dual graph）とはすべての頂点がGの各面に対応するグラフである。Gの双対はGの面どうしをつなぐ辺があるとき、それに対応する辺を持ち、辺の両側が同一面である場合、する。Gの各辺eは対応する双対辺をもち、この辺はGの面に対応する双対頂点どうしをつなぐ。双対は平面グラフ（すでに平面への埋めこまれているグラフ）についての性質である。平面的グラフ（平面へ埋め込みが可能だが定まっていないグラフ）については、グラフGの埋め込みの選択により、異なる双対グラフになりえる。 歴史的に、双対グラフの概念は正多面体を双対多面体の組とみなすことができるという発見から始まった。グラフの双対性は、双対多面体を位相幾何学的な視点から一般化したものである。またこれはの概念によって代数的に一般化される。双対グラフは有向グラフや平面以外の二次元曲面についても一般化できる。 「双対」という語のとおり、GがHの双対であるとき、HもGの双対となる。面と頂点という対応だけでなく、グラフに関する他の多くの特性および構造は、双対グラフについてその対応物をもつ。例えばサイクルはカットの双対であり、全域木は全域木の補集合の双対である。単純グラフ（または自己ループなし ）の双対は3辺連結グラフである。 グラフの双対性は、迷路や排水盆地の構造を説明するのに便利である。双対グラフは、コンピュータビジョン、計算幾何学、メッシュ生成、および集積回路の設計にも適用されてきた。 サイクルの平面埋め込みは、ジョルダン曲線の定理により、平面をサイクルの内側と外側の2つの面のみに分割する。しかしながら、これら2つの領域は、複数の異なる辺によって分離されているため、閉路グラフの双対は、2つの頂点（2つの面に対応する）が、複数のエッジに接続されたマルチグラフとなる。このようなグラフはと呼ばれる。 によると、すべての多面体グラフ（3次元凸ポリトープの頂点と辺によって形成されるグラフ）は平面で3頂点接続である必要があり、3頂点接続の平面グラフはすべて凸多面体に対応させることができる。すべての3次元凸多面体には双対多面体をもつ。双対多面体は、元の多面体のすべての面に頂点を持ち、2つの面が辺に共有されるとき、対応する2つの頂点の間に辺をもつ。2つの多面体が双対であるときはそのグラフもまた双対となる。たとえば、正多面体において、立方体と正八面体、正二十面体と正十二面体、正四面体とそれ自身は、互いに双対の関係にある。多面体の双対性は、より高次元のポリトープの双対性に拡張することもできるが、三次元の場合とは異なり、グラフ理論的な双対性との明確な関連性を持っていない。 平面グラフの双対グラフがそれ自身と同型のとき、このグラフ自己双対と呼ばれる。車輪グラフは、自己双対多面体（角錐）に対応する自己双対グラフである。また、対応する多面体が存在しないような自己双対グラフも存在する。は、「接着」と「爆発」と2つの操作を使うことで与えられた平面グラフを含む自己双対グラフを構築することが可能であることを述べている。例えば、図の自己双対グラフは四面体とその双対との接着として構成することができる。 オイラーの公式から、n個の頂点を持つすべての自己双対グラフは、厳密に2n − 2個の辺を持つ。すべての単純自己双対平面グラフは、次数3の頂点を少なくとも4つ含み、すべての自己双対グラフの埋め込みは少なくとも4つの三角形面を持つ。 (ja) Nella teoria dei grafi il grafo duale di un grafo planare (o in generale di un grafo raffigurato su una varietà) G è un nuovo grafo G′ che ha un nodo per ogni regione di G ed un arco per ogni arco di G (due nodi di G′ sono connessi da un arco se e solo se le due corrispondenti regioni di G sono separate da un arco). (it) 그래프 이론에서 듀얼 그래프(쌍대 그래프, Dual graph)는 평면 그래프 G의 각 면에 하나의 꼭짓점을 갖는 그래프이다. 듀얼 그래프는 G의 한 변으로 구분된 인접한 면을 잇는 변을 가지며, 한 변의 양쪽 면이 같은 경우 루프를 가진다. 따라서, 그래프 G의 각 변 e는 그에 상응하는 듀얼 변을 가지며, 이 듀얼 변의 양 끝 점은 변 e의 양쪽 면에 상응하는 듀얼 꼭짓점이 된다. (ko) Em teoria dos grafos, um grafo dual G' de um grafo planar G é um grafo que tem um vértice por cada região (face) de G, e uma aresta por cada aresta em G que une duas regiões adjacentes. (pt) Mając graf planarny G można zdefiniować dla niego pojęcie grafu dualnego G*. Termin dualny (ang. dual) jest użyty ponieważ dualność jest symetryczna, jeśli graf X jest dualnym grafem grafu Y, to graf Y jest dualnym grafem grafu X; w efekcie grafy takie są podawane jako pary. (pl) Inom grafteori är en dualgraf, eller en dual graf, till en planär graf G en graf som har en nod som motsvarar varje "sida" i G och en kant som förbinder dessa noder för varje kant i G. Beteckningen "dual" används eftersom egenskapen är symmetrisk, vilket innebär att om H är dual graf till G, så är G dual till H (om G är ). Samma dualitetsbegrepp kan också användas för mer allmänna av grafer i mångfalder. Det begrepp som beskrivs här är inte detsamma som kantgrafen (nod <-> kant i stället för nod <-> sida) till en graf, och skall inte förväxlas med denna. (sv) Двойственный граф к планарному графу — это граф, в котором вершины соответствуют граням графа ; две вершины соединены ребром если и только если соответствующие им грани графа имеют общее ребро. Например, двойственны друг к другу графы куба и октаэдра. Термин двойственный используется ввиду того, что это свойство симметрично — если H двойственен G, то G двойственен H (при условии, что G связен). То же самое понятие можно использовать для вложения графов в многообразия.Понятие двойственности графов отличается от рёберно-вершинной двойственности (рёберный граф) графа и эти два понятия не следует путать. (ru) Двоїстий граф до планарного графу — це граф, у якому вершини відповідають граням графу ; ці вершини з'єднані ребром, тільки якщо відповідні їм грані графу мають спільне ребро. Наприклад, двоїсті один до одного графи куба й октаедра. Двоїстий граф є : у ньому можуть бути петлі й кратні ребра. Залежно від , до одного графу можуть існувати декілька двоїстих. Самодвоїстим називають граф, що ізоморфний своєму двоїстому графу. Наприклад, самодвоїстим є граф тетраедра. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Duals_graphs.svg?width=300 |
| dbo:wikiPageID | 2536864 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Dualität_(Mathematik) |
| dbo:wikiPageLength | 51625 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116471724 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Projective_plane dbr:Pyramid_(geometry) dbr:Mesh_generation dbr:Multigraph dbr:Nowhere-zero_flow dbr:Barnette's_conjecture dbr:Basis_(linear_algebra) dbr:Algorithm dbr:Jordan_curve_theorem dbr:Cubic_graph dbr:Cycle_(graph_theory) dbr:Cycle_basis dbr:Cycle_space dbr:Vector_space dbr:Degree_(graph_theory) dbr:Delaunay_triangulation dbr:Duncan_Sommerville dbr:Induced_subgraph dbr:Integrated_circuit dbc:Planar_graphs dbr:Complement_(set_theory) dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Connected_graph dbr:Mathematics dbr:Geographic_information_system dbr:Petersen_graph dbr:Wilson_operation dbr:Circumcenter dbc:Duality_theories dbr:Frank_Harary dbr:GF(2) dbr:Generating_set_of_a_group dbr:Girth_(graph_theory) dbr:Glossary_of_graph_theory dbr:Gomory–Hu_tree dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:Connected_space dbr:Convex_hull dbr:Cremona_diagram dbr:Leonhard_Euler dbr:Line_graph dbr:Computational_geometry dbr:Computer_vision dbr:Fundamental_group dbr:Harmonices_Mundi dbr:Hemi-dodecahedron dbr:Hemi-icosahedron dbr:Polygon dbr:Spanning_tree dbr:Steinitz's_theorem dbr:Strut dbr:Matroid dbr:Pierre_Varignon dbr:Acyclic_orientation dbc:Algebraic_graph_theory dbr:Topology dbr:Torus dbr:Transpose_graph dbr:Tree_(graph_theory) dbr:Wheel_graph dbr:Drainage_basin dbr:Drainage_divide dbr:Dual_matroid dbr:Dual_polyhedron dbr:Heawood_graph dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:Lloyd's_algorithm dbr:Logic_synthesis dbr:Minimum_cut dbr:Alfred_Kempe dbr:Cut_(graph_theory) dbr:Cut_space dbr:Cycle_graph dbr:Duality_(mathematics) dbr:Edge_(graph_theory) dbr:Equivalence_relation dbr:Eulerian_path dbr:Face_(graph_theory) dbr:Bridge_(graph_theory) dbr:Outerplanar_graph dbr:Dimension_(vector_space) dbr:Directed_graph dbr:Four_color_theorem dbr:Graph_embedding dbr:Graph_isomorphism dbr:Graph_theory dbr:Graphic_matroid dbr:Tessellation dbr:Matroid_girth dbr:Rank_(graph_theory) dbr:Handshaking_lemma dbr:Hassler_Whitney dbc:Topological_graph_theory dbr:Johannes_Kepler dbr:Karl_Georg_Christian_von_Staudt dbr:Biconnected_graph dbr:Binary_matroid dbr:Bipartite_graph dbr:Bipartite_matroid dbr:Bipolar_orientation dbc:Graph_operations dbr:Homeomorphism_(graph_theory) dbr:Toroidal_graph dbr:Transistor dbr:Dipole_graph dbr:Directed_acyclic_graph dbr:Manifold dbr:Boolean_algebra dbr:CMOS dbr:Pixel dbr:Planar_graph dbr:Platonic_solid dbr:Circuit_diagram dbr:Circuit_rank dbr:Convex_polyhedron dbr:Infinite_graph dbr:Minimum_spanning_tree dbr:Orientability dbr:Canonical_form dbr:Loop_(graph_theory) dbr:Maze dbr:Medial_graph dbr:SPQR_tree dbr:Vertex_(graph_theory) dbr:Voronoi_diagram dbr:Tutte_polynomial dbr:Strong_orientation dbr:Symmetric_difference dbr:Symmetric_function dbr:Euler_characteristic dbr:Eulerian_matroid dbr:Seven_Bridges_of_Königsberg dbr:Point_at_infinity dbr:St-planar_graph dbr:Finite_element_method dbr:Whitney's_planarity_criterion dbr:Polyhedral_graph dbr:Polytope dbr:Self-dual_polyhedron dbr:Series–parallel_graph dbr:Petrie_dual dbr:Petrie_polygon dbr:Dual_tessellation dbr:Hamiltonian_cycle dbr:Grid_graph dbr:Plane_graph dbr:Shortest_path_tree dbr:Complement_set dbr:Cutset dbr:Self-loop dbr:Strongly_connected_graph dbr:File:Dual_Cube-Octahedron.svg dbr:File:Circularmazeexample.jpg dbr:File:Delaunay_Voronoi.svg dbr:File:Duals_graphs.svg dbr:File:Noniso_dual_graphs.svg dbr:File:Self-dual_graph.svg |
| dbp:align | right (en) |
| dbp:caption | is dual to the Petersen graph in the projective plane (en) A cycle graph (en) A dipole graph (en) is dual to the Heawood graph in the torus (en) |
| dbp:image | Dipole graph.svg (en) Intercpunetring.png (en) K6-Petersen duality.svg (en) Heawood graph and K7 dually embedded in the torus.svg (en) |
| dbp:mode | cs2 (en) |
| dbp:title | Dual graph (en) |
| dbp:urlname | DualGraph (en) |
| dbp:width | 158 (xsd:integer) 192 (xsd:integer) 200 (xsd:integer) 220 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Good_article dbt:Harvtxt dbt:Interlanguage_link_multi dbt:Main_article dbt:Math dbt:Mathworld dbt:Multiple_image dbt:Mvar dbt:Reflist dbt:Short_description dbt:Bots |
| dcterms:subject | dbc:Planar_graphs dbc:Duality_theories dbc:Algebraic_graph_theory dbc:Topological_graph_theory dbc:Graph_operations |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Action114006945 yago:Attribute100024264 yago:Cognition100023271 yago:Communication100033020 yago:Explanation105793000 yago:Graph107000195 yago:HigherCognitiveProcess105770664 yago:Operation114008806 yago:Process105701363 yago:PsychologicalFeature100023100 yago:WikicatGraphOperations yago:State100024720 yago:Theory105989479 yago:Thinking105770926 yago:VisualCommunication106873252 yago:WikicatDualityTheories yago:WikicatPlanarGraphs |
| rdfs:comment | A teoria de grafs, un graf dual (G) d'un graf planar G és un graf que té un vèrtex per a cada regió de G, i una aresta per cada aresta en G unint a dues regions veïnes. (ca) Jako duální graf nějakého rovinného grafu G se v teorii grafů označuje takový graf G*, jehož vrcholy odpovídají stěnám grafu G a hrany vedou mezi každou dvojicí stěn, které sdílejí společnou hranu. (cs) En teoría de grafos, un grafo dual G' de un grafo planar G es un grafo que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo a dos regiones vecinas. (es) En théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual. (fr) Nella teoria dei grafi il grafo duale di un grafo planare (o in generale di un grafo raffigurato su una varietà) G è un nuovo grafo G′ che ha un nodo per ogni regione di G ed un arco per ogni arco di G (due nodi di G′ sono connessi da un arco se e solo se le due corrispondenti regioni di G sono separate da un arco). (it) 그래프 이론에서 듀얼 그래프(쌍대 그래프, Dual graph)는 평면 그래프 G의 각 면에 하나의 꼭짓점을 갖는 그래프이다. 듀얼 그래프는 G의 한 변으로 구분된 인접한 면을 잇는 변을 가지며, 한 변의 양쪽 면이 같은 경우 루프를 가진다. 따라서, 그래프 G의 각 변 e는 그에 상응하는 듀얼 변을 가지며, 이 듀얼 변의 양 끝 점은 변 e의 양쪽 면에 상응하는 듀얼 꼭짓점이 된다. (ko) Em teoria dos grafos, um grafo dual G' de um grafo planar G é um grafo que tem um vértice por cada região (face) de G, e uma aresta por cada aresta em G que une duas regiões adjacentes. (pt) Mając graf planarny G można zdefiniować dla niego pojęcie grafu dualnego G*. Termin dualny (ang. dual) jest użyty ponieważ dualność jest symetryczna, jeśli graf X jest dualnym grafem grafu Y, to graf Y jest dualnym grafem grafu X; w efekcie grafy takie są podawane jako pary. (pl) Inom grafteori är en dualgraf, eller en dual graf, till en planär graf G en graf som har en nod som motsvarar varje "sida" i G och en kant som förbinder dessa noder för varje kant i G. Beteckningen "dual" används eftersom egenskapen är symmetrisk, vilket innebär att om H är dual graf till G, så är G dual till H (om G är ). Samma dualitetsbegrepp kan också användas för mer allmänna av grafer i mångfalder. Det begrepp som beskrivs här är inte detsamma som kantgrafen (nod <-> kant i stället för nod <-> sida) till en graf, och skall inte förväxlas med denna. (sv) Двоїстий граф до планарного графу — це граф, у якому вершини відповідають граням графу ; ці вершини з'єднані ребром, тільки якщо відповідні їм грані графу мають спільне ребро. Наприклад, двоїсті один до одного графи куба й октаедра. Двоїстий граф є : у ньому можуть бути петлі й кратні ребра. Залежно від , до одного графу можуть існувати декілька двоїстих. Самодвоїстим називають граф, що ізоморфний своєму двоїстому графу. Наприклад, самодвоїстим є граф тетраедра. (uk) المخطط المزدوج أو الرسم البياني الثنائي (بالإنجليزية: Dual graph) يمثل مخططاً أو رسمة لمخطط مستوٍ G، بحيث تكون لديه عقدة لكل وجه في المستوي G وذلك كما هو موضح في فرع نظرية المخططات من علم الرياضيات. يحتوي المخطط المزدوج على ضلع كلما تم فصل وجهين من المستوي G عن بعضهما البعض بضلع، وحلقة ذاتية عندما يظهر نفس الوجه على جانبي الضلع. وهكذا فإن كل ضلع e من المستوي G له ضلع مزدوج مقابل، ونقاط نهايتها هي العقد المزدوجة المقابلة للأوجه على جانبي الضلع e. يعتمد تعريف الازدواجية على اختيار تضمين المخطط G، لذا فهو خاصية للرسوم البيانية المستوية (الرسوم البيانية المضمنة بالفعل في المستوى) بدلاً من المخططات المستوية (الرسوم البيانية التي قد تكون مضمنة ولكن التضمين لها لم يعرف بعد). وبالنسبة إلى المخططات المستوية بشكل عام، قد يكون هناك العديد من المخططات المزدوجة، وذلك اعتمادًا على اختيار التضمين المستو (ar) In the mathematical discipline of graph theory, the dual graph of a plane 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 pla (en) グラフ理論において平面グラフGの双対グラフ（そうたいグラフ、英: Dual graph）とはすべての頂点がGの各面に対応するグラフである。Gの双対はGの面どうしをつなぐ辺があるとき、それに対応する辺を持ち、辺の両側が同一面である場合、する。Gの各辺eは対応する双対辺をもち、この辺はGの面に対応する双対頂点どうしをつなぐ。双対は平面グラフ（すでに平面への埋めこまれているグラフ）についての性質である。平面的グラフ（平面へ埋め込みが可能だが定まっていないグラフ）については、グラフGの埋め込みの選択により、異なる双対グラフになりえる。 歴史的に、双対グラフの概念は正多面体を双対多面体の組とみなすことができるという発見から始まった。グラフの双対性は、双対多面体を位相幾何学的な視点から一般化したものである。またこれはの概念によって代数的に一般化される。双対グラフは有向グラフや平面以外の二次元曲面についても一般化できる。 「双対」という語のとおり、GがHの双対であるとき、HもGの双対となる。面と頂点という対応だけでなく、グラフに関する他の多くの特性および構造は、双対グラフについてその対応物をもつ。例えばサイクルはカットの双対であり、全域木は全域木の補集合の双対である。単純グラフ（または自己ループなし ）の双対は3辺連結グラフである。 (ja) Двойственный граф к планарному графу — это граф, в котором вершины соответствуют граням графа ; две вершины соединены ребром если и только если соответствующие им грани графа имеют общее ребро. Например, двойственны друг к другу графы куба и октаэдра. (ru) |
| rdfs:label | مخطط مزدوج (ar) Graf dual (ca) Dual graph (en) Duální graf (cs) Dualer Graph (de) Grafo dual (es) Graphe dual (fr) Grafo duale (it) 双対グラフ (ja) 듀얼 그래프 (ko) Grafo dual (pt) Graf dualny (pl) Dualgraf (sv) Двойственный граф (ru) Двоїстий граф (uk) |
| owl:sameAs | freebase:Dual graph yago-res:Dual graph wikidata:Dual graph dbpedia-ar:Dual graph dbpedia-ca:Dual graph dbpedia-cs:Dual graph dbpedia-de:Dual graph dbpedia-es:Dual graph dbpedia-fa:Dual graph dbpedia-fr:Dual graph dbpedia-hu:Dual graph dbpedia-it:Dual graph dbpedia-ja:Dual graph dbpedia-ko:Dual graph dbpedia-pl:Dual graph dbpedia-pt:Dual graph dbpedia-ru:Dual graph dbpedia-sv:Dual graph dbpedia-uk:Dual graph dbpedia-vi:Dual graph https://global.dbpedia.org/id/2AdtM |
| prov:wasDerivedFrom | wikipedia-en:Dual_graph?oldid=1116471724&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Dual_Cube-Octahedron.svg wiki-commons:Special:FilePath/Dipole_graph.svg wiki-commons:Special:FilePath/Heawood_graph_and_K7_dually_embedded_in_the_torus.svg wiki-commons:Special:FilePath/Intercpunetring.png wiki-commons:Special:FilePath/K6-Petersen_duality.svg wiki-commons:Special:FilePath/Noniso_dual_graphs.svg wiki-commons:Special:FilePath/Self-dual_graph.svg wiki-commons:Special:FilePath/Delaunay_Voronoi.svg wiki-commons:Special:FilePath/Circularmazeexample.jpg wiki-commons:Special:FilePath/Duals_graphs.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Dual_graph |
| is dbo:wikiPageRedirects of | dbr:Whitney_planarity_criterion dbr:Planar_dual dbr:Algebraic_dual_graph dbr:Self-dual_graph dbr:Weak_dual dbr:Weak_dual_graph |
| is dbo:wikiPageWikiLink of | dbr:List_of_dualities dbr:Mesh_generation dbr:Nowhere-zero_flow dbr:Tonnetz dbr:Dessin_d'enfant dbr:Pathwidth dbr:Percolation_theory dbr:Petersen's_theorem dbr:Regular_icosahedron dbr:Cycle_basis dbr:Cycle_space dbr:Vizing's_theorem dbr:Delaunay_triangulation dbr:Dots_and_Boxes dbr:Dyck_graph dbr:1-planar_graph dbr:1725_in_science dbr:Maximum_cut dbr:Errera_graph dbr:Pitteway_triangulation dbr:Wilson_operation dbr:Girth_(graph_theory) dbr:Glossary_of_graph_theory dbr:Gomory–Hu_tree dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Bowyer–Watson_algorithm dbr:Möbius_strip dbr:Line_graph dbr:Snark_(graph_theory) dbr:Combinatorial_class dbr:Feedback_arc_set dbr:Hemi-dodecahedron dbr:Hemi-icosahedron dbr:Ideal_polyhedron dbr:Penrose_tiling dbr:Planar_separator_theorem dbr:Maekawa's_theorem dbr:Steinitz's_theorem dbr:Matroid dbr:Maze_generation_algorithm dbr:Brigitte_Servatius dbr:Acyclic_orientation dbr:Wheel_graph dbr:Dual_matroid dbr:Dual_polyhedron dbr:Duality_(electrical_circuits) dbr:Dually_chordal_graph dbr:K-edge-connected_graph dbr:Oriented_matroid dbr:Duality_(mathematics) dbr:Edge_coloring dbr:Forbidden_graph_characterization dbr:Barrier_resilience dbr:Discrete_calculus dbr:Goldberg–Coxeter_construction dbr:Goldner–Harary_graph dbr:Graph-encoded_map dbr:Graph_operations dbr:Graphic_matroid dbr:Tessellation dbr:List_of_Euclidean_uniform_tilings dbr:Primal_graph dbr:Italo_Jose_Dejter dbr:Courcelle's_theorem dbr:Schröder–Hipparchus_number dbr:Arrangement_of_lines dbr:Art_gallery_problem dbr:Bipartite_matroid dbr:Polygon_triangulation dbr:Dipole_graph dbr:Planar_graph dbr:Circle_packing_theorem dbr:Klein_graphs dbr:Medial_graph dbr:SPQR_tree dbr:Voronoi_diagram dbr:Tutte_polynomial dbr:Eulerian_matroid dbr:F26A_graph dbr:FKT_algorithm dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Planarization dbr:Planigon dbr:St-planar_graph dbr:Finite_subdivision_rule dbr:Möbius–Kantor_graph dbr:Nauru_graph dbr:Whitney's_planarity_criterion dbr:Polycube dbr:Tutte_embedding dbr:Quad-edge dbr:Uniform_matroid dbr:Petrie_dual dbr:Pfaffian_orientation dbr:The_Petersen_Graph dbr:Pancyclic_graph dbr:Random_cluster_model dbr:Two_ears_theorem dbr:Whitney_planarity_criterion dbr:Planar_dual dbr:Algebraic_dual_graph dbr:Self-dual_graph dbr:Weak_dual dbr:Weak_dual_graph |
| is dbp:properties of | dbr:Wheel_graph |
| is foaf:primaryTopic of | wikipedia-en:Dual_graph |
