弦グラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 弦グラフの意味・解説 

弦グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/10/05 07:45 UTC 版)

弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てがを持つようなグラフである。ここで、とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である(4頂点以上の誘導グラフは閉路を持たないか、弦を持つ)。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、perfect elimination orderingという頂点の順序付けが可能である」「最小頂点分離(minimal separator)(グラフを全域グラフでなくするために除去する必要最小限なグラフ)がクリークである」「木の部分木の交差グラフ英語版」といった特徴も持つ。また、rigid circuit graphs[1]や、triangulated graph[2]とも呼ばれる。




「弦グラフ」の続きの解説一覧



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「弦グラフ」の関連用語

弦グラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



弦グラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの弦グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2024 GRAS Group, Inc.RSS