LineGraph

LineGraph[g]

グラフ g の線グラフを与える．

LineGraph[{vw,…}]

規則 vw を使ってグラフ g を指定する．

詳細とオプション

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

LineGraph[g]の頂点は1で始まる連続する整数であるとみなされる．
LineGraphは，無向グラフ，有向グラフ，多重グラフに使うことができる．

予備知識

LineGraphはの線グラフを返す．このグラフは，頂点がの辺で，頂点隣接性がの辺隣接性に相当する．より形式的には，辺が e₁,…,e_mであるグラフを与えられた場合，は頂点 e₁,…,e_mを持つことになる．無向グラフについて，とがの同じ頂点に接続している場合，はの辺である．一方，有向グラフについては，中での始点がの終点である場合ははの辺である．線グラフは，随伴グラフ，共役グラフ，被覆グラフ，導関数グラフ，派生グラフ，辺グラフ，辺頂点双対グラフ，交換グラフ，代表グラフ，-obrazom グラフと呼ばれることもある．
線グラフは，グラフ理論において，グラフ頂点についての結果を辺についての結果に翻訳するために使われる．例えば，の独立辺集合はの独立頂点集合になり，の辺彩色数はの彩色数と等しい，等である．
線グラフはもとのグラフと数多くの数学的な関係がある．その中でも最も単純なものは，の頂点数がの辺の数と等しいというものである．加えて，が本の辺と個の頂点を持ち頂点次数が d₁,…,d_nの単純グラフなら，の辺の本数はである．線グラフが明示的に構築できるまた別の関係として，単純グラフの結合行列と m×m 恒等行列について，の隣接行列はで与えられる．
あるグラフが線グラフかどうかは線形時間で求めることができる．の各頂点が厳密にあるクリーク族のうちの2つのクリークに含まれるようなクリークの族が存在するときかつそのときに限り，グラフは単純グラフあるいは多重グラフの線グラフであり，の各辺はそれらのクリークの1つによって誘導される．もしの頂点のうち2つが同じ2つのクリークに含まれないような形でこのクリーク族が形成できるならば，は単純グラフの線グラフである．
グラフのそれぞれが最高で6個の頂点を持ち，その単純グラフがその集合中のどのグラフをも誘導部分グラフとして含まないときかつそのときに限り他の単純グラフの線グラフであるような9つの禁止グラフの集合がある．この禁止グラフの集合はGraphData["Beineke"]で与えられ，完全二部グラフを含むので，線グラフはclaw-freeである．単純グラフのどれの最大次数が少なくとも5であるかを知るためには，これらの禁止グラフのうち6つがあればよい（GraphData["Metelsky"]を参照のこと）．
グラフ理論における多くの重要な結果が線グラフの特性を特徴付けている．例えば，Vizingの定理は，が三角形を含まない単純グラフならの彩色数はの最大クリーク数と等しいかそれより1大きいことを示唆している．また，Königの線彩色定理は，二部グラフの線グラフが完全グラフである（つまり，のすべての誘導部分グラフの彩色数が部分グラフの最大クリークのサイズと一致する）ことを示唆している．