他の性質

ウィキペディア小見出し辞書

他の性質

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/11 14:38 UTC 版)

「双対グラフ」の記事における「他の性質」の解説

すべての平面グラフに有効な頂点や面の数え上げ公式は、双対性によって、頂点と面の役割が入れ替わった同等の式に変換することができる。自己双対的であるオイラーの公式はその一例である。また別の例ではHararyによるハンドシェイク補題がある。これによると、平面グラフの各頂点の次数の合計は、グラフの辺の数の2倍に等しい。この補題の双対形式は、平面グラフの各面を囲む辺の数を全ての面について合計した数は、グラフの辺の数の2倍に等しいことを示す。 平面グラフの中間グラフは元のグラフの双対の中間グラフと同型となる。また、2つの平面グラフは、それらが互いに双対である場合にのみ同形の中間グラフを持つことができる。 4つ以上の頂点を持つ平面グラフは、その双対グラフが3頂点接続と3正規の両方である場合に限り、最大（平面性を保ちながらそれ以上の辺を追加することができない）となる。 連結平面グラフは、その双対グラフが2部グラフである場合に限り、オイラー路（すべての頂点の次数が偶数）となる。平面グラフGにおけるハミルトン路は、双対グラフの頂点を2つの部分集合（サイクルの内側と外側）に分割することに対応し、その誘導部分グラフは両方とも木となる。特に、3次2部多面体グラフのハミルトン性に関するBarnette予想は、すべてのオイラー路最大平面グラフを2つの誘導木に分割できるという推測と同等である。 平面グラフGがTutte多項式TG(x,y)を持つ場合、その双対グラフのTutte多項式はxとy交換することによって得られる。このため、Tutte多項式がGの特定の構造に関する情報を持つ場合、Tutte多項式の引数を交換すると、Gの双対についてそれに対応する情報が得られる。例えば、Gの強い配向の数はTG(0,2)あり、非閉路配向の数はTG(2,0) である。ブリッジレス平面グラフの場合、k色のグラフの色付けは剰余kのゼロフローに対応する。4色定理は、すべてのブリッジレス平面グラフの双対は全て剰余4のゼロフローがあることと同等である。k色付けの数はTutte多項式の値TG(1 − k,0)によって数えられ、その双対である剰余kのゼロフローの数はTG(0,1 − k)によって数えられる。 st-平面グラフとは双極配向をもつグラフである。双極配向とは、一対のソースとシンクによる、循環なしの方向付けで、ソースとシンクが同一の面に属しているようなものである。このようなグラフは、ソースとシンクを結ぶもう一つの辺を加えることで強い結合をもつグラフにすることができる。この補完されたグラフの双対はそれ自身、別のst-平面グラフの補完となる。

他の性質

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/09/07 08:21 UTC 版)

「弱作用素位相」の記事における「他の性質」の解説

定義よりただちに、共役作用 T → T* は WOT において連続であることが分かる。 積（multiplication）は、WOT において共同で連続（jointly continuous）ではない: 再び、T を片側シフトとする。コーシー-シュワルツより、Tn および T*n のいずれも WOT において 0 に収束することが分かる。しかし、T*nTn はすべての n に対して恒等作用素である（有界集合上では WOT は σ-弱位相と一致するため、σ-弱位相においても積は共同で連続ではない）。 しかしながら、一つの弱い主張は成立する: 積は WOT においてそれぞれに連続（separately continuous）である。もし WOT においてネット Ti → T が成立するなら、STi → ST および TiS → TS が WOT において成立する。

他の性質

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/05/09 14:58 UTC 版)

「二重確率行列」の記事における「他の性質」の解説

シンクホーンの定理（英語版）では、厳密に正な成分を持つ任意の行列は、適切な対角行列の前方および後方からの乗算によって二重確率行列へと変換することが出来ることが述べられている。 に対し、すべての二重確率行列はユニタリ型確率行列（英語版）かつ直交型確率行列（英語版）である。しかしより大きい に対してこのことは成立しない。 Van der Waerden は、すべての n × n 二重確率行列の中での最小の永久式（英語版）は であり、そのような最小はすべての成分が であるような二重確率行列によって達成されると予想した。この予想の証明は、1980年の B. Gyires 、1981年の G. P. Egorychev および D. I. Falikman によって行われた。この業績により、Egorychev と Falikman は1982年にファルカーソン賞を受賞した。

他の性質

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:46 UTC 版)

「立方体グラフ」の記事における「他の性質」の解説

任意の n-頂点立方体グラフのパス幅（英語版）は、最大でも n/6 である。しかし、立方体グラフのパス幅の知られている下界のうち最良のものは、より小さく、0.082n である。 グラフ理論を初めて扱った、1736年のレオンハルト・オイラーによる論文の一部分において証明された握手補題（英語版）によると、すべての立方体グラフの頂点の数は偶数であることが分かる。 ジュリウス・ピーターセンの定理は、橋（英語版）の無いすべての立方体グラフには完全マッチングが存在する、というものである。 ロヴァースとプラマーは、すべての橋の無い立方体グラフには、指数関数的な数の完全マッチングが存在すると予想した。この予想は近年、すべての橋の無い n 頂点立方体グラフには少なくとも 2n/3656 個の完全マッチングが存在する、という結果とともに証明された。

他の性質

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/28 14:13 UTC 版)

「正規拡大」の記事における「他の性質」の解説

L を体 K の拡大とすると、 L が K の正規拡大で E が中間体（すなわち L ⊃ E ⊃ K）であれば、L は E の正規拡大である。E は K の正規拡大とは限らない。 E と F が L に含まれる K の正規拡大であれば、合成体 EF および共通部分 E ∩ F も K の正規拡大である。