|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 対 ： [つい] 【名詞】 1. pair 2. couple 3. set ・ 対称 ： [たいしょう] 【名詞】 1. symmetry ・ 称 ： [しょう] 1. (n,vs) call 2. label ・ ラフ ： [らふ] 1. (adj,n) rough 2. (adj,n) rough
数学のグラフ理論の分野において、あるグラフ ''G'' が対称グラフ（たいしょうぐらふ、）あるいは弧推移グラフであるとは、''G'' に含まれる任意の与えられた隣接する頂点同士からなるペア ''u''1—''v''1 および ''u''2—''v''2 に対して、 :''f''(''u''1) = ''u''2 and ''f''(''v''1) = ''v''2 であるような :''f'' : ''V''(''G'') → ''V''(''G'') が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上（すなわち、方向を持つと考えられる辺の上）で推移的に作用することを言う。 そのようなグラフはしばしば1-弧推移的〔（1-arc-transitive）あるいは旗推移的（flag-transitive）とも呼ばれる。 定義に従い（''u''1 と ''u''2 を無視することで）、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる〔。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、''a''—''b'' が ''d''—''c'' ではなく ''c''—''d'' へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。 したがって、全ての連結対称グラフは頂点推移的かつ辺推移的であり、次数が奇数であるようなグラフに対してはその逆も成立する〔。しかしながら、次数が偶数である場合は、頂点推移的かつ辺推移的であるが、対称でないような連結グラフも存在する〔Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.〕。そのようなグラフは（half-transitive）であると呼ばれる。最小の連結半推移グラフは、次数4で頂点数27のである〔〔.〕。厄介なことに、学者の中には対称グラフという語を、弧推移グラフではなく、頂点推移的かつ辺推移的であるようなグラフに対して用いる人もいる。そのような定義では、上述の定義では除外されている半推移グラフを含むことになる。 距離推移グラフでは、隣接している頂点同士のペア（すなわち、距離が1だけ離れている頂点のペア）を考える代わりに、各々が同じ距離だけ離れているペアを考える。そのようなグラフは、定義より、自然に対称グラフとなる〔。 ''t''-弧という語が、「任意の連続した頂点が隣接しているような頂点の列 ''t''+1 および2ステップ以上離れているような繰り返された頂点」に対して定義される。''t''-推移グラフとは、その自己同型群が''t''-弧の上では推移的に作用するが (''t''+1)-弧の上ではそのように作用しないグラフのことを言う。''1''-弧は単純に辺であるため、次数が3以上であるような全ての対称グラフには、''t''-推移的となるような ''t'' が必ず存在し、そのような ''t'' の値は対称グラフを分類する際に用いられる。例えば、立方体は2-推移的である〔。 't''-推移グラフとは、その自己同型群が''t''-弧の上では推移的に作用するが (''t''+1)-弧の上ではそのように作用しないグラフのことを言う。''1''-弧は単純に辺であるため、次数が3以上であるような全ての対称グラフには、''t''-推移的となるような ''t'' が必ず存在し、そのような ''t'' の値は対称グラフを分類する際に用いられる。例えば、立方体は2-推移的である〔。 == 例 == 対称性の条件と、グラフが（すなわち、すべての頂点の次数が3）であるという制限を組み合わせることは、条件として十分強く、そのようなグラフはリスト化出来るほど特徴的なものである。フォスター調査（Foster census）とその追加調査では、そのようなリストが提供された〔Marston Conder, ''Trivalent symmetric graphs on up to 768 vertices ,'' J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63〕。フォスター調査は、1930年代にによって、彼がベル研究所に雇われていた頃に開始された〔Foster, R. M. "Geometrical Circuits of Electrical Networks." ''Transactions of the American Institute of Electrical Engineers'' 51, 309–317, 1932.〕。また、1988年（フォスターはこの時92歳であった〔）に、最新フォスター調査（512個の頂点を含むものまでの全ての立体対称グラフをリスト化した）が、書籍の形式で出版された〔"The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2〕。その初めの13個の項目は、30の頂点を含むものまでの立体対称グラフである〔Biggs, p. 148〕〔Weisstein, Eric W., "Cubic Symmetric Graph ", from Wolfram MathWorld.〕（その内の10個はまた距離推移的である。例外も以下に示されている）： この他のよく知られた立体対称グラフには、、やがある。上のリスト内の10個の距離推移グラフと、およびのみが、立体距離推移グラフである。 立体でない対称グラフには、（次数2の）閉路グラフや、（頂点の数が5以上の場合には次数が4以上の）完全グラフ、（頂点の数が16以上の場合には次数が4以上の）、および正八面体、正二十面体、立方八面体、二十・十二面体のそれぞれの頂点と辺からなるグラフが挙げられる。無限個の頂点と無限大の次数を持つ対称グラフの例として、が挙げられる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「対称グラフ」の詳細全文を読む スポンサード リンク
|