ここが適切な場所か分からないのですが・・・。

 Kautz digraphは、対称グラフなのでしょうか。K(d, k)として、d=2のときはそのような気がしますが、自信が持てません。また、d>3のときについてはカイモク見当もつきません。

 どなたかご存知の方、ご教授頂ければ幸いです。

このQ&Aに関連する最新のQ&A

A 回答 (5件)

再帰性について再び。


本来のご質問の意味はKautz digraphを適当にアークをちょん切っていくつかの部分グラフに分けたときに、それぞれがKautz digraphにできるか、という問題だったんですね。
d,kがうんと小さいときを除くと、一般に丁度2種類の文字を含む語があって、これらの語は3種類以上の文字を含むKautz digraphに含まれてしまいます。つまり文字xを含まない語によるKautz digraphは部分グラフとして存在しますが、文字y(y≠x)を含まない語による部分グラフと共通のノードを持ってしまいます。アルファベットを二つに分割してA=B+C (B∩C=φ)とすれば、B,Cそれぞれのアルファベットだけによる部分グラフがKautz digraphになるけど、両方の文字を含む大量の語が余ってしまう。そして、この余った語の一部でKautz digraphを構成しようとすると、Bだけの文字を含む語がどうしても含まれなくてはならない。つまり<xyxyxy....>という形の語がどの部分Kautz digraphにも必要なので、うまく分割できないように思われます。無理じゃないかな、という感じはするんですが。

やっぱり専門家に出てきて貰わんとアキマヘンな、こりゃ。
どうもすいません。

この回答への補足

 stomachmanさん

>やっぱり専門家に出てきて貰わんと
 いやいやいや、ここで書かれていることは相当(あるいは完璧に)的を射ていると思いますよ。私がstomachmanさんを混乱させてしまったのは、言葉をちゃんと定義できなかったからです(対称性についてもそうです)。

 ホントにグラフプロパーの方じゃないんですか?

補足日時:2001/03/18 15:46
    • good
    • 0

みたび、再帰性についてです。


K(d,k)はK(d-1,k)を部分グラフとして含んでいます。K(d-1,k)は、アルファベットA
のなかのどれか1文字を使わない、という語だけからなる部分グラフですから、
K(d,k)に含まれるK(d-1,k)は(d+1)通りあります。
同様にして、それぞれの部分グラフK(d-1,k)はd通りの部分グラフK(d-2,k)を含んで
おり、..... それぞれの部分グラフK(2,k)は2通りのK(1,k)を含んでいます。
ですから(共通の語があるので)分割はできませんが、このような入れ子構造になっ
てる。これが「再帰性」のもう一つの意味ということでは如何でしょうか。
    • good
    • 0
この回答へのお礼

 stomachmanさん

 もちろんそれも「再帰性」といえないことはないと思います。が、それは言葉の定義のしかただと思います(私はこれを厳密にできませんでした)。グラフの世界ではこういうことはいわないでしょう(ただし、Xというグラフの中に別のYというグラフをembeddingすることができる、ということは論文になります)。

お礼日時:2001/03/19 15:52

 なるほど、「どのノードから見ても同じに見える」とおっしゃる意味がやっと理解できました。

先にstomachmanが書いたのは語の文字を置換する話なので、語の構造を保存するような変換しか許しません。この意味での対称性は自明ですが、語の構造が違う任意のノード同士を対応付けることはできないですね。ですからご質問の本来の意図における「対称性」に関しては、多分「対称でない」というのが答だと思います。実際反例を挙げていらっしゃるのだから、あとは「対称性」をきちんと定義しさえすれば、問題は解決したことになるのでは?

 「再帰性」に関しては、もっと美しい構造があるのかも知れませんが、何しろ初学者なもので....

 なお、Kautz digraphはk文字分の記憶を持つ非同期の有限オートマトンの状態遷移図(つまり入力が変化した時に状態遷移を起こし、新しい入力がcであるとき<pR>→<Rc>へ移る)と見なすことができるように思われます。
    • good
    • 0

●仰る意味での対称性は自明に成り立っています。


stomachmanが書いたKautz digraphの定義において、語をノード(頂点)と同一視していることがポイントです。アルファベットAの要素を適当な順番で枚挙したものS=<a[0],a[1],a[2],a[3],......,a[d]>を決めて、写像fをたとえば
f(a[d])=a[0], f(a[n]) = a[(n+1)] (n=0,1,....,d-1) z
と定義します。さらに語x=<x[1],x[2],....,x[k]>に対しても、
F(x)=F(<x[1],x[2],....,x[k]>) = <f(x[1]),f(x[2]),....,f(x[k])>
と定義します。
すると、あるKautz digraph K(d,k)に対しても
F(K(d,k)) = K(d,k)の各ノードxをf(x)で置き換えたもの
が定義できます。このとき、F(K(d,k))=K(d,k)となることはK(d,k)の定義から自明でしょう。一般にSをどのように並べても良いし、fは置換でありさえすれば何でも良い。
 この先、厳密な証明を書き上げるのはお任せしましょう。

●また、再帰構造をしているか(あるサイズのKautz digraphを、更に小さいサイズのいくつかのKautz digraphに分解できるか)に関しては、きちんと議論するには再び「分解」の意味を確認する必要がありそうですが....
 d=2ぐらいで見ているとdを変えたときに再帰的になっているような気がするかも知れません。ですが、たとえば(A-{a[n]})というアルファベットを使って作られるグラフK(d-1,k)[n]は、K(d,k)の中に埋め込まれています。もちろん取り除く文字がn=0~dのどれであってもK(d-1,k)[n]はK(d-1,k)と同型です。K(d-1,k)[n]の語のうち、文字a[m](m≠n)をa[n]で置き換えたものを考えると、これはK(d-1,k)[m]に他なりません。文字a[m]もa[n]も含まない語だけによる部分グラフK(d-2,k)[n,m]は、K(d-1,k)[n]とK(d-1,k)[m]に共通です。だからK(d,k)はK(d-1,k)[n]とK(d-1,k)[m]とには分解されません。

●むしろ「再帰性」と仰っているのは以下のような意味ではないでしょうか。
 K(d,k)の語の集合をW(k)とします。K(d,k)において語 <pqR> (1文字目がp、2文字目がqでその後に長さk-2の文字列Rが続く語)から出ているアークが繋がっている語の集合は{<qRc>|∀c∈A∧<qRc>∈W(k)}ですが、<sqR>(∀s≠p)に対しても{<qRc>|∀c∈A∧<qRc>∈W(k)}が繋がっている。K(d,k-1)を考えます。つまり語の最初の文字が何であっても同一視し、K(d,k)の語d個づつを一つにまとめてしまうことにします。すると、K(d,k)における<pqR> も<sqR>(∀s≠p,q)も一つの語<<qR>>にまとめられてしまい(K(d,k-1)の語は<<>>と書くことにします。)つまり<<qR>>={<pqR>|∀p∈A∧<pqR>∈W(k)}、それに繋がるのは{<<Rc>>|∀c∈A∧<<Rc>>∈W(k-1)}である。ここに<<Rc>> = {<qRc>|∀q∈A∧<qRc>∈W(k)}。
 そこでK(d,k-1)において、<<qR>>→<<Rc>>という、一対の語と一つのアークにまとめられちゃったものが、もとのK(d,k)ではどういう構造を持っていたかを反省してみますと、まず
{<pqR>|∀p∈A∧<pqR>∈W(k)}→{<qRc>|∀q∈A∧<qRc>∈W(k)}
というアークに関してはそのまんま束ねられただけです。問題は{<pqR>|∀p∈A∧<pqR>∈W(k)}の要素間でのアークがどうなっていたかですが、<pqR>∈W(k)だからp≠qであり、従って{<pqR>}の要素同士の間にはアークは存在しない。また、{<qRc>|∀q∈A∧<qRc>∈W(k)}の内部でのアークはどうか?これも最後の文字が全部同じcであるから、相互にアークは存在しない。
 従ってK(d,k)の語長kの語(互いにアークはない)について、最初の文字だけが異なる物をd個まとめて語長(k-1)の一つの語と見なすという操作は、実に単純な構造を持っています。この縮約をkをひとつづづ減らしながら幾らでも行うことができ、最後にK(d,1)に行き着きます。これは(d+1)角形の完全グラフに他なりません。
 たとえばK(2,3)位で眺めてみる(Excelか何かで、グラフを行列で表現してみる)と、K(2,2)と同じ構造をしているのがよく分かると思いますよ。

◎ついでながら、ぜひKautz digraphがどんな分野でどのように使われるものなのか、簡単な解説を補足していただけないでしょうか。Stomachmanも今回初めて勉強したもんですから....この話専門的すぎて分かんない、という方(stomachmanを含む)のためにも。

この回答への補足

 stomachmanさん、再びどうもです。

 対称性についてですが、だんだん分からなくなってきました。

 下に書いたように、私は対称性のことを「どのノードから見てもグラフが同じように見える」と認識していたので、今までKautzグラフは非対称だと思っていました(なぜなら、例えばK(2, 3)ですとノード010を含む長さ2のサイクルが存在しますが、ノード012についてはそのようなサイクルは存在しないからです)。しかし、自己同型写像が存在するか、ということでいえば、恐らくするのでしょう(詳しく詰めてはいません)。

 また、再帰構造についてですが、どちらかといえば上に書かれたことが私の意図しているものに近いようです。具体的にどのように書けばいいのかが分からないのですが・・・。

 例えば、hypercubeを例にとりますと、n-hypercube はふたつの(n-1)-hypercubeに分割することができます(ノードを余すことなく)。また、n-star graphは、n個の(n-1)-star graphに分割することができます(こちらもノードは余りません)。同様に、K(d, k)が例えばd個のK(d-1, k)、またはk個のK(d, k-1)、さもなくばdk個のK(d-1, k-1)に分割できるのか、ということが知りたかったわけです。ここでは、いくつかのノードを束ねる、ということは考えません。

Definition 1: An n-dimensional hypercube consists of $2^n$ nodes whose address are represented by n-bit binary numbers. A node x has n adjacent nodes whose address are ontained by reverting, one by one, each bit of its address.

Definition 2: An n-dimensional star graph consists of $n!$ nodes whose address are represented by the permutations of the set {1, 2, ..., n}. A node x has n-1 adjacent nodes whose address are ontained by interchanging the first symbol with the ith symbol.

 Kautzグラフの用途についてですが、別に他のグラフと違った使われ方をするものではありません。このグラフの特長としては、直径に対して頂点数が多いということが挙げられます。

補足日時:2001/03/18 05:28
    • good
    • 0

先ず用語の確認からです。


●「Kautz digraph」
Kautz digraph, あるいはdirected Kautz graphのことですね。(Kautsじゃないです。)
K(d,k)は以下のように定義されているとして良いでしょうか?
まず(d+1)個の要素を持つ文字の集合(アルファベット)Aが決まっている。そして、この文字k個を連ねて語xを作る。すなわちx=<x[1],x[2],....,x[k]> (x[j]∈A, j=1,2,...,k) ただし、この語の中に同じ文字が2文字続く所があってはいけない。このような条件を満たす語の集合をNとすると、その個数は|N|=(d+1)(d^k)である。
 この|N|個の語をノード(バーテックス)とする有向グラフを考える。どのノードx=<x[1],x[2],....,x[k]>についても、<x[2],x[3],....,x[k],c>である全てのノード(もちろんc∈A, c≠x[k])へアーク(エッジ、辺)が繋がっている。(その他にはアークはない。)

●「対称グラフ」
どのアークについても、ノードxからノードyへのアークがあるならば、必ずノードyからノードxへのアークがある。(つまり無向グラフである。)

 こういう意味で宜しいでしょうか。だとしますと、答はもう自明でしょう。
d=2, k=2の場合を考えてみると<01>,<10>,<12>は確かにK(2,2)のノードである。で、<01>←→<10>ですが、<01>→<12>に関しては<12>から<01>へのアークはない。だから対称になりません。

 ではd=1の場合を考えてみますと、kが偶数のときノードは<010...1>,<101...0>の2つしかない。kが奇数のときは<010...0>,<101..1>の2つしかない。いずれも対称グラフになります。

◎どうもご質問における「対称」の意味が、この回答とは微妙に違っているようにしか思えません。(余りに自明だもん。)お考えになっている「対称」を定義していただけませんでしょうか。

この回答への補足

 stomachmanさん、回答ありがとうございます。

 回答を見せて頂いてから気付いたのですが、私が知りたいのは対称かどうかではなく、再帰構造をしているか(あるサイズのKautz digraphを、更に小さいサイズのいくつかのKautz digraphに分解できるか)でした。すいません。お詫びして訂正します。

 ところで、「対称」の定義についてですが、stomachmanさんのと私のとではかなり違うようです。私の中では、「対称」とは、平たく書けば、「どの頂点から見てもグラフが同じように見える」ということです(堅く書けば、グラフの任意の二頂点i, jに対して、iからjへの自己同型写像が存在するということです)。ちなみに、Kautzと並べられることの多いde Bruijnは対称ではなく、再帰構造もしていません。hypercubeは対称ですし、再帰構造をしています。また、rotator graphは有向グラフですが、対称で再帰構造をしています(と私は認識しています)。

補足日時:2001/03/17 17:26
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q小数点以下が0になるときの考え方について教え得て頂けると幸いです。小学

小数点以下が0になるときの考え方について教え得て頂けると幸いです。小学算数の指導方法は理解できました(下のサイト)。たとえば12.0という数字では、実測に関する場合には小数点以下の0が有意味で、それ以外は無意味ということになり、無意味な数字は表記しないことが原則となるようですが、このことは、数学ではどのように説明されるのでしょう。整数の範囲であれば、整数論に関する文献を当たることも可能なのですが、こういう問題は何の分野になるのでしょうか。
http://oshiete.goo.ne.jp/qa/5884510.html

Aベストアンサー

物理や化学の分野でよく使われています。
広く言えば測定が関係する、または測定が前提となった数字を扱う分野ではすべて扱います。
「有効数字」という言葉であらわされている数字の扱い方です。
数学的には「誤差論」が背景にあります。(ガウスの「誤差論」というのがよく知られているようです。)
加減・乗除について材料となった数字の誤差が演算の結果の数字の誤差にどのように反映するか、したがって信用できる部分はどれだけであるかを議論しているものです。

普通の数学では測定を前提にしてはいませんのでほとんどの数学的な記述には有効数字は考慮されてはいません。πの値を~万桁出したというようなことが書かれている場合があります。こういうことは自然を記述する数字としてはあり得ないことです。10桁の数字が書かれている文章があれば執筆者の能力を疑ってかかってまず大丈夫でしょう。普通、信用できるのはせいぜい5桁以下の数字です。特別な定数で10桁近い値が得られているものもあります。でもその値は現在得られている最高の精度のものであるということであって、普通の測定で得られる値であるということではありません。
有効数字の桁数を上げることに意味のない数字もかなりあります。
(「桁」という言葉にも注意が必要です。「有効数字」の桁数という時と位どりの意味での桁数とは意味が異なります。位どりの意味での桁数は有効数字の桁数ではありません。測定の精度に関係なく、単位の取り換えでいくらでも変わります。1mは1000mmですから3桁変化します。)

「有効数字」という言葉が異なった意味で使われている場合がありますので注意が必要です。
数値計算の分野(コンピュータの内部処理)の分野で使われている「有効数字」の意味は物理や化学で使われているものとは異なります。コンピュータの中ではほとんどの数字が無限小数として出てきます。どこかで打ち切って次の処理に回さなければいけないのですが打ち切り方が問題になります。最後の数字の扱いも問題になります。これはJISで決めています。(JISにのっているということで工業系の人は「有効数字」というとこの意味だと思っている人が多いです。)
有効数字に慣れてない人が有効数字について知りたいと思ってJISの規格を読むということをやるとおかしなことになります。JISで扱っている数字は測定を前提にしてはいません。有限の桁数の数字(コンピュータの内部処理の有効桁数以下の数字)が出てくればこういう扱いの対象にならないのです。整数が出てくればいつも誤差なしの扱いです。
測定を前提としていて23と23.0は意味が異なるという意味での「有効数字」とは全く別物であることが分かります。
大学の入試問題などではこの食い違いが原因ではないかと思われるおかしな数値がよく目につきます。
自然科学的な立場で言うと欠陥問題である、答えの出ない不十分な数値しか与えられていないおかしな問題であるとしか言えない問題が目につきます。

物理や化学の分野でよく使われています。
広く言えば測定が関係する、または測定が前提となった数字を扱う分野ではすべて扱います。
「有効数字」という言葉であらわされている数字の扱い方です。
数学的には「誤差論」が背景にあります。(ガウスの「誤差論」というのがよく知られているようです。)
加減・乗除について材料となった数字の誤差が演算の結果の数字の誤差にどのように反映するか、したがって信用できる部分はどれだけであるかを議論しているものです。

普通の数学では測定を前提にしてはいません...続きを読む

Q次の課題について適切な統計手法を教えて頂けないでしょうか?

お世話になっております。

子供の属性(実の息子/実の娘/義理息子/義理の娘)ごとに、親の居住状況(同居・近居・遠居)の割合がどのように違うかを、
特に、「近居」の割合に注目して調べています。

現在クロス集計は作りおえ、割合の算出はできたのですが
この割合が有意味であるかどうかを調べるために、
どのような統計的な分析手法があるのかわかりません。

カイ二乗検定によって、子供の属性ごとに全体の割合について独立性が存在することは分かるのですが、
特に「近居」だけに注目した場合に、子供の親族属性ごとに割合の相違が有意味であるかどうかを調べたいと考えております。

アドバイスをいただけませんでしょうか。
どうぞよろしくお願い申し上げます。

Aベストアンサー

つまり{近居と実の息子}、{近居と実の娘}、{近居と義理息子}、{近居義理の娘}というように対比較したいということでしょうか?

それなら多重比較ですね(http://shiriuskun.srv7.biz/toukei_hosoku/cross_table_analyse.htm)。

QΣ[k=1→n]k(k+1)(k+2)・・・(k+(m-1))を積の形にしたい。

皆様、こんにちは。

表題の通りなのですが、
Σ[k=1→n]k(k+1)(k+2)・・・(k+(m-1))を積の形にしたいのですが、
やり方が分かりません。
一応答えは分かっているのですが、導き方が分からないのです。
証明は帰納法でできると思います。

Σ[k=1→n]k(k+1)(k+2)・・・(k+(m-1))を積の形に簡単に直せる方がいましたらそのやり方を教えてください。
よろしくお願いします。

Aベストアンサー

「積の形」というのがよく分かりませんが、Π[k=1→n]・・・みたいな形にするということなら私にはお手上げです。
でも「単に和を求めろ」ということでしたら、ヒントを。

簡単のためにm=3で考えると、
1・2・3=1・2・3・4/4
2・3・4=(2・3・4・5-1・2・3・4)/4
3・4・5=(3・4・5・6-2・3・4・5)/4


n・(n+1)・(n+2)=(・・・・)/4
ですよね。
両辺をザザーっと加えると左辺がΣ[k=1→n]k(k+1)(k+2)、右辺がいちおう「積の形」になります・・・

Q数学の問題について 次の画像の大問5と6番解いて頂ける方いましたらご回答お願い致します。(´;ω;`

数学の問題について
次の画像の大問5と6番解いて頂ける方いましたらご回答お願い致します。(´;ω;`)

回答は白紙やノートに書かれた画像でも大丈夫ですのでお願いします。

詳しくは画像をご覧下さい。

Aベストアンサー

どこがどのように分らないのでしょうか。
具体的に質問した方が、より良い回答が期待できますよ。
詳しく書かれた回答を丸写ししても、勉強にはなりませんよ。

問5
(1)、DからBCに下した垂線の足をMとする。
    題意よりCE=BC-BEですから CE=3cm。
    ∠DECの角度から∠DEMが解ります。
    直角三角形DMEから三平方定理によって、
    EM及びDMの長さが決まります。
    したがって△DCMも三平方定理からCDの長さを求められます。

(2)、三角形の面積は底辺と高さが解ればよいですから、
    底辺をBE,高さは(先ほど求めた)DMで、簡単に求められますね。

(3)、線分AEとDMとの交点をNとすると、△ADNと△EMNは相似形になりますよね。
    AD:EM=AN:EN=DN:MN ですね。
    DMの長さをAD:EMに内分すればDN,MNが求められます。
    一方△ADN(又は△EMN)も直角三角形ですからAN(又はEN)の長さが求められます。
    つまり△ABEは底辺をAE、高さをBHとみれば、(2)の面積から簡単に求められる筈です。

問6 すみません、回答を書いている時間がありませんので、
ご自分で工夫して頑張って下さい。

どこがどのように分らないのでしょうか。
具体的に質問した方が、より良い回答が期待できますよ。
詳しく書かれた回答を丸写ししても、勉強にはなりませんよ。

問5
(1)、DからBCに下した垂線の足をMとする。
    題意よりCE=BC-BEですから CE=3cm。
    ∠DECの角度から∠DEMが解ります。
    直角三角形DMEから三平方定理によって、
    EM及びDMの長さが決まります。
    したがって△DCMも三平方定理からCDの長さを求められます。

(2)、三角形の...続きを読む

Q小6算数 対称な図形 (線対称)

下の図でA君はア地点から、川に行き、川で水をくみ、その水を池に入れてから、再びア地点に戻ってきます。
A君はどのように進めば最短距離を行く事になりますか、図に書き込みなさい。です。

Aベストアンサー

アから川岸に垂線を引き、アと川岸との距離と同じ距離のところをア'とします。
また、アから池の岸に垂線を引き、ア問い家との距離と同じ距離のところをア’’とします。
ア’とア’’とを結んで、川岸との交点をイ、池の岸との交点をウとします。
アとイとウを結んでできる三角形の道が最短距離になります。


人気Q&Aランキング

おすすめ情報