LineGraph

LineGraph[g]

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

LineGraph[{vw,…}]

規則 vw を使ってグラフ g を指定する．

詳細とオプション

  • LineGraph[g]の各頂点は g の辺に対応する．
  • 無向グラフ g では，LineGraph[g]の2つの頂点に対応する辺が共通の頂点を持つ場合，この2つの頂点は隣接する．
  • 有向グラフ g では，LineGraph[g]の2つ頂点に対応する辺が連結されている，つまり一方の辺のターゲットが他方の辺のソースである場合，この2つの頂点は隣接する．
  • LineGraph[g]の頂点は1で始まる連続する整数であるとみなされる．
  • LineGraphは，無向グラフ，有向グラフ，多重グラフに使うことができる．

予備知識

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

例題

すべて開くすべて閉じる

例  (1)

完全グラフの線グラフ：

スコープ  (5)

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

有向グラフ：

多重グラフ：

規則を使ってグラフを指定する：

LineGraphは大きいグラフに使うことができる：

特性と関係  (11)

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

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

線グラフの隣接行列は で計算できる：

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

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

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

経路グラフ の線グラフは と同型である：

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

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

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

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

おもしろい例題  (1)

Wolfram Research (2010), LineGraph, Wolfram言語関数， https://reference.wolfram.com/language/ref/LineGraph.html （2015年に更新）.

テキスト

Wolfram Research (2010), LineGraph, Wolfram言語関数， https://reference.wolfram.com/language/ref/LineGraph.html （2015年に更新）.

CMS

Wolfram Language. 2010. "LineGraph." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/LineGraph.html.

APA

Wolfram Language. (2010). LineGraph. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LineGraph.html

BibTeX

@misc{reference.wolfram_2024_linegraph, author="Wolfram Research", title="{LineGraph}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/LineGraph.html}", note=[Accessed: 23-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_linegraph, organization={Wolfram Research}, title={LineGraph}, year={2015}, url={https://reference.wolfram.com/language/ref/LineGraph.html}, note=[Accessed: 23-November-2024 ]}