完全マッチングの数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/20 05:15 UTC 版)
「ピーターセンの定理」の記事における「完全マッチングの数」の解説
ラースロー・ロヴァースとマイケル・D・プラマー（英語版）は、橋のない立方体グラフの完全マッチングの数は、頂点数 n の指数関数的に増大すると予想した。この予想はまず2部グラフの場合に証明され(Voorhoeve (1979))、次いで平面グラフの場合に証明された(Chudnovsky & Seymour (2012)、受付は2009年)。一般の橋のない立方体グラフの場合、少なくとも 2 n / 3656 {\displaystyle 2^{n/3656}} の完全マッチングが存在することが示されている(Esperet et al. (2011)、受付は2010年)。
※この「完全マッチングの数」の解説は、「ピーターセンの定理」の解説の一部です。
「完全マッチングの数」を含む「ピーターセンの定理」の記事については、「ピーターセンの定理」の概要を参照ください。
ウィキペディア小見出し辞書の「完全マッチングの数」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 完全マッチングの数のページへのリンク
