グラフ理論において平面グラフGの双対グラフ（そうついグラフ、英: Dual graph）とはすべての頂点がGの各面に対応するグラフである。Gの双対はGの面どうしをつなぐ辺があるとき、それに対応する辺を持ち、辺の両側が同一面である場合、自己ループ（英語版）する。Gの各辺eは対応する双対...

双対（そうつい、dual, duality）とは、互いに対になっている2つの対象の間の関係である。2つの対象がある意味で互いに「裏返し」の関係にあるというようなニュアンスがある（双対の双対はある意味で "元に戻る"）。また、2つのものが互いに双対の関係にあることを「双対性がある」などとよぶ。双対...

次に、平面グラフの全域木とその双対を考える。グラフの全域木とはグラフのすべての頂点を接続し、なおかつ閉路を含まないようなグラフである。また、双対グラフとは、元となるグラフの面に対応する頂点をもち、元グラフの面どうしを繋ぐ辺に対応する辺をもつグラフである。全域木の双対は、元グラフの双対...

の周の集合（これら多角形の周の辺は直線である必要はない。） 多角形グラフ(polygonal graph) その辺が平面でどの多角形も他の多角形を完全に取り囲むことのないような、多角形網を作る平面グラフ 多角形グラフ G の双対グラフ G* (dual graph G* of a polygonal...

グラフと対応がとれる。これにより、どの様な結び目も、3-正則平面グラフで表現できることになる。結び目を構成する方法は、3-正則平面グラフの全域木と双対グラフの全域木を用いる。その概略は、3-正則平面グラフの任意の全域木の各辺に「偶数個の交点」を配置し、全域木の辺ではない 3-正則平面グラフ...

e_{i}^{*}} である。一様なハイパーグラフの双対は、正則であり、逆も成り立つ。双対を考えることで新たな発見があることが多い。 ハイパーグラフの彩色は次のように定義される。 H = ( V , E ) {\displaystyle H=(V,E)} というハイパーグラフは ‖ V ‖ = n {\displaystyle...

ライングラフ 双対グラフ 補グラフ-頂点集合はそのままで隣接関係を逆にする操作 グラフ書換え (graph rewriting)  「二項演算 (binary operation)」では、2つの初期グラフから以下のような新たグラフを生み出す。 グラフ同士の交わりを持たない和 グラフ同士のデカルト積 (cartesian...

グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。 頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフ...

前述のように、グラフ理論により「平面グラフは4彩色可能である」という定理となる（証明もグラフ理論によってなされている）。参考例を図に示すが、まず、地図の境界線をグラフの辺、境界線が接続する点をグラフの頂点としたグラフを作る。その双対グラフにおける頂点の彩色が、元の地図の塗分けと同じ問題となる。...

半正多面体（アルキメデスの立体） - 全ての面が正多角形で、全ての頂点形状が合同な凸多面体のうち、正多面体以外。 カタランの立体（アルキメデス双対） - 全ての面が合同で、二面角が等しい多面体のうち、正多面体以外。各面の中心を結ぶと半正多面体になる。 デルタ多面体 - 全ての面が正三角形である凸多面体。...

となる。双対のランク関数も、例えば r*({1, 3}) = 2 + r({2}) - r({1, 2, 3}) = 2 + 1 - 2 = 1 となるように、成り立っていることが分かる。 また、平面グラフに対する双対とグラフ的マトロイドの双対の概念は一致する。つまり、任意の平面的グラフ G の閉路マトロイド...

最小カット問題を線形計画問題として定式化したとき、双対問題は最大フロー問題である。最小カット問題と最大カット問題は双対ではないので注意されたい。 最大サイズのカットを最大カットとよぶ。最大カット問題はNP完全であり、この証明は、最大充足可能性問題からの変換で得られる。無向グラフの最大カット問題に対する既存の乱択アルゴリズムについて述べる。...

v は閉路グラフを構成する。 車輪グラフは 平面グラフであり、一意な平面グラフを持つ。 車輪グラフはハリングラフ（木（グラフ）の葉を閉路でつないだ平面グラフ）である。 車輪グラフは自己双対である。 最大平面グラフは、K4 = W4であるか、W5 か W6を部分グラフとして含む。 n - 1...

isomorphic) であるとは、それらの間に標準的な同型写像が存在することをいう。例えば、有限次元ベクトル空間 V から二重双対空間への標準的な写像は標準的な同型写像である。一方、V は双対空間に同型であるが、一般には標準的にではない。 同型写像は圏論を用いて形式化される。ある圏の射 f: X → Y...

𝒞 の対象 I のことを指す。圏 𝒞 の終対象（しゅうたいしょう、英: final object, terminal object）とは、始対象の双対概念であり、 𝒞 の任意の対象 X に対してちょうど一つの射 X → T が存在するような 𝒞 の対象 T のことを指す。...

定理の一般的な形を提供することである。このことは、ユニタリ双対(unitary dual)上の測度と、G 上の二乗可積分函数の空間 L2(G) の正規表現とユニタリ双対上のL2函数空間の間の同型を構成することで達成される。ポントリャーギン双対とピーター・ワイルの定理（英語版）は、可換群とコンパクトな群でそれぞれ達成された。...

pairing)を一般化したものである。 アーベル多様体の 偏極(polarisation)とは、アーベル多様体からその双対への 同種 であって次の性質を持つものを言う。アーベル多様体の 二重双対 について対称であり、付随するグラフ射(graph morphism)に沿ったポアンカレバンドルの引き戻しが豊富であること（このこ...

クリークが極大であるかを判定するだけである。 弦グラフのクリークは、双対弦グラフ（英語版）と呼ばれる。 弦グラフがパーフェクトであるとき、極大クリークが最大クリークとなる。この時、クリークの頂点数はグラフの彩色数（頂点彩色）と等しくなる。また、弦グラフはperfect elimination...

上の順序になっていることが容易に分かる。 ( P , ≼ ) {\displaystyle (P,\preccurlyeq )} を (P, ≤) の双対順序集合という。 双対順序集合はその定義 ( P , ≼ ) {\displaystyle (P,\preccurlyeq )} よりもとの順序集合 (P, ≤)...

面を持つ。これと四面体の二つのみが、任意の二頂点を結ぶ線分が必ずその多面体の辺となっているような多面体であると知られている。 チャーサールの多面体の双対がシラッシの多面体であり、それは七つの六角形面がどの二つも互いに隣接 (adjacent) する多面体である。したがって、それは（種数 1...

T のグラフは X × Y で稠密であり、極大不連続線型写像の一種を与える（至る所不連続な函数（英語版）を参照）。ここで X は完備でなく、このような構成可能写像が存在する場合を考えなければならないことに注意。 位相線型空間の双対...

{\displaystyle \beta (X^{*},X)} はウェブ付きである。 特に距離化可能局所凸空間の強双対はウェブ付きである。 局所凸部分空間の場合はウェブを成す各集合は円板とすれば 閉グラフ定理: 局所凸ベール空間の帰納極限から局所凸ウェブ付き空間への任意の閉線型写像は連続である。 開写像定理:...

a long root or a short root). 最後に、図式の双対性は、存在すれば、矢印の向きの反転に対応する：Bn と Cn は双対であり、F4 や G2 や simply-laced ADE 図形は自己双対である。 多重辺を持たないディンキン図形、および対応するリー環やリー群は、simply...

の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である。 二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、c = 0 かつ Q が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。 L ( x , λ ) = 1 2 x T Q x +...

point method)、その双対問題を扱う方法(双対内点法、英: dual interior point method)、主問題と双対問題を同時に解く方法(主双対内点法、英: primal-dual interior point method)に分けられる。 主双対...

\dots ,x_{k+m})} なる多重線型写像として与えられる。 また、K 上のベクトル空間 V から W への K-線型写像の全体 L(V, W) は双対空間 V* を用いれば V ∗ ⊗ W → L ( V , W ) ; ( f , w ) ↦ f ( ∙ ) w {\displaystyle V^{*}\otimes...

という対称性が存在することを言っている。 この理論は、ホログラフィック原理の文脈でも重要である。AdS5 × S5 空間（5 次元球面と5次元 AdS 空間の直積)上のタイプIIB超弦理論と、AdS5 上の 4次元境界における N = 4 超対称ヤン・ミルズ理論の間には双対性がある。この双対性は、ホログラフ...

可換局所コンパクト群に対する調和解析の理論はポントリャーギン双対性と呼ばれる。これは調和解析の持つ主な特徴を説明する分には十分な内容を持つと考えられる[要出典]。調和解析は、このような双対性とフーリエ変換の性質について研究すること、およびそれらの特徴をもっとほかの状況（たと...

{\displaystyle O(n\log n)} 時間で実行可能である。 多角形Pの三角形分割関連で有用なグラフに、三角形分割の双対グラフがある。Pの三角形分割TPが与えられたとき、TPの三角形を頂点として持ち隣接を辺として表すグラフG(TP)が定義できる。G(TP)は木であり、その最大次数は3である。 長きに渡って、単純多角形を...

は自然に π1(X, x) の双対(dual)群と同一視できるので、π1(X, x) の双対群の作用は、x 上のファイバー上への Aut(p) の作用に一致する。Aut(p) と π1(X, x) とは、この場合は自然に同型となる（群はいつも自然に g ↦ g−1) を通して、双対と同型となる）。 p が正規被覆であれば、Aut(p)...

f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)\,} を満たすものをいう。グラフの膨らむ向きを区別する表現を使うなら、凸関数とは「下に凸な関数」のことである。これはまた、エピグラフ（グラフ上およびグラフの上部の点の集合）が凸集合であるような関数であるともいえる。より一般に、ベクトル空間の...