グラフ理論において平面グラフGの双対グラフ(そうついグラフ、英: Dual graph)とはすべての頂点がGの各面に対応するグラフである。Gの双対はGの面どうしをつなぐ辺があるとき、それに対応する辺を持ち、辺の両側が同一面である場合、自己ループ(英語版)する。Gの各辺eは対応する双対...
48 KB (6,672 words) - 05:39, 18 February 2024
双対(そうつい、dual, duality)とは、互いに対になっている2つの対象の間の関係である。2つの対象がある意味で互いに「裏返し」の関係にあるというようなニュアンスがある(双対の双対はある意味で "元に戻る")。また、2つのものが互いに双対の関係にあることを「双対性がある」などとよぶ。双対...
10 KB (1,342 words) - 13:37, 23 March 2023
オイラー標数 (category 位相幾何学的グラフ理論)
次に、平面グラフの全域木とその双対を考える。グラフの全域木とはグラフのすべての頂点を接続し、なおかつ閉路を含まないようなグラフである。また、双対グラフとは、元となるグラフの面に対応する頂点をもち、元グラフの面どうしを繋ぐ辺に対応する辺をもつグラフである。全域木の双対は、元グラフの双対...
9 KB (1,141 words) - 05:52, 26 December 2023
の周の集合(これら多角形の周の辺は直線である必要はない。) 多角形グラフ(polygonal graph) その辺が平面でどの多角形も他の多角形を完全に取り囲むことのないような、多角形網を作る平面グラフ 多角形グラフ G の双対グラフ G* (dual graph G* of a polygonal...
6 KB (824 words) - 04:15, 22 October 2023
全域木 (category グラフ理論における計算問題)
グラフと対応がとれる。これにより、どの様な結び目も、3-正則平面グラフで表現できることになる。結び目を構成する方法は、3-正則平面グラフの全域木と双対グラフの全域木を用いる。その概略は、3-正則平面グラフの任意の全域木の各辺に「偶数個の交点」を配置し、全域木の辺ではない 3-正則平面グラフ...
5 KB (666 words) - 12:22, 21 July 2024
e_{i}^{*}} である。一様なハイパーグラフの双対は、正則であり、逆も成り立つ。双対を考えることで新たな発見があることが多い。 ハイパーグラフの彩色は次のように定義される。 H = ( V , E ) {\displaystyle H=(V,E)} というハイパーグラフは ‖ V ‖ = n {\displaystyle...
6 KB (981 words) - 19:01, 24 May 2024
ライングラフ 双対グラフ 補グラフ-頂点集合はそのままで隣接関係を逆にする操作 グラフ書換え (graph rewriting) 「二項演算 (binary operation)」では、2つの初期グラフから以下のような新たグラフを生み出す。 グラフ同士の交わりを持たない和 グラフ同士のデカルト積 (cartesian...
31 KB (4,435 words) - 08:39, 28 August 2022
グラフの辺で囲まれた各領域(面)を隣接する面同士が同じ色にならないように彩色する問題である。 頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフ...
48 KB (6,767 words) - 10:14, 17 August 2024
四色定理 (category グラフ理論の定理)
前述のように、グラフ理論により「平面グラフは4彩色可能である」という定理となる(証明もグラフ理論によってなされている)。参考例を図に示すが、まず、地図の境界線をグラフの辺、境界線が接続する点をグラフの頂点としたグラフを作る。その双対グラフにおける頂点の彩色が、元の地図の塗分けと同じ問題となる。...
29 KB (4,510 words) - 13:52, 23 March 2024
半正多面体(アルキメデスの立体) - 全ての面が正多角形で、全ての頂点形状が合同な凸多面体のうち、正多面体以外。 カタランの立体(アルキメデス双対) - 全ての面が合同で、二面角が等しい多面体のうち、正多面体以外。各面の中心を結ぶと半正多面体になる。 デルタ多面体 - 全ての面が正三角形である凸多面体。...
8 KB (969 words) - 13:17, 22 May 2024
となる。双対のランク関数も、例えば r*({1, 3}) = 2 + r({2}) - r({1, 2, 3}) = 2 + 1 - 2 = 1 となるように、成り立っていることが分かる。 また、平面グラフに対する双対とグラフ的マトロイドの双対の概念は一致する。つまり、任意の平面的グラフ G の閉路マトロイド...
36 KB (6,112 words) - 23:52, 14 October 2023
最小カット問題を線形計画問題として定式化したとき、双対問題は最大フロー問題である。最小カット問題と最大カット問題は双対ではないので注意されたい。 最大サイズのカットを最大カットとよぶ。最大カット問題はNP完全であり、この証明は、最大充足可能性問題からの変換で得られる。無向グラフの最大カット問題に対する既存の乱択アルゴリズムについて述べる。...
6 KB (840 words) - 22:05, 24 August 2024
v は閉路グラフを構成する。 車輪グラフは 平面グラフであり、一意な平面グラフを持つ。 車輪グラフはハリングラフ(木(グラフ)の葉を閉路でつないだ平面グラフ)である。 車輪グラフは自己双対である。 最大平面グラフは、K4 = W4であるか、W5 か W6を部分グラフとして含む。 n - 1...
6 KB (693 words) - 09:58, 24 January 2021
isomorphic) であるとは、それらの間に標準的な同型写像が存在することをいう。例えば、有限次元ベクトル空間 V から二重双対空間への標準的な写像は標準的な同型写像である。一方、V は双対空間に同型であるが、一般には標準的にではない。 同型写像は圏論を用いて形式化される。ある圏の射 f: X → Y...
23 KB (3,607 words) - 04:26, 23 July 2023
𝒞 の対象 I のことを指す。圏 𝒞 の終対象(しゅうたいしょう、英: final object, terminal object)とは、始対象の双対概念であり、 𝒞 の任意の対象 X に対してちょうど一つの射 X → T が存在するような 𝒞 の対象 T のことを指す。...
14 KB (2,035 words) - 14:17, 11 August 2023
定理の一般的な形を提供することである。このことは、ユニタリ双対(unitary dual)上の測度と、G 上の二乗可積分函数の空間 L2(G) の正規表現とユニタリ双対上のL2函数空間の間の同型を構成することで達成される。ポントリャーギン双対とピーター・ワイルの定理(英語版)は、可換群とコンパクトな群でそれぞれ達成された。...
91 KB (7,737 words) - 20:39, 8 March 2024
アーベル多様体 (section 偏極と双対アーベル多様体)
pairing)を一般化したものである。 アーベル多様体の 偏極(polarisation)とは、アーベル多様体からその双対への 同種 であって次の性質を持つものを言う。アーベル多様体の 二重双対 について対称であり、付随するグラフ射(graph morphism)に沿ったポアンカレバンドルの引き戻しが豊富であること(このこ...
29 KB (3,452 words) - 03:47, 24 March 2023
クリークが極大であるかを判定するだけである。 弦グラフのクリークは、双対弦グラフ(英語版)と呼ばれる。 弦グラフがパーフェクトであるとき、極大クリークが最大クリークとなる。この時、クリークの頂点数はグラフの彩色数(頂点彩色)と等しくなる。また、弦グラフはperfect elimination...
19 KB (2,442 words) - 04:16, 6 August 2024
順序集合 (section 逆順序、狭義の順序、双対順序)
上の順序になっていることが容易に分かる。 ( P , ≼ ) {\displaystyle (P,\preccurlyeq )} を (P, ≤) の双対順序集合という。 双対順序集合はその定義 ( P , ≼ ) {\displaystyle (P,\preccurlyeq )} よりもとの順序集合 (P, ≤)...
42 KB (5,944 words) - 22:08, 28 June 2024
面を持つ。これと四面体の二つのみが、任意の二頂点を結ぶ線分が必ずその多面体の辺となっているような多面体であると知られている。 チャーサールの多面体の双対がシラッシの多面体であり、それは七つの六角形面がどの二つも互いに隣接 (adjacent) する多面体である。したがって、それは(種数 1...
13 KB (1,274 words) - 14:06, 28 November 2021
T のグラフは X × Y で稠密であり、極大不連続線型写像の一種を与える(至る所不連続な函数(英語版)を参照)。ここで X は完備でなく、このような構成可能写像が存在する場合を考えなければならないことに注意。 位相線型空間の双対...
16 KB (2,719 words) - 15:57, 1 September 2023
ウェブ付き空間 (section 閉グラフ定理と開写像定理)
{\displaystyle \beta (X^{*},X)} はウェブ付きである。 特に距離化可能局所凸空間の強双対はウェブ付きである。 局所凸部分空間の場合はウェブを成す各集合は円板とすれば 閉グラフ定理: 局所凸ベール空間の帰納極限から局所凸ウェブ付き空間への任意の閉線型写像は連続である。 開写像定理:...
9 KB (1,422 words) - 16:32, 29 March 2022
a long root or a short root). 最後に、図式の双対性は、存在すれば、矢印の向きの反転に対応する:Bn と Cn は双対であり、F4 や G2 や simply-laced ADE 図形は自己双対である。 多重辺を持たないディンキン図形、および対応するリー環やリー群は、simply...
79 KB (5,977 words) - 11:44, 29 August 2022
の陽な計算を避けた共役勾配法のバリエーションとして書くことも可能である。 二次計画問題のラグランジュ双対はまた二次計画問題となる。これを見るために、c = 0 かつ Q が正値定符号であるケースに着目しよう。ラグランジュ関数は以下のように書ける。 L ( x , λ ) = 1 2 x T Q x +...
19 KB (1,627 words) - 12:22, 17 December 2023
内点法 (section 主双対内点法による非線型最適化)
point method)、その双対問題を扱う方法(双対内点法、英: dual interior point method)、主問題と双対問題を同時に解く方法(主双対内点法、英: primal-dual interior point method)に分けられる。 主双対...
5 KB (870 words) - 13:02, 15 February 2021
\dots ,x_{k+m})} なる多重線型写像として与えられる。 また、K 上のベクトル空間 V から W への K-線型写像の全体 L(V, W) は双対空間 V* を用いれば V ∗ ⊗ W → L ( V , W ) ; ( f , w ) ↦ f ( ∙ ) w {\displaystyle V^{*}\otimes...
24 KB (3,733 words) - 09:22, 28 July 2023
N=4 超対称ヤン・ミルズ理論 (section S-双対)
という対称性が存在することを言っている。 この理論は、ホログラフィック原理の文脈でも重要である。AdS5 × S5 空間(5 次元球面と5次元 AdS 空間の直積)上のタイプIIB超弦理論と、AdS5 上の 4次元境界における N = 4 超対称ヤン・ミルズ理論の間には双対性がある。この双対性は、ホログラフ...
15 KB (1,375 words) - 13:03, 23 October 2020
可換局所コンパクト群に対する調和解析の理論はポントリャーギン双対性と呼ばれる。これは調和解析の持つ主な特徴を説明する分には十分な内容を持つと考えられる[要出典]。調和解析は、このような双対性とフーリエ変換の性質について研究すること、およびそれらの特徴をもっとほかの状況(たと...
8 KB (1,107 words) - 13:00, 22 May 2024
多角形の三角形分割 (section 三角形分割の双対グラフ)
{\displaystyle O(n\log n)} 時間で実行可能である。 多角形Pの三角形分割関連で有用なグラフに、三角形分割の双対グラフがある。Pの三角形分割TPが与えられたとき、TPの三角形を頂点として持ち隣接を辺として表すグラフG(TP)が定義できる。G(TP)は木であり、その最大次数は3である。 長きに渡って、単純多角形を...
10 KB (1,290 words) - 02:39, 9 June 2024
被覆空間 (category 位相幾何学的グラフ理論)
は自然に π1(X, x) の双対(dual)群と同一視できるので、π1(X, x) の双対群の作用は、x 上のファイバー上への Aut(p) の作用に一致する。Aut(p) と π1(X, x) とは、この場合は自然に同型となる(群はいつも自然に g ↦ g−1) を通して、双対と同型となる)。 p が正規被覆であれば、Aut(p)...
53 KB (4,025 words) - 23:56, 10 April 2024
f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)\,} を満たすものをいう。グラフの膨らむ向きを区別する表現を使うなら、凸関数とは「下に凸な関数」のことである。これはまた、エピグラフ(グラフ上およびグラフの上部の点の集合)が凸集合であるような関数であるともいえる。より一般に、ベクトル空間の...
9 KB (1,226 words) - 02:21, 9 August 2024