（概率论与数理统计专业论文）随机映射图的局部性质.pdf

论文独剖性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特别加以标注和致谢的地方外不包含其他入或其它机构已经发表或撰写 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 作者签名 瑙鲈嗍学m 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 、 作者签名 曼赫然复沾心川 导师签名：臣! ：f 哺码! 必 随机映射圈鑫冬局部性矮 摘要：给定顶点枭合m ：= l ，2 ，n 对于每个顶点i ，独立媲且随机 遮扶吲孛取窭令埂点歹，然后在这两令瑗患之瓣连接条塔i 为鲶点，以 j 为终点的有向边这样构成的图一般称为随机映射豳论文中研究当礼趋向 无穷大时随飘陕射瞬酶两者极限睦j 瞩及冀应用 首先，我们讨论固寇的m 个顶点在隧机映射图中的连接概率因此得割 连接概率酶耩薅解禚其二阶展汗院薅，m 个菝煮黧稽连接的穰率荧子髓鼙 调下降趋于攘爨，或者，纛不连接的概率关于n 单调增加趋予南 文串接蓉籀述陡辊映射瑟戆【醇嚣郝霆纛阏好匿。洚l 一越部露是一瞧 保留着顶点集合 k 在原来的映射图中的拓扑结构的最小的图。宥些映射图的 潲一局部图具有简单拓扑结构；它仍然是映射圈且含有2 忌个顶点，其中f k l 的 瑗点是它戆跨子，冀余豹是个疆焘燕入度为二懿悫熹我 l 把这麓巽露楚单缝 构的捌一局啬l ：图的映射网称为一好图容易发现当n 趋向无穷大时，随机 映射图赫瞄一好图的概率趋商予一进一步研究得到，随机映射蔺的简部圆极 限在莫种意义下等份于一个马尔科失链，准确地说是等份予图嬲随机生长过 程；图的随机生长过程中产生的图的连通分支的顶点个数的时闻序列是一个 溉1 2 ) 一孛虽餐厅逡翟，释产象酶蕊的树鹣顼京个数盼对瓣彦巅是( 1 2 ，u 2 ) 申国餐脬过程；局郄图极限性质能够反映随机映射臌的整体性质一一局部图 可以用米估计随机映射图的具有莫类性质的顶点的个数和莫些顶点的高度 瘦麾禺郝疆极限性壤麓够反浚壤辊浃射黧鲍整俸性鹱，我f 】客荔褥裂三静定 义在随机映射图的遍历过程，h a r r i s 游动，深度优先的遍历和在叶予上的遍 历，在缎迂标准化黯弱收敛予简一个反射带鹤桥 最后，我们介绍( n ，p ) 一中国餐厅过氍假设餐厅来了似个客人，他们坐 在前面静七个餐桌，盈第i 个餐桌霄m 个客入当下一个客人翻达餐厅时， 他将以b d ) + 鲫黝概搴坐在第i 个餐桌，以拶+ 七n ) ( 冠十8 ) 的概率挺 在第一张非空的餐桌，即第k 十1 个餐桌上这样的一个随机过程称为参数为 ( “，彩静孛嚣餐厅过程。我雷j 褥翻在不簿参数下警餐搿慧人数足够多孵，孛篷 1 餐厅过程粒餐桌的最大客人人数豹务酚激进矩。应雳戆薅结沦，遐的随机生长 过程中所产生的图的连通分支的顶点个数的时间序列就是一个( 0 ，1 2 ) 一中国 餐厅过栏和搿部爵极限健质麓够反映隧梳陕射匿的麓体稳震，童接褥爨警珏 趋向无穷大时随机映射照的最大连通分支的硬点个数的备酚渐进矩进耐从 各阶渐进矩，知道最大连通分支的顶点个数的渐进分布密度函数类似地，得 翻最大街静袋点伞数静备阶澎避戆l ；盂及渐连分带密发函数 荚键词：随机映射图，随机树，中湖餐厅过程，马尔科夫链，遍历过程 m r ( 2 0 0 0 ) 定趣努类0 5 c 8 0 ，6 0 j 1 0 中囝分类0 2 1 1 2 l o c a li m a g eo fr a n d o mm a p p i n gg r a p h s a b s t r a c t ：g i v e nv e r t i c e ss e t 两 l ，2 ，嚣，。f o re v e r yv e r t e x ，w ei n d e - p e n d e n t l ya n dr a n d o m l yc h o o s ea v e r t e xf r o m 捌，a n dj o i nt h e s et w ov e r t i c e s w i t ha no r i e n t a le d g ew h i c hh a si n i t i a lp o i n tia n de n dp o i n t s u c hg r a p h c o m p o s e do ft h e s ev e r t i c e sa n dt h e s ee d g e s 。 8g e n e r a l l yc a l l e dr a n d o mm a p - p i n gg r a p h i nt h ep a p e r ，w ei n v e s t i g a t et h el i m i tp r o p e r t yo ft h el o c a li m a g e o far a n d o mm a p p i n gg r a p ha n di t su s ea 8ng o e st oi n a u i t y f i r s tw es t u d yt h ej o i n e dp r o b a b i l i t yo fmf i x e dv e r t i c e si nar a n d o m g r a p h h e n c ew eg e ti t sp r e c i s ef o r m u l aa n di t ss e c o n do r d e re x p a n s i o n f o r e x a m p l ea s 犯g o e st oi n f i n i t y , t h ep r o b a b i l i t yt h a tmv e r t i c e sa r ej o i n e di s i n c r e a s i n gt o 器掰，w h i l et h et h ep r o b a b i l i t yt h a tm v e r t i c e sa r em u t u a l l y d i s j o i n e di sd e c r e a s i n gt o 面神1 t h ep a p e rn e x td e s c r i b e s ( k - l o c a li m a g eo far a n d o mm a p p i n gg r a p h a n df k - g o o dg r a p h t 疑幽一l o e 破i m a g eo fa m a p p i n gg r a p h i sam i n i m a l g r a p hw h i c hk e e p st h et o p o l o g i c a ls t r u c t u r eo f s o m em a p p i n gg r a p h s s 【k - l o c a li m a g e sh a v es i m p l et o p o l o g i c a ls t r u c t u r e ：i ti ss t i l lam a p p i n gg r a p h b u tw i t h2 4v e r t i c e sa n di th a s 溺a sl e a v e sa n dt h er e s t 是v e r t i c e sa 8i n n e r v e r t i c e sw h o s ei n d e g r e ei st w o w ec a l lt h e s ew h o s e ( k - l o c a li m a g e sh a v e s i m p l es t r u c t u r ef k - g o o dg r a p h s i ti se a s i l yt of i n dt h a ta s 嚣g o e si n 蠡鳐晚 t h ep r o b a b i l i t yt h a tar a n d o mm a p p i n gg r a p hi s 【k - g o o da s y m p t o t i ct oo n e + f u r t h e r m o r e ，t h el i m i t a t i o no fl o c a li m a g eo far a n d o mm a p p i n gg r a p hi se q u i v - a l e n tt oam a r k o vc h a i n 。r a n d o mb i r t hp r o c e s so fg r a p h sm o r ep r e c i s e l y 熟e t i m es e q u e n c eo ft h es i z e so fc o m p o n e n t s ( o rt r e e ) o ft h eg r 神h sc o n s t r u c t e db y r a n d o mb i r t hp r o c e s si s a ( o ，1 2 ) 一c h i n e s er e s t a u r a n tp r o c e e s ( o r ( 1 2 ，1 2 ) 一 c h i n e s er e s t a u r a n tp r o c e s s ) 。t h el i m i tp r o p e r t yo fi 毫8l o c a li m a g ec a l lr e f l e c t t h ew h o l ep r o p e r t yo far a n d o mm a p p i n gg r a p h t h i sm a k eu 8c a l le s t i m a t e t h en u m b e ro fv e r t i c e sw i t hac e r t a i no fp r o p e r t ya n dt h eh e i g h to fs o m ev e t - t i c e so far a n d o mm a p p i n gt h r o u g hi t sl o c a li m a g e b yt h ef a c tt h a tt h el i m i t p r o p e r t yo fi t sl o c a li m a g ec a n r e f l e c tt h ew h o l ep r o p e r t yo far a n d o mm a p p i n g 3 g r a p h 。w ee 蹴e a s i l yd r a wo u tt h ec o n c l u s i o nt h a tt h r e ek i n do ft r a v e l sw h i c h a r ed e f i n e do nar a n d o mm a p p i n gg r a p h ，h a r r i sw a l k ，t r a v e l so nt h ec o n t o u r a n dt r a v e l si nd e p t h - f i r s to r d e r ，w e e k l yc o n v e r g et ot h es a i n ep r o c e s sc a n e d r e f l e c t e db r o w nb r i d g e a tl a s tw ei n t r o d u c e ( 拶) 一c h i n e s er e s t m l r a n tp r o c e 酷。s u p p o s et h a t t h e r ea r enc u s t o m e r si nar e s t a u r a n ta n dt h e yo c c u p yt h ef i r s tkt a b l e sw i t h m c u s t o m e r ss i t t i n ga r o u n dt h e , i - t ht a b l e l e tt h en e x tc u s t o m e rb eb r o u g h t e i t h e rt ot h ei t ho c c u p i e dt a b l ew i t hp r o b a b i l i t y ( 魄一a ) ( n + 8 ) o rt ot h e f i r s te m p t yt a b l ew i t hp r o b a b i l i t y ( p + k a ) ( n 十p ) s u c ha r a n d o ms e q u e n c e i sc a l l e d 陋，8 ) 一c h i n e s er e s t a u r a n tp r o c e s s w eg e ta s y m p t o t i cm o m e n t so ft h e s i z eo ft h el a r g e s tt a b l ea 6 罪l a r g ee n o u g hf o re a c hp a i r 妇，鳓a p p l y i n gt h e a b o v er e s u l tt h a tt h et i m es e q u e n c eo ft h es i z e so fc o m p o n e n t so ft h eg r a p h s c o n s t r u c t e db yr a n d o mb i r t hp r o c e s si sa ( 0 ，1 2 ) 一c h i n e s er e s t a u r a n tp r o c e s s a n dt h er e s u l tt h a tt h el i m i tp r o p e r t yo fi t sl o c a li m a g ec a nr e f l e c tt h ew h o l e p r o p e r t yo far a n d o mm a p p i n gg r a p h ，w ed i r e c t l yg e tt h ea s y m p t o t i cm o m e n t s o ft h es i z eo ft h el a r g e s tc o m p o n e n to far a n d o mm a p p i n gg r a p ha s 嚣g o e st o i n f i n i t y f u r t h e r m o r e ，w eg e ti t sa s y m p t o t i cd i s t r i b u t i o nd i r e c t l yf r o mt h ea s - y m p t o t i cm o m e n t s ，s i m i l a r l y w ef i n dt h ea s y m p t o t i cm o m e n t so ft h es i z eo f t h el a r g e s tt r e ea n di t sa s y m p t o t i cd i s t r i b u t i o n ， l ( e yw o r d s ：r a n d o mm a p p i n gg r a p h s ，r a n d o mt r e e ，c h i n e s er e s t a u r a n tp r o c e s s ， m a r k o vc h a i n ，t r a v e r s a lp r o c e s s m r ( 2 0 0 0 ) s u b j e c tc l a s s i f i c a t i o n0 5 c 8 0 ，6 0 j 1 0 c h i n e s el i b r a r yc l a s s i f i c a t i o n0 2 1 1 4 圈l ：陕射匿 l弓f 言 随机映射图的基本概念一般说，图表示成g = ( y ( g ) ，e c a ) ) ，其中 v ( g ) 表示鹜g 懿】燹点菝点集会，e ( c ) 表拳毽g 约骞岗逡豹集会( 毫称 边的集合) 我们说图g 是映射图如果对于图g 的任何一个顶点i 满足，以 i 为始点的边有且仪有一条，鄄 l ：( t ，j ) e c g ) l i ，v i 矿( g ) 瑷在记同一 l ，2 ，摊 及e ：一 辑x ( 墓) ) ，= l ，露 ，其孛 x ( 蛰 独 兜且都在m 上均匀分布，即 1 p ”( x c i ) = j ) ) ：一三， j l ，2 ，m 换句话说，对任何顶点t ，从m 中独立地且随机地选取一点与其连接一条有 礴透这襻静瑟逶常称为覆点集舍菇融l 瓣隧橇映射錾。令它懿撵本空舞k 表示顶点集会为融】的映射图全体( 共有n “个样本) 和它的概率测度用p 。 袭示如图l 就是一张联点集合为【5 0 】的映射图事实上p 。是f k 上的古 典概率，鄂抛辕 p 。( u ) ) ：一去 5 谗号”：表示。定义必” 我们说图g 嫩一条长度为k 的路，如果图g 的顶点集合是 ：1s i k 十l 磷逸酶集合爨 ( 嚣l ，现) ，x k ，强+ 1 ) 如果，又有茹i = + 。，猁图g 是条闭合的路丽合静貉称为盈，匿g 是 楗，翔果墨g 含毒一个特殊骢瑷焱r ，且扶瓣g 的其它任意个顼点私出 发都存在唯一的路到达顶点r 顶点r 称为图g 的根从顶点t 刘根r 的 路的长度记麓顶点u 的高度绞联点嚣为怒点酶逸静令数记必顶轰锰静毽 壤，棚反，以顶点毯为终点的边的个数记为瑗点u 的人度映射阕的任何 一个顶点的出度为对于映射图，我们把入度为释的顶点称为叶子我们 谶两个不蔺鼢顼煮与j 相纛，燕聚存在l l ，奴v ( c ) 使缮 i ，i t ) ，( i l ，i 2 ) ，( 珏，歹) ( 茹，y ) ：( 茹，y e ( g ) o r 治，善) 毫e g ) 。 我f f 】说瑟g 连逶，船袋其串任何两个璜点裰连一个连逶分支是指最大连 遥子墅。 考虑任何一幅映射随f 的结构因为映射图，的每个顶点唯一地连磁一 条透，疹i 有我嚣j 盘把，着或楚丞数： f ( i ) 一j ，麴栗i ，j ) 联，) ， 鬣然，每一樯浃射鹜曦一魂辩应一个函数，一个这样静滋数毽唯一缝对瘦一 蠛图。因此我们一般不严格酝分，是映射图或者愚函数顺便说一下，为了 节约符号的长度，在集合运算过程中我们往穗把，的顶点集龠v ( f ) 写成， 一一这样并苓会零l 起混淆酶，露黎簧强溺是溪点集会对锈震矿) 。容易知 道，映射图，的健何一个连通分支仍然是映射图，而且罐个遗通分支有髓仅 有一个圈。以后我们总约定，所有提蓟的映射图的顶点标号都是自然数令 旗，焉，表示陕瓣星，黪黪有不懑鲍述逶分支，虽按它嬲的瑗点的最小掭号 从小到大排序，即m i n 蜀 m i n 镌 我们说映射瞬，盼第i 个连通分 支是麓如果i 不趱遵映射圈，酶连逶分支静个数，否弼说映射鋈，酶第i 个 连逶分支是童銎。如果我 f j 摁映射图，的所有圈上的边去掉，那么保留下来 的图燕一片森林，即像的每个连通分支都是树直接着出，这样所得剃的 6 撵戆总数穰映射强，匿上载顶轰鲍总数一襻类似域，令鳗，编，表示映 射图，去掉所有圈上的边后保留下来的翻的所有不同连通分支，且按它们的 顶点的簸，j 、标号驮小到大排序，邵m i n 锈 m i n 锈 我f j 说浚瓣瑟， 的笫i 橡挝是鳗如果i 不超过映射蹑，的圈上的顶点个数，否则说映射凰， 的第i 个连通分支是空圈因此可以说，映射图，每一个连通分支怒由一个 蕊褥冗颡祷稀成的，褥量酃冗裸褥静根蓬在那个嚣上。 随机映射图的背景在随机图选讲( i ) 书中，中国科学院院士骂 惠锈巍，4 隧梳瑟譬隧钒复杂瓣珞理论是个酝具有理论掭度，又是蠢实繇应 用背景的交叉学科领域，近年来受到了人们日益增长的重视为此，中国科学 院数学与系统科学研究陡从事随槐分析与菌论的同事髓，蠢2 0 0 3 年戳来联合 举办了* 蘧枫匿与隧投复杂赠终一研究生讨论班其实，皇1 9 9 8 零以 w a t t s 和b a r a b a s i ”等为代表的科学家先后发现网络的小世界( s m a l lw o r d ) 效应与光标畿( s c a u - f r e e ) 祷浚浚来，对予隧梳复杂黼络鹃研究瑟形成莺霞上 的鼹究热点，来囊统计物理，随机分橱，统计，凰论，计算机网络，系缀科 学，生命科学等不同领域的科学家征在从不同的角度积极探索与研究随机复 杂阕络翡特饿，形成梳理及箕应惩。透魏，缒掇复杂援终爨最缓得重点分绥鲍 研究方向。”正是程随机阉已成当今国内外研究热点的背景下，我们着手予随 机映射图的研究 事实主，隧瓤淡射錾懿搿究已萋烫有缀久戆掰史，嚣丰鬻的戏皋。早在1 9 5 4 年k r u s k a l 发表了。t h ee x p e c t e dn u m b e ro fc o m p o n e n t su n d e rar a n d o m m a p p i n gf u n c t i o n 一德得到随机映射图的连遴分鬣个数g 辩数学期鋈； ， 一 e 。( v i ) = 言l o g ( 2 n ) + 吾+ o ( 1 ) 二 其中，c = 0 5 7 7 2 欧拉常数g e r t s b a k h 在l 7 7 冬发表7 “e p i d e m i c p r o c e s s e so nar a n d o mg r a p h ：s o m ep r e l i m i n a r yr e s u l t s ”，提出传染病扩 散模型；给窳一随机映射图，其上每个顶点对应一个人，其上每条边对应两 个久之瓣有联系；警葵孛懿舔分溪点受嚣感染时，熬栗传染瘸沿着逡夔 最方向，边的反方向，或者边的正反两方向的三种传播方式最终会使多少个 顶点受到感染主要结论由p i t t e l 在1 9 8 3 竿的一篇论文提供值襻一糖酶 熬k o l c h i n 瓣著终。r a n d o mm a p p i n g s ”有簧丰富戆隧枧映射霆的结果= | ； 申有随机映射图连通分支个数q 渐进服从正态分带，且当n = n ( n ) 满足 7 ( n 一( 1 2 ) l n 犯) ( k 社) 。1 2 在蠢限区阉走，一致骞 蹦q 钢= 志嘲 一生管型) ( 1 + 雌) ) - 第r 大连通分支的顶点个数二g ，凝大事孽酶顶点令数三嚣，释遮撬陡莉蚕戆 离度量等继果，燕要或用了母丞数的技巧求出相应随机变量的的分布； 豫( 等寸“丢r - 1 。互。譬 批对再嘉 p 。( 等才一砉警厶；砖监篙挚 号n ( 隽s ：) 一。塾珍e 罐鳓 其中蛾( 2 ) 一 戤z ，i 一1 ，s ，茹1 4 - + 岛 l 书中还介绍了随祝跌射 爨裙疆枧整换星，隧枧映射露程g a l t o n - w a t 甚o n 树之阕的关系。a l d o u s 戎随 机映射图卓有成果他张1 9 9 4 年发表了。b r o w n i a nb r i d g ea s y m p t o t i c sf o r r a n d o mm a p p i n g s8 任给张隧梳陡辩匿，按h a r r i s 游动方式速掰所鸯获 点，并撼遍历的每个顶点的摆应的时间和高度记录成直角搬标系的一个点最 腐把这螳不同点连成一条折线这样使得一幅随机映射图对应一条折线另一 方萄，肖裙瑟折线瓣两懈映鸯孛鏊霹梅a l d o u s 蒌骥了这榉形成酶拆线在灏进 媳服从反射撩朗桥。这个结果几乎反映了i 随机映射图所有的宏观性质利用这 个结果，a l d o u s 等在2 0 0 2 发寝“t h ea s y m p t o t i cd i s t r i b u t i o no ft h ed i a m e t e r o far a n d o mm a p p i n g ”，研究t 隧撬映射圈豹纛径长度。一m a x a i 是 ， 其中 写( 0 ：= m i n 0 芝1 ：9 0 惫 矗u ( 0 = 。8 ( 1 ) ， 交量。是社伞顼点静醣橇陕瓣蚕该论文褥蘩； 恶琢( ( 鲁) ) = 衍簿丽z 。”e 喝。瓣，如 其中， 酬一厂u _ l e “如，荆= f n 气弋t 吲孑备眦 如果用王。( r ) 表示隧枧映射慰灼裹嶷为r 的褒点个数，那么利翅隧规映射爨 渐进服从反射布朗桥的事实，容易想到( f n ( ) ，t20 ) 是反射布朗桥的局部时 过程，英孛 a ( t ) 一靠一1 2 ( 銎弼+ l t 问k ( p 而j ) + 0 聂一扛阔) 磊( 鎏娴+ 1 ) 确实魏戴，m i c h a e ld r m o t aa n db e r n h a r d 在1 9 9 9 发表- f “s t r a t ao fr a n d o m m a p p i n g s - ac o m b i n a t o r i a la p p r o a c h 。得到k ( 幻在c o ，o o ) 弱收敛予局部时 的结果： 国一言 导 ， 二 其孛，b ( t ) 是反射枣翅耩，憨硌) 是它豹愿郝时，鄹 1，l 。渤2 溉；五1 m 司( 嚣办 p i t m a n 的著作4c o m b i t o r i a ls t o c h a s t i cp r o c e 龉e s “，l l 雯漾了多篇关于隧橇 映射图的文章。其外还碟很多遽机蹋论的著作； r u b i na n ds i t g r e a v e s 4 0 1 ， k a t z 2 6 1 ，f o l k e r t 2 1 】，h a r r i s 2 5 】，r i o r d a n 3 7 ，s t e p a n o v 4 3 1 4 4 4 5 】， p r o s k u r i n 3 4 】，s a c h k o v 4 1 】，b a g - - , 4 s ，r o 潞 3 9 ，m u t a f c h i e v 3 0 l ， d r m o t a 1 4 ，d u q u e s n e 1 6 】，a l d o u sa n dm i e r m o n ta n dp i t m a n 5 】。 随机映射图和随机鬣换匿，随机映射豳和随机树有密协关系它们的许多 终皋可以互攘壹接应震。等可艉她扶对熬群& 鲍爨考珏! 个元索孛致遗一个 元索，即7 1 , 个元素的随机置换图等可能地从所有含有礼个顶点的树申取出一 裸帮嘻( 共有矿。种可能) ，即n 个礤点的随机褥在酝知随机映射圈的匿上酶 顶点教条律下，这些疆上的褒点所织成的子图等馀予越枧熬换霉在跫知琏规 映射图奠一棵树上的所有顶点，那么这戡顶点所构成的树就是棵随机树 j o y a l 双射歪楚反努尚说疆，一裸隧氍树襁一个支襻在融 豹垮磐分书翡陡祝 变量，撼如何同一蠛随机映射蹰一一对应f 5 1 有关随机置换图期l 瞳机树的严 格定义和结论可参既k o l c h i n 2 7 ，b o l l o b a s 1 0 j 。p i t m a n 3 2 j 和f e l l e r 2 0 】等 著作。在莲撬陕射毽静基磁上发羡戆有隧椒多跌射嚣秘隧撬p 一沃射戮。跌阏 中每个顶点出发独叛地麒随机地连接的m 个顶点，所构成的图即随机多 映射图箕严格定义和褶关结采参觅f o l k e r t 2 1 j 如果 ，j = l ，似) 独立冠分泰： p p ( k ( ，) = t ) = p i ，i = 1 ，竹 9 焚孛热之o ，l = 1 ，椎，p l 十+ 一l ，薅么我寒】黎( 圈， 纹玛( i ) ) ，= 1 ，n ) 为随机p 一映射图妇= ( m ，孙) ) 随机p 一映射图参见a l d o u s a n dm i e r m o n ta n dp i t m a n 【5 j 随机映射瀚和随梳复杂两络的形成机翩有着稆 缓戆镶好连接，这决定了隧枫映射掇具蠢弱隧规复杂嬲终一襻具有懿无掾度 特性随机映射图的形成机制参见举论文关予随机映射图的局部图的构造方 式和西的随税生长过程无标度特性指，阿皤的莫魏数蠹待征寝瑗籀幂率分 磁， p ( k ) 一c k 一7 便是随机映射圈的树的联点个数表现出幂率分带：按每棵树的最小元索排莉， 笨熹：棵褪酶瑗轰个数隰| 有 ，溉繇( 譬) 溉一， 随机复杂网络的主要著作b a r a b a s ia n da l b e r t 科，w a t t sa n ds t r o g a t z 4 7 1 这些疆规映射懿不强联系，罴研究蘧规欧射嚣黪重要嵌撵，势为醣炎提供了 工具 蘧执映射翅的磷究方法。馈计满足一定性震的图约个数通常毒两种途经。 一种途径是求出精确表遮式，可以利用p o l y a 数定理，特征函数，微分算予和 缀合数学的群有理论鸯辩避一步考虑稽碡谨又复杂懿表达式翡渐进行为这 种方法的应用一般是一个繁琐的工作这种方法的特征戎于完垒确定性的 参见t e m p e r l e y 【4 6 1 ，d i _ e s t e 1 2 豳的数数的理论有漂赢的和丰富的成果， 趸襁遽在鳃合数学锈竣里发嶷，懿是宅穰夔撬垂理论骞较步豹联系男一释 途径是豳e r d o sa n dr e n y i 引进的，参见e r d o sa n dr e n y i 1 7 】【1 8 】【1 9 】它和 数数理论少有联系，不燕热衷于精确表达式，衙是尽可髓地和用概率分布和 剩薅概率思想去逼近精确鳃泛如e r d o sa n dr e n y i 指出，这狰概率方法遥常 比确定性方法应用在随机图上更有效 本论文的结论以及方法。第二黪我们首先计算l 滚机映射图的给寇顶点嶷 的任意分类的连接概率及其：阶展汗设a 。， 2 ，a 。是互不相交的自然 数戆有隈菲空子集，记u = l 聪l 磊。我髑慧是谖秸足够太彼褥u c 阐震符 号以，国如国o 以。表示下列察件；对任何不同顶点l ，j u ，与j 相 1 0 运誊显仅差褥在1 ksm 绠碍l ，j a k 运9 拳仔簿獠翠张隽a 1 ，一，颤 的连接概率利用p 。关于顶点对称性和引理2 2 ( 参见a o 龉 a g ，1 2 9 1 3 7 ) p 。塑是连逶戆) ：迎云坐萎署， 蒋易得到定联2 i ( i ) p 。 厶。穆五。静$ 厶。 的寝达式s 一 咤掣羡量。雨( n - - k - - m ) 1 - k - n 黔, n 嵩半 妒 惫袋。如一是一班) !怂1 肚盎 j f ! 逃步剿熙s t i r l i a g 公式一一i ) r l 磊积r a m 矗蕴u j a n 序列净圜 ；矿；t + 蠢+ 芸+ 鑫+ 署 其中雨1 鞭 靠 去，佛关乎r 单调递减且满足美系式；+ 蔼责：而， 纛丢s 肆rs 纛，擞楚碍到定联2 。l ( 2 ) p 。 以；毋以：彩e j a 的= 盼展舞； 鬻2 m 器2 a1 + 掣2 m 搿2 a2 ”霎2 a 铲i ，鱼6 n 叫。州n 叫。， ( + 一) ”f+ 一) ! ! 、厶f1 ” ” 。v 。” 由此容易得出，对于任意固定m 个不同的顶点，巍顶点个数r 趋向无穷大 辩，这m 个壤点羹裙连接的概率鼙清增鸯e 惹离予蔼= 1 丽；然掰，这m 伞褒 成互不连接的概率单调减少趋向于簦羔裂。并且给出连接概率的部分数值模 拟( 表1 ) 我们通用新的方法重新证明随机映射图的连通分支个数e ，渐 避缝骧扶烤魏秀；l o g n 裙方麓为1 1l o g n 戆歪冬分零。劳强进一步说疆了g 的均值朔方蓑同喜观相符即分别的阶展开是 1l o g n 和i 1l o g n 这一章威用 礴定住的方法，从丽许算量较大 第惩章我 f 】研宠了隧祝映射图媳局郝塑性爱，黄先我嚣】把游足以下条烨 的图称为【七| 好图t ( 1 ) 任侮闻酶篌煮不在蘸上； ( 2 ) 任何矧的蹰个顶点都不存在一条路； ( 3 ) 如果【q 的两个顶点在同一棵树，那么信们的交点不能在豳上； ( 4 ) 麓暴阔豹三令壤纛农游一操耱，群么宅锯苓爨有椐露豹交点。 如果顶点u 和顶点u 磁同一棵树，那么存在非负熬数七和z 满足( u ) 一 1 1 ( 鬈) 令k 穰 歪楚瀵怒( 珏) = ( 管) 豹最小菲受整数，我爨耀褒点( 程) 是顶点“和顶点”的交点定理3 1 说对于任意固定k ，当n 趋向予无穷穴 时，几乎所有的图麓嘲一好嚣所以我们只需簧考虑【辟好图就足够了现 在定义阁一局部强绦p ) t 局郄匿联妇) 鳃菝点集会是嘲以及圈豹交患秘 所在的树的根的并集，且如果( u ， ) 是敬) 的边，那么t ，；( ) ，其中 d m i n 七：( n ) 矿( 磁p ) ) 闷一好函静潲一局部黼比较简单，它仍 然是映射图旦富有2 盎个埂点，其中吲的顶点是它的时予，其余的k 个璜患 是入度为二的内点因此它的每一连通分支有唯一的一个豳和几棵：叉树， 二叉树酶根在甏主魏暴一裸树静静伞菝赢懿入度哭有两种情援，要么是零 要么是二，那么我们称这棵树为二义树如果把所有吲一好图的一局部 图的内点标号去掉，那将共得静( 2 k 一1 ) ! ! 个不同的瞬定理3 1 还说当竹宛 努太露遨些( 2 老一1 ) ! 不麓戆爨足孚等概率发生圭 囊 ：我缎搀造缀戆隧橇生长 过程：初始图f 1 = ( 【2 】， ( 1 ，1 ) ，( 2 ，1 ) ) 即一个最短的圈和条最短的路构成 的黼；假设图按时间顺序分剐长成矗，矗，那么第k 十l 时刻，圈以概率 蠡扶瑟& 长出一个最短豹甏寝一条最缎懿黪摊成鹣连邋分支，器 靠+ l 一 2 k + 2 】，e ( & ) u ( 2 是+ i ，2 是+ 1 ) ，2 k + 2 ，2 k 十1 ) ) 或者以橛攀磊2 k 爵，等概窭地从塑磊豹边( i ，j ) 长出一条边，鄹 & 十l = ( 贮老+ 2 】，( 露( ) ( i ，) ) u ( i ，2 k + 1 ) ，( 2 1 ：+ l ，j ) ，( 2 k + 2 ，2 k + 1 ) ) ) 这样生成的型靠等价于一局部图( 当性趋向无穷大) ( 引理3 4 ) 这为硪 究髑部圈的性质提供了方便怒理3 , 3 说，随机过程( ( 峨) 1 1 2 ，t 1 ) ，k 1 ) 是( 0 ，l 2 ) 一审溪餐搿过稷耱( ( | 缓躲) i 2 ，t i ) ，k 1 ) 是( 1 2 ，1 2 ) - 中餮餐 厅过程这正憋第四章讨论中尉餐厅过程的原因我们知道抽样调查过程中， 当样本容量达猁一定程度时，样本的分布熊够反映母体分布由这个概率思糠 出发我嬲注意到，潮一慰郏塑憩够缀好蟪夏浃攘应鲍圈一好强：娅当拜是 且k 充分大时，推论3 4 说一局部图的每个遴通分支顶点个数和总顶点数 2 未院值，大约等于舞阍一好匿盼裙藏的逢通分支顶点个数和总顶点数盼n 的 比艇；同撵推论3 3 说嗍一局郄凰的每撵挝顶点个数和总鞭点数2 七比值， 大约等予为一好阔的棚应的树顶点个数和总顶点数的”的比值；推论3 5 说若霞定謇然数r ，弼翻中的溪点在陶一局部蘑静嵩度缀过缭夺磊倍磁 的数值，大约等于棚应顶点在糊一好图的高度经过缩小v 慌倍聪的数值遮 1 2 骜难论蠢稷多鏖霉，疆多古典黪趣题霹以较套荔逡扶这些关系窭瑟瑟缮裂毖 如考虑定义在随机映射朦的三种不同的遍历h a r r i s 游动，在叶子上的遍历和 深度优先遍历为了定义映射瞬上的游动，我们需要把映射图嵌入平衡但是 一螟錾毒妻 几转嵌入方式，爨以霉簧嚣努。定义( d 。，p 。) 建隧规专廖映射塑 的概率窘间一幅随机有序映射图冒n 。按如下方式得到；等概率地从f k 中选出一循浚射图，然后绘映射瞪u 盼每个顶点的孩予垮匀缝稚序我仍 张皈扣) ：= z 叫：u ( ：) = 墨z ： 中约域点是顶点z 在映射嬲埘孛鲍 孩子现在给定映射图u 以及u 的有序化后的一幅有序映射图苗定 义有彦陡射蚕召童酶嚣a x r i s 游动约( o ) ：0 l 2 n ) t 向； 猷豫叫国默纂蕊暑三曼 其孛记号珏表示瑗熹瓢辑在戆秘鳇攘，记号电( 鬈一嚣) 袭零u 农映射鎏 w 上的高度辅助过程( w 孑( o ) ：0 is2 n ) 定义为； 慨( o ) 一，n 0 ( 1 ) 一u ( ( 1 ) ) 对于1 i 2 n 假设