MATHEMATICA 組込みシンボル

LineGraph

LineGraph[g]
グラフ g の線グラフを与える．

有向グラフ g では，LineGraph[g]の2つ頂点に対応する辺が連結されている，つまり一方の辺のターゲットが他方の辺のソースである場合，この2つの頂点は隣接する．

完全グラフの線グラフ：

Out[1]=

Out[2]=

LineGraphは無向グラフに使うことができる：

有向グラフ：

大きいグラフに使う：

グラフの辺の数はそのグラフの線グラフの頂点数に等しい：

連結グラフの線グラフは連結グラフである：

線グラフの隣接行列は

で計算できる：

g の線グラフ中の最大独立集合は g の最大マッチングに対応する：

巡回グラフはその線グラフと同型である：

爪グラフ

の線グラフは三角形である：

経路グラフ

の線グラフは

と同型である：

二部グラフの線グラフは完全グラフである：

ハミルトン(Hamilton)グラフの線グラフはハミルトングラフである：

無向オイラーグラフの線グラフはオイラーグラフである：

オイラーグラフの線グラフはハミルトングラフである：