パスグラフ

グラフ理論の数学分野において、パスグラフ（または線形グラフ）とは、頂点をv ₁、v ₂、 ...、v _nの順に並べることができ、辺が{ v _i、v _{i +1} }となるグラフのことである。ここでi = 1, 2, ..., n − 1である。言い換えれば、少なくとも 2 つの頂点を持つパスは連結であり、2 つの終端頂点（次数1 の頂点）を持ち、その他の頂点（存在する場合）はすべて次数 2 である。

パスは、他のグラフのサブグラフとして重要な役割を果たすことが多く、その場合、パスはそのグラフ内のパスと呼ばれます。パスは木の特に単純な例であり、実際には、パスは次数が3以上の頂点を持たない木そのものです。パスの非交和は線形フォレストと呼ばれます。

パスはグラフ理論の基本的な概念であり、ほとんどのグラフ理論の教科書の入門セクションで説明されています。例えば、Bondy and Murty (1976)、Gibbons (1985)、またはDiestel (2005)を参照してください。

代数学では、パスグラフはタイプAのディンキン図として現れます。そのため、タイプAのルート系とタイプAのワイル群（対称群）を分類します。

• パス（グラフ理論）
• ラダーグラフ
• 毛虫の木
• 完全なグラフ
• ヌルグラフ
• パス分解
• サイクル（グラフ理論）

• Bondy, JA ; Murty, USR (1976).グラフ理論とその応用. North Holland. pp. 12–21 . ISBN  0-444-19451-7。
• Diestel, Reinhard (2005).グラフ理論（第3 版）.大学院数学テキスト、第173巻、Springer-Verlag、6-9頁。ISBN  3-540-26182-6。

• Weisstein, Eric W. 「パスグラフ」 . MathWorld .