パスグラフ

パスグラフ
6頂点のパスグラフ
頂点	ん
エッジ	1の
半径	⌊n / 2⌋
直径	1の
自己同型	2
彩度数	2
色指数	2
スペクトラム	${\displaystyle \{2\cos \left({\frac {k\pi }{n+1}}\right);}$${\displaystyle k=1,\ldots ,n\}}$
プロパティ	単位距離 二部グラフ 木
表記	Pn [1 ]
グラフとパラメータの表

数学のグラフ理論の分野において、パスグラフ（または線状グラフ）とは、頂点がv 1 _、 v 2 _、 ...、v _nの順序で並べられ、辺が{ v _i、v _{i +1} }となるグラフである。ここで、 i = 1、2、...、n − 1。同様に、少なくとも 2 つの頂点を持つパスは接続されており、2 つの終端頂点（次数1の頂点）を持ち、その他すべて（ある場合）の次数は 2 である。

パスは、他のグラフのサブグラフとしての役割が重要であることが多く、その場合、そのグラフ内のパスと呼ばれます。パスはツリーの特に単純な例であり、実際にはパスは、どの頂点も次数が 3 以上のツリーそのものです。パスの互いに素な和集合は、線形フォレストと呼ばれます。

パスはグラフ理論の基本的な概念であり、ほとんどのグラフ理論のテキストの導入部で説明されています。たとえば、Bondy と Murty (1976)、Gibbons (1985)、Diestel (2005) を参照してください。

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

• パス（グラフ理論）
• ラダーグラフ
• キャタピラーツリー
• 完全なグラフ
• ヌルグラフ
• パス分解
• サイクル（グラフ理論）

• Bondy, JA ; Murty, USR (1976)。グラフ理論とその応用。ノースホランド。pp. 12–21。ISBN 0-444-19451-7。
• ディーステル、ラインハルト(2005)。グラフ理論 (第 3 版)。Graduate Texts in Mathematics、vol. 173、Springer-Verlag。pp. 6–9。ISBN 3-540-26182-6。

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