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

Weblio 辞書 > 同じ種類の言葉 > 人文 > 幾何学 > グラフ > 連結グラフの意味・解説 

連結グラフ

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

連結グラフ(れんけつグラフ、: connected graph)は、グラフ上の任意の2頂点間にが存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。




  1. ^ 点連結度の対応物と辺連結度の対応物についての用語の和訳は定訳が不明であるため直訳した。


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

連結グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/12 14:26 UTC 版)

グラフ (離散数学)」の記事における「連結グラフ」の解説

詳細は「連結グラフ」を参照 無向グラフでは、頂点 x から y まで道がたどれる場合、非順序対 { x , y } {\displaystyle \{x,y\}} が「連結している (connected)」と言う。道が存在しない場合、その非順序対は「非連結」と呼ばれる。 「連結グラフ」は、グラフにある任意の頂点の非順序対連結している無向グラフである。それ以外場合は非連結グラフと呼ばれる有向グラフでは、x から y まで有向道がたどれる場合に、頂点順序対 ( x , y ) {\displaystyle (x,y)} が「強連結」であると言う。有向道は存在しないが、有向辺を全て無向辺に置き換えた後なら x から y までの無向道がたどれる場合は「弱連結」であると言うそれ以外場合、その順序対は非連結呼ばれる強連結グラフは、グラフにある任意の頂点順序対強連結している有向グラフである。それ以外で、グラフにある任意の頂点順序対が弱連結している場合は、弱連結グラフという。それ以外のものは非連結グラフという。 k-頂点連結グラフk-辺連結グラフは、取り除いた場合グラフが非連結となる k−1 個の頂点後者なら辺)集合存在しないグラフである。k-頂点連結グラフは単に「k-連結グラフ」と言うことも多い。

※この「連結グラフ」の解説は、「グラフ (離散数学)」の解説の一部です。
「連結グラフ」を含む「グラフ (離散数学)」の記事については、「グラフ (離散数学)」の概要を参照ください。

ウィキペディア小見出し辞書の「連結グラフ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



連結グラフと同じ種類の言葉


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

辞書ショートカット

すべての辞書の索引

「連結グラフ」の関連用語

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

   

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



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

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

©2024 GRAS Group, Inc.RSS