Semi-symmetric graphとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Semi-symmetric graphの意味・解説 

半対称グラフ

(Semi-symmetric graph から転送)

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

ナビゲーションに移動 検索に移動
フォークマングラフは最小の半対称グラフである。

数学グラフ理論の分野における半対称グラフ(はんたいしょうグラフ、: semi-symmetric graph)とは、辺推移的かつ正則であるが、頂点推移的でない無向グラフのことを言う。

言い換えると、グラフが半対称的であるとは、各頂点に接続する辺の数が等しく、各辺を別のどの辺へも推移することの出来る対称性が存在するが、ある頂点のペアに対しては、対称性によってそれらを別のものへと推移することが出来ないことを言う。半対称グラフは2部グラフであり、その自己同型群英語版は bipartition の各二頂点の集合上で推移的に作用する。右上図において、緑の頂点はどのような自己同型によっても赤い頂点へ写されることはない。

半対称グラフは、1967年、最小の半対称グラフである 20 頂点のフォークマングラフを発見したジョン・フォークマン英語版によって初めて研究された[1]

最小の立方体半対称グラフは、54 頂点のグレイグラフ英語版である。そのグラフが半対称であることは Bouwer (1968) によって初めて確認された。また、最小の立方体半対称グラフであることは、ドラガン・マルシッチ英語版とアレクサンダー・マルニッチによって証明された[2]

立方体半対称グラフについては、768 頂点のものまでが知られている。コンダー、マルニッチ、マルシッチおよびポトチェニクによれば、グレイグラフに続く最小の四つの立方体半対称グラフには、110 頂点のイオフィノヴァ-イヴァノフグラフ、112 頂点のリュブリャナグラフ英語版[3]、120 頂点の内周 8 のグラフ、およびトゥッテ-12ケージ英語版がある[4]

参考文献

  1. ^ Folkman, J. (1967), “Regular line-symmetric graphs”, Journal of Combinatorial Theory 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3 .
  2. ^ Bouwer, I. Z. (1968), “An edge but not vertex transitive cubic graph”, Bulletin of the Canadian Mathematical Society 11: 533–535, doi:10.4153/CMB-1968-063-0 .
  3. ^ Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002), “The Ljubljana Graph”, IMFM Preprints (Ljubljana: Institute of Mathematics, Physics and Mechanics) 40 (845), http://www.imfm.si/preprinti/PDF/00845.pdf .
  4. ^ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), “A census of semisymmetric cubic graphs on up to 768 vertices”, Journal of Algebraic Combinatorics 23 (3): 255–294, doi:10.1007/s10801-006-7397-3 .

外部リンク


「Semi-symmetric graph」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「Semi-symmetric graph」の関連用語

Semi-symmetric graphのお隣キーワード
検索ランキング

   

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



Semi-symmetric graphのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの半対称グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS