情報工学教室 永松正博 On Algorithms Which Generate Random Trees

ランダムツリーを発生するアルゴリズムについて

      （昭和54年5月31日原稿受付）

情報工学教室 永松正博

On Algorithms Which Generate Random Trees

       by Masahiro NAGAMATSU

      」㌔bstract

  In thi5 paper we consider the problenl of generating trees at randol11・ Here問at raIldonゴ

means that each tree｛each node of the tl・ee has a lavel alld is dl5tinguishable from lhe others〕has

  There have been three algoritllms which generate trees， The first is very primitive． It

9，、e，ates g・・ph・wl・i・h h・v・…。des・・d，・−1・dg…n・・ft・・a・⑪th・r Lmtil1…n・e・t・d g・・ph i・

9，，，，at，d． B・t if we u・e this meth・d， w・filld th・しth・・ve・・g・an・・u・t・f time p・・t・ee i・

郎eater thanα、日r（θ／2）り．

  OII the otller halld、 the secolld and tlle third lnethods｛see｛3）for example）can generate tree5 in polynomial average time per tree． But they camot gellerate at random． If、y・e use them， we filld that tlle ratio of tl〕e probability of the most frequently gellerat但d tree alld the probabiHty of th， m。、t，a，，ly 9。ne・at・d t…g・・ws・e・y・1・i・kly｛白卜1｝！・・d郎・・…tha・ O（（・雨加1／・・〕

respectively）．

  After sh。wil、g th。・e， w・p・…nt…19・・ithm whl・h ge…ates t…s・t・and・m i・ti1…0（・｝

per tree．

      る。点の個数と辺の個数を与えてランダムにグラフを発

Lまえがき        生させ漣齢否かを・碇し漣結なグラフができ法

ある観のグラフに関するある問題を解く計算機プログ   で，ランダムグラフの発生を繰返せぱよい。しかし・こ ラムを作り，その性能．たとえば処理時間が問題の大き   の方法は．辺の個数が点の個数に比べて非常に少ないよ さの増加に従ってどのように増加してゆくのかとか，プ  うな連結グラフを発生する場合には使いものにならない

・グラム中のどの部分の処理に1硅も時間を費して幡の くら嚥1肪かかろ・ここでは・辺の隔の嗣少ない かとか，どれくらいの記憶容：駄を要するか等を検討した   連結グラフ，すなわちツリーのランダムな発生を考える。

h場合や，いく種類かのプログラムを作りそれらの性能   まず，前述の原始的な方法では1個のランダムツリ を

ラムが対象とす5範囲のグラフ（たとえば，平而グラフ   ぎに，点の個数が与えられている場合・ツリーを発生す

ラ・であるとか〕をランダムに難する必要が生じる。 ンダムというにはほど遠いぽどカ たよりのある麟でし

1禎の個故と辺の密度が与えられる場台以外，ランダム   リーを非常に効率よく発生させる方法を示す・

ll酬生する効繊い方馴1ら』・ていない・た 2淀義

こえば・点の個数と辺の個数が与えられてしかも迎結で

あ砺フをランダムに難する聯り筋齢擁す 餉グラフを〔エ1∫）で抽す・ここで工脚）賠

162

で，び⊂Xx Xである。びの要業を弧とよぴ，（泊，エ：）の       ， START 形で表わす。弧の方向を無視したグラフを無向グラフと

よび（X，E）で表わす。すなわち、E⊂ダパX）である。

ここで．虜ユ（X）は正の2元部分集合である。Eの要素を辺

       刀頂点ハ∫−1辺の

  皆（）1，，川＝｛無向グラフG￥。，E川lEl＝，η1と

リズムをπ頂点，，｝〜辺のランダムグラフを発生するアル        NO

ゴリズムという。      YES

．ダ｛川＝1無向グラフG＝（X元，E）lGはツリーであ

る｝      END

とする。王（川の要素をすべて等確率に発生するアルゴ      図一1 最も原始的なアルゴリズム

リズムを｝1頂点のランダムッリーを発生するアルコ リ

ズムという。

 グラフ理誼の諸定義は文献②に従う。      であることが示される。実際計算機で計算すると，

3・種袖アルゴ1以ムの解析       α。）

3⊥最も原拗なアルゴリズム     研・酔 ^一・ O．1田……（ヌ7−→QO）

 図一1に最も簡単なアルゴリズムを示す。このアルゴリ   である。すなわちG（｝の＝0（、信｛e／2）叶である。

ズムはランダムツリーを発生するが，時間的効率が非常   ｛訂2｝≧1であるので，これはG白δ，すなわち，ツリー に悪い。ここでは，この効率の悪さを定量的に示す。    を1個発生させるまでに平均して待ち時間が指数関数的  このアルゴリズムが図工におけるループを平均何回ま   に増加することを意味している。たとえば，〜＝100の時 わるとツリーを1個発生するかは次式で示される（成功   G（，〜）≒2xID」3になる。

の確率がPである試行がはじめて成功するまでには，平    3ユ．ツリーを順次大きくしてい（方法

均（1 う回の試行を繰り返さなくてはならない。）   図一2にアルゴリズムを示す。この方法は，スパニング

  序（、1，，，−1）1      ツリーを作る時などによく勘れる；憶嚥たとえ

       からなるツリーを作り，次に，このツリー上の任意のl l哲（，1，」1−1）1＝♪禦C・−1であり，1刀1」）1＝鍵7n4   点とそれ以外の任意の1点を結び3点からなるツリーを であるコ吻でG〔」r）はつぎのようになる。         作り，次に……と繰り返し，η点からなるツリーを作る        方法である。この方法は0〔 1）の時間で1個のツリーを

  G｛H｝＝  か，       発生する。しかしながら，ランダムなツリーは発生しな        ヨエ

   ー詞1−2）！亘1（       2「（，1−1）一       ，〜）  い蒜芸誼リ繊図．3（、臓示すツリー

・≦｛2軸≦1筋るので     を発生する麟を勅・そ砒を計財る・図一3（・｝に示

       すツリーの場合，辺el、 eコ，…， c。．1をこの順番に発生

2；睾詩鋼棚言等  す纏は

一ング⊇使、聯すると，，＞1。0の場合， 恒：rx（i−r）＝（｛，、』Ul）2

0．3」万（42P≧C（，1）≧0』3、ノ7142P       である。（a）の場合，辺は任意の順序で発生できるから，

START

y＝｛エJ E＝φ

・       ．r片＿宝

    工1

工昂一1      」ご

γ一X．YEs @   X 烏臼ノ

       END         ＼     ／  No       ＼ ＿ ノ

」・ ﾃ王，．ピε冗n−F

をランダムに選ぶ。

五＝EU｛〔ピ．−rつ｝

γ＝｝ノULピ1

（乱）

工」

・τハ    」ごコ    ーr3         工η一1   ．τ町

○古☆。：…一〇一〇

       Cn−；   ｛撒．＿1

図一2ツリ＿を鰍大きくして     図一3b）最端率で発生さ栖

    ゆ（方法      ツリー

      （b）最小確率で発生される

㈲を発生させる確率は      

｛・・−1）！・（b、』1）！アー白，』1）！

である。一方（b）の場合，辺は凸，ε：，…，β国の順番 でしか発生できない。故に〔b）の発生率は，（a）の場合と 同様に計算されて

ST、へRT

（    1（」卜1）！）2

である。

 以上の考察より，（司が最大確率で発生され，（b｝が最

小確事で発生され，その比は（η一1｝1であることがわか る。したがってこの方法で発生したツリーはランダムと

 3．3．閉路ができないように辺を加えてゆく方法

｛，12｝の時門で・ツリーを発生するどしかし，ランダムツ       YEs リーは発生しない。以下図一3（a｝に示すツリーをこのア        ルゴリズムが発生する確率を示し，（最大確率／最小庄       ENII

率）が崎大きくし塒志速に大きくなることを示す・   図＿4閉路がで純、・ように辺を 辺が副e，，…e祠酬i番で発生される確率は       加えて蝋方法

164

⊥X 1。 1X＿X ］         ST帆RT

ηC2 ηC2一コG  πC2−3C2   ηCゴー，1−1C2       2n−1

（1r−］）！（2」〜−2｝（2，〜一一3｝・・一〔2H−，o）       ，

であろ。辺が発生される願番は（」1−1〕！通りあり、その

いずれもが上記の確寧で発生されるので，図一3｛a）に示 すツリーが発生される確率は

］

（    ワ」〜一丁   一）（・号）・・一（・・一丁）

である。分母の各因子のうち右側のレ〜／2］個はいずれも

（ノト白ノの）以下であり，左側のη一1−［〃／21個はい

ずれも〃以下である。したがって上記の確辛は

1

・《÷）］

以上となる。

 一方1，ブ （」〜月＝」〜 「弓である：1ので，ツリーの中には，

1／白ノよ一り以下の確率で発生されるものが存在する。故

に

緩〉毒「鵠     憶

入力：∫f，εΣ打 ご

1｛」∫ぽ1エ，…エη

ﾜ＝φ

lFの中に1回だけ出てくろ文   嘯 さがす。それ・うのうちIF ﾌ中で酷初にあらゆろものを

､とす6。

撃eの先頭の文字をZ「とする。      IH ＝IIノからyとZを消三芒

@ したもの

@      操1相

NO _lr＝空語 YES

となり，これは髄こ大きくなる．たとえば。＝1。0のと   図一5 ：Σ 】一ごイω

き，約1伊になる。したがって文献U｝に述べてあるアルゴ

リズムは正しくない。       てある操作1の中では，yをIP中で1個しか含まれな

4・ラン蜘・トを発生するアルゴ1」ズム @㌶㌶漂㍑と㌶；よ盤蕊

 工h追，…，礼，を文字とみなしΣ＝占，炬，…，㌔i   単に／」を確定したものにするために，適当にきめてやれ

部コである。以下にΣn一コの元IPから∫b1）の元1」（rのを    操作1を実行する時のWを前半，後半の2つの部分

数∫」は単射であることが示され，したがって1」は全単    IFの前半・…・・始めに与・えられた （」の部分（図一6に示

射である。Σf：コの元を等確率にラングムに発生するのは      す例の点線の左側の部分）

簡単にできる。したがって変換〃をつかえば．デ（川の元    Wの後半・…・・始めに与えられた甜の後につけられた をランダムに発生できる。    一       項，ぷ．…，エ．の部分｛図一6に示す例の  Σ コと．ア（川の問に圭単射の存在することは，1ノー         点線の右側の部分〕

白r）1＝パ」2の証明2，から直硯的にもわかることであ

ろこまた文嶽目1にツリーワードという言葉で述べられて   〔譲1題］〕 操作ユは必らず実行できて，その時1γの前 いる。ここでは、文献（4｝とは鍵なった全単射を述ぺる。   半にある文宇はすぺてIPの後半にもある。したがって・

 変顯∫∫のアルゴリズムを図一5に示す。図一5の中に示し  操「乍1で選ばれるyはll〆の接半にある凸

㌣   ㌢_{ユ      ．L}

簗吉識㍉＿秩轟忘埠＿鷲

       詩いぽi‥畠＿京＿＿→ 』兵D

        一     ま   ㌔｝ゴ          1べ皐

      ○一：一違一一一一→㌧茸⊇

       違づ違兵…  き属

      醤i蓮…   

き・』≧

        iC籔一一一一→一

睡一6∫＝・｛：拒ぽ・…，轟｛：斑とき      掛＝＝ユs丑最浜証に粛Lて      ぎζ緒きを志と・轟る違壼を皐      す剖

  ξ証轡 警作1を婁汚丁毛籔巨に園す悉藻議法で≡  毒註｝こ静≡：霞亭巧二至蓬i二きご聴しな■文享㌻注吉

巳奪蔓棄±‡す畦て言ま託てい主顯こ蕪題1±類らかiこ惑  繧「三よ摯工fぎ三垂一玉琶§蕊跨違に±註く葺トご違事［二

立す㌻       存在Lな渋一｛ξな法なr・膓。す蕊毒』≧渡蓑蕊蔑稼こ

 圭一1函窪難話二謹琶が鼠立す轟と握定して声薗巨に  お 膓てぷ』±野■前1≒にき窪半に三春藍てミ主一忘毒一 蔑立す芒にとを示r㌔懸蟻注口療憲こよ竜孟蟹目導雲行  1諺E鱒欝俸で‡t潅｝誓≒毒≡葬鱈．芸ζこ：主i董㌃竣こ 直誌鰐点に君い主皆郵前半｛コ±高身才‡一た一玉撞顯  ｝衰し卓出謬Lな臼文字で皇ミ』もた誤ゴて。こ㌻薄．

び墳宇吉清ま蕊塗半｝こ鷺H一吉÷』蓮寿勧文宇が含まれ  1罫惑裟半f紅㍊湧某き巌墨こと註も・。註：二垂璽彗毒        婁行蒔にもぽ嚢塗≒≦こ茸に鷲二・主詰≡ロこ鉦窪彦霊這

       蓑  鴛：繁ぎ叢墓驚巳蕊

       x      半に存童す垂文享是許三「｝…≒：ζ鍵言㌻註…こ屋⊆・

      ノぐ驚讐塞∵．

       れ顯塾口☆已アとし三選｝ぎきこきさ

   ．τ雪

⊂） ・．．   一・    ｛蕊謬書謬詩，〔エゴ共．か⌒簗鍵

      ＿       を誕ゴ患して汗避芝i≡言に皇磐鷲鉦丁㌻養逗㌻壼ざ惑

四蓼；㍗『註  吉癒μ泣繰コ縦一鷲蕊

166

を選び出す｝・摘題1より王は常にII の後半にあるの   （的，切が選ばれること（すなわち占が1｛ノの先頭にあ で・すぺてのエ・εX・に対してぱ底）≦1である｛正確  ．ること）と矛盾する。故に∬（〜のには閉路は存在しない。

に言うと最後に選ばれるZに対してのみ∂ヰZ｝；0で   H（〜叶は」卜1本の辺を含み，閉路をもたないのでツ あり．その他の点苛に対してはゴー（エ」＝1である）。し  り一である。       □

たがって上記の方法で有向グラフ化した∫∫｛」のに閉路       

μが存在すると仮定すると，μは初等有向閉路でなくて   〔系2〕 摘題2の証明の中で定義した有向グラフ化を はならない。そうでないとすると，亙一馬）≧2の点が存   するとJJ（副はアウトツリーである。ここでアウトツ 在しなくてはならなくなるからである。またμ上には，   リーとは根とよばれる点をもち，根からすべての点へ有

（エ ，エ．1｝，｛．r」，エ」という2つの弧で，アルゴリズムにお   向道が存在するような木である。 H価）の根は，最後に

いて巨，，垣｝の方が〔㍉，エh｝よりも先に選ばれているよ  選ばれたZであろ。

うなものが必らず存在する。（毛，エ、）が選ばれた時にはエ」

はIF中には1回しか出限していない。これは，その後   〔系3〕 アルゴリズムで選ばれた弧を，選ばれた逆の

START

1≦f≦，〜なるすべての∫に対して NUM〔f）・−1

       Eσ）−0

］≦「≦」卜2なるすべての〆に対してAUい一「，1xRAND「＋ユ

κ一1

γ・−PD

E（z｝・一｝

NuM（z）・−NUM（z）−1

z−∫，D

｝㌔一、PD E｛z］一王

図一8 ランダムツリーを発生するアルゴリズム

鰯に並べた胴考焔・この列は・最歓選ばれたZ す。ここではΣ＝｛L2い．．」壮してある．各魏，

を根とするアウトツリー剛次弧をっ1部えて大きくし 悶馳次の瑚…をもつ。

栖剛になっている・       A−・…・大き細一2の配列で胸・入る。

  （証明） 系1，系2，よワ明らか       ［コ    ∧fロ遅・・大きさ刀の配列で∧「ひM（「｝は1γ中品文字∫

      の個数を表わす。        ，

ラフとして見る時は・上の方の点から下の方の点へ矢印       表わす。

が向かっていると見ればよい・      PD・…・プッシュダウンスタックで｝！一ノ〕Dは∫口を  また・明らかに1｛㌦エb㌔…・㌔の中の断の出現回        ポップアップしてγに入れること，PD・−r

数が」∫（1のにおける山の次数になっている。      は1「Dに｝・の値をプッシュダウンすること       を意味する。

〔捕題3〕 rl）1・〜 ］三EΣ 1』2とする。〜（ノ1土r ・2ならば1J   RAND・1・（0，1）の一様乱数を発生させる関数であ

｛〜（け字H（〜山である。      る。

  （証明） 1｛∫1と趣の中のエ，の個数が異なるような    このアルゴリズムは，出限回数が1の文字をPDに入 叫が存在するとJJ価1）とH（蛙〕は聯の次数が異なる   れているが，二のようにしてもよいのば，鼎題3の証明 ので明らかに異なる。故に，すべての「に対して1（・1と  よ1）明らかである。

1｛」2の中の岳の個数が同じ場合を考えればよい。

  川＝即｛，1      ・       〔定理2〕 図一8に示すアルゴリズムは0〔川の時間で

  〜t1の長さは占      ・

  1，ぺと、、棚醐破字は異なる    5・あとがき

と仮定する。さて，貼にアルゴリズムを適用してゆく過    一殻に」】個の点．〜川箇の辺を含む連結グラフをランダ 程と晦にアルゴリズムを適用してゆく過程を並列にた   ムに発生する問題は， 〃が小さい場合まだ効宰の良い解

どってゆこう。占回操作1を実行するまでは，両者共に   法が知られていない。ここでは川が最小の場合（すなわ まったく同じ動作をし，同じ辺を選び出す。なぜならそ   ち，川＝η一1）について考察した。3．1．では，原始的

冊のみに依存した動作をおこなうからである。〜｛，；，王口の   3．2．，3．3．においては従来知られているツリーを作る方

先頭文字をそれぞれエ，，㌔とすると，荊≠㌔であり，  法が，ランダムツリーの発生には使えないことを示した。

距＋1回目の操作1の実行では，柘の先頭には，それぞれ   しかしながら，4章で述べてあるように，川＝η一1の 土輌、㌔がくる。また，1ドに］回だけ出現する文字は共に  場合には， 1Σ1＝〃であるようなアルファペット上の 同じものであるのでこれを巧とおく。占十1回目の揮1乍  長さ」1−2の語の集合と，ツリー全体の集合の間に全単

1の実行で選び出される辺は，それぞれ，〔ぞT∫旬  ザt．，〕，〔与，  射が存在することよ1〕，きわめて効率よく（ツリー1個 苫、〕である。止回目以前には両者共同じ辺が選ばれ，占＋   につき0ω｝の時間で）ランダムな発生をおこなうこと

2回目以後では占に隣接する辺は選ばれない（なぜな   ができる。ツリー以外の場合，たとえば，川＝ηの場合 ら，もはやIIノ中に毛は存在しないから）ことより∫」  には，ツリーの場合のような都合のよいコーディング方

｛ t1」≠H（幌）である。故に〜f）1≠1↓）。ならぽ∫ゴ（1｛FJ甲   法がまだ知られていない。あるグラフの集合の要素をラ

∫∫｛f吋である。      ロ   ンダムに発生する問題は，すでにランダムに発生するこ        とができることがわかっている集合へ1対1であるよう

〔定理1〕 1子：Σノ」コー・王（，1｝は全単射である。     なコーディンダを上手におこなってやろことが解法への

 （証明） 補題2，捕題3より明らか。     口   ひとつのアプローチであると思われる。

図一8にランダムツリーを発生するアルゴリズムを示

1酪

      参 考 文 献

1｝高見沢他： ランダムグラフの慌計的解折印情報処理学会諸文誌  Vo1，19｝qo，8 1978，

2）Berge，C．； Graphs and Ilypergraphs North−Holland正〕ub．      −

Comp．］97＆

3）Christofides， N、；唱 Graph Theory， An Algorithmic Ap−

 proach Academic Press 1975．

4）R田ens【ieh1， P．， and B， Leclerc，ド T祀es inいCombilla・

 toτic5． Graphs and メLlgebra  hlouton 乱nd Gauthier−Villars

 1976．