グラフの基礎と連結性

グラフ理論の基礎では、グラフ、その基本的なパラメータ、およびグラフがどのように結合しているかを記述する連結性と走査の概念が導入されます。

Definition

グラフは、頂点の集合と、頂点のペアを結ぶ辺の集合で構成されます。連結性は、頂点または辺が除去されたときにグラフがどの程度一体性を保つかを測定します。

Scope

このトピックでは、グラフと有向グラフの定義、次数と握手補題、部分グラフと同型性、ウォーク、パス、サイクル、連結性と連結成分、およびオイラーグラフとハミルトングラフの古典的な特徴付けについて説明します。これは、グラフ理論全体で使用される語彙と中心的な構造的結果を確立します。

Core questions

• グラフの基本的なパラメータ（位数、サイズ、次数）は何ですか？
• グラフはいつ連結になり、その連結性は削除に対してどの程度堅牢ですか？
• グラフはすべての辺を正確に1回使用する閉路をいつ許容しますか？
• パスとサイクルは到達可能性と構造をどのように符号化しますか？

Key concepts

• 頂点、辺、次数
• ウォーク、パス、サイクル
• 連結成分
• 頂点連結度と辺連結度
• オイラー路
• ハミルトン閉路

Key theories

握手補題

任意のグラフにおいて、すべての頂点次数の合計は辺の数の2倍に等しく、これは奇数次数の頂点の数が偶数であることを直ちに意味します。

オイラー路に関するオイラーの定理

連結グラフがすべての辺を正確に1回通過する閉路を持つのは、すべての頂点が偶数次数を持つ場合のみであり、これはケーニヒスベルクの橋の問題に対するオイラーの解決策の基礎となる結果です。

Clinical relevance

連結性分析は、ネットワークの信頼性、ルーティング、および耐障害性通信システムや輸送システムの設計において中心的であり、オイラー構造とハミルトン構造はルーティングとシーケンスの問題で発生します。

History

オイラーの1736年のケーニヒスベルクの論文はグラフ走査を導入しました。メンガーの1927年の定理は、現代の理論の基礎となる連結性と素なパスの間の基本的な双対性を提供しました。

Key figures

• Leonhard Euler
• Karl Menger

Seminal works

• diestel2017

Frequently asked questions

オイラー閉路とハミルトン閉路の違いは何ですか？

オイラー閉路はすべての辺を正確に1回使用しますが、ハミルトン閉路はすべての頂点を正確に1回訪れます。前者は単純な次数特性を持ちますが、後者を決定することは計算上困難です。

グラフがk連結であるとはどういう意味ですか？

グラフがk連結であるとは、k未満の頂点が除去されても連結性を維持する場合を指し、頂点障害に対するその回復力を定量化します。