辺推移グラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 辺推移グラフの意味・解説 

辺推移グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/24 09:36 UTC 版)

ナビゲーションに移動 検索に移動

数学グラフ理論の分野における辺推移グラフ(へんすいいグラフ、: edge-transitive graph)とは、与えられた任意の辺 e1 および e2 に対して、e1e2 へと写す自己同型英語版が存在するようなグラフ G のことを言う[1]

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

例と性質

グレイグラフ英語版は辺推移的かつ正則であるが、頂点推移的ではない。

完全2部グラフ や、対称グラフ(例えば立方体の頂点と辺から成るようなグラフ)は、どのようなものであっても辺推移グラフである[1]。対称グラフは(連結であれば)頂点推移的であるが、一般的に、辺推移グラフが頂点推移的であるとは限らない。グレイグラフ英語版はそのように辺推移的であるが頂点推移的でないグラフの例である。そのようなグラフは全て2部グラフであり[1]、したがって2色のみを使って彩色することが出来る。

正則であるが頂点推移的でないような辺推移グラフは、半対称グラフと呼ばれる。そのような例として、グレイグラフ英語版が再び挙げられる。すべての辺推移グラフは必ず2部グラフであり、また、半対称であるか双正則英語版であるかのいずれかである[2]

関連項目

参考文献

  1. ^ a b c Biggs, Norman (1993). Algebraic Graph Theory (2nd ed. ed.). Cambridge: Cambridge University Press. p. 118. ISBN 0-521-45897-8 
  2. ^ Lauri, Josef; Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037, http://books.google.com/books?id=hsymFm0E0uIC&pg=PA20 .

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「辺推移グラフ」の関連用語

辺推移グラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



辺推移グラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの辺推移グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS