辺推移グラフのソースを表示

{{about|グラフ理論|幾何学における「辺推移的」|:en:Edge-transitive}}
[[数学]]の[[グラフ理論]]の分野における'''辺推移グラフ'''（へんすいいグラフ、{{Lang-en-short|edge-transitive graph}}）とは、与えられた任意の辺 ''e''<sub>1</sub> および ''e''<sub>2</sub> に対して、''e''<sub>1</sub> を ''e''<sub>2</sub> へと写す{{仮リンク|グラフ自己同型性|label=自己同型|en|Graph automorphism}}が存在するような[[グラフ理論|グラフ]] ''G'' のことを言う<ref name="biggs">{{cite book | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd ed. | location=Cambridge | publisher=Cambridge University Press | year=1993 | page=118 | isbn=0-521-45897-8}}</ref>。

言い換えると、グラフが辺推移的であるとは、その[[準同型|自己同型群]]が各辺の上で[[群作用|推移的]]に作用することを言う。

== 例と性質 ==
[[Image:Gray graph 2COL.svg|thumb|200px|{{仮リンク|グレイグラフ|en|Gray graph}}は辺推移的かつ[[正則グラフ|正則]]であるが、[[頂点推移グラフ|頂点推移的]]ではない。]]

[[完全2部グラフ]] <math>K_{m,n}</math> や、[[対称グラフ]]（例えば[[立方体]]の頂点と辺から成るようなグラフ）は、どのようなものであっても辺推移グラフである<ref name="biggs" />。対称グラフは（連結であれば）[[頂点推移グラフ|頂点推移的]]であるが、一般的に、辺推移グラフが頂点推移的であるとは限らない。{{仮リンク|グレイグラフ|en|Gray graph}}はそのように辺推移的であるが頂点推移的でないグラフの例である。そのようなグラフは全て[[2部グラフ]]であり<ref name="biggs" />、したがって2色のみを使って[[グラフ彩色|彩色]]することが出来る。

[[正則グラフ|正則]]であるが頂点推移的でないような辺推移グラフは、[[半対称グラフ]]と呼ばれる。そのような例として、{{仮リンク|グレイグラフ|en|Gray graph}}が再び挙げられる。すべての辺推移グラフは必ず[[2部グラフ]]であり、また、半対称であるか{{仮リンク|双正則グラフ|label=双正則|en|biregular graph}}であるかのいずれかである<ref name="ls03">{{citation
 | last1 = Lauri | first1 = Josef
 | last2 = Scapellato | first2 = Raffaele
 | isbn = 9780521529037
 | pages = 20–21
 | publisher = Cambridge University Press
 | series = London Mathematical Society Student Texts
 | title = Topics in Graph Automorphisms and Reconstruction
 | url = https://books.google.co.jp/books?id=hsymFm0E0uIC&pg=PA20&redir_esc=y&hl=ja
 | year = 2003}}.</ref>。

== 関連項目 ==
* {{仮リンク|辺推移的 (幾何学)|en|Edge-transitive}}

== 参考文献 ==
{{reflist}}

== 外部リンク ==
* {{MathWorld | urlname=Edge-TransitiveGraph | title=Edge-transitive graph }}

{{DEFAULTSORT:へんすいいくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]
[[Category:代数的グラフ理論]]