第12ç« æœ‰å‘图就是边是顶点的有åºå¯¹çš„图,也就是说æ¯ä¸ªè¾¹éƒ½æœ‰èµ·å§‹é¡¶ç‚¹å’Œç»ˆæ¢é¡¶ç‚¹ã€‚ä»»æ„两顶点间有且仅有一æ¡è¾¹çš„æœ‰å‘图å«ç«žèµ›å›¾ã€‚若任两顶点间都å¯ä»¥æ²¿æœ‰å‘路径互达,图就是强连通的。 æ— å‘图的强连通定å‘å°±æ˜¯æŠŠæ¯æ¡è¾¹æŒ‡å®šä¸€ä¸ªæ–¹å‘,然åŽä¿è¯å¾—到的有å‘图是强连通的。强连通定å‘å˜åœ¨å½“ä¸”ä»…å½“åŽŸå›¾ä¸æ²¡æœ‰æ¡¥ã€‚æž„é€ å‡ºè¿™ä¸€å¼ºè¿žé€šå®šå‘事实上很简å•:按照一éDFS的访问方å‘给边定å‘å°±å¯ä»¥äº†ï¼ˆä¹¦ä¸çš„算法一如既往地麻烦)。 æ ¸å¿ƒåˆ†é…é—®é¢˜æ˜¯è¿™æ ·çš„ï¼šn个商人,æ¯äººæœ‰1个商å“,æ¯äººå¯¹æ‰€æœ‰nä¸ªå•†å“æŒ‰ç…§è‡ªå·±çš„喜好进行排åºã€‚求一个把n个商å“分é…ç»™n个人的方案,使ä¸å˜åœ¨å‡ 个商人的集åˆï¼Œä»–们把分到的商å“冿¬¡è¿›è¡Œäº¤æ¢åŽå¯ä»¥ä½¿æ¯ä¸ªäººéƒ½æ›´æ»¡æ„。算法是:æ¯ä¸ªå•†äººå¯¹è‡ªå·±æœ€å–œæ¬¢çš„商å“的主人连一个有å‘边,找一个圈(由于æ¯ä¸ªç‚¹éƒ½æœ‰å‡ºè¾¹ï¼Œæ‰€ä»¥è¿™è‚¯å®šæ˜¯èƒ½æ‰¾åˆ°çš„),按照这个圈进行分é…,把已分é…çš„é¡¶ç‚¹åˆ æŽ‰ï¼Œæ‰€æœ‰æŒ‡å‘è¿™äº›é¡¶ç‚¹çš„è¾¹é‡æ–°è®¡ç®—。 网络就是å˜åœ¨æºç‚¹s和汇点t的有å‘å›¾ï¼Œå…¶ä¸æ¯æ¡è¾¹éƒ½æœ‰ä¸€ä¸ªå¯ä»¥è®¤ä¸ºæ˜¯â€œå®¹é‡â€çš„æƒå€¼ã€‚ç½‘ç»œä¸çš„æµå®šä¹‰ä¸ºåŠ åœ¨æ¯æ¡è¾¹ä¸Šçš„ä¸€ä¸ªå‡½æ•°ï¼Œä¹Ÿå°±æ˜¯è¯´ç»™æ¯æ¡è¾¹æŒ‡å®šä¸€ä¸ªâ€œæµé‡â€ã€‚åˆæ³•çš„æµåº”è¯¥æ»¡è¶³ï¼šæ¯æ¡è¾¹çš„æµé‡ä¸è¶…过其容é‡ï¼Œé™¤æºç‚¹å’Œæ±‡ç‚¹å¤–,点的出边的容é‡å’Œä¸Žå…¶å…¥è¾¹çš„æµé‡å’Œç›¸ç‰ã€‚æµçš„净æµé‡å°±æ˜¯æºçš„出边的æµé‡å’Œæˆ–汇的入边的æµé‡å’Œã€‚æ±‚ä¸€ä¸ªåˆæ³•的净æµé‡æœ€å¤§çš„æµå°±æ˜¯æœ€å¤§æµé—®é¢˜ã€‚ 网络的割是一组边的集åˆï¼Œæ»¡è¶³æŠŠè¿™äº›è¾¹ä»ŽåŽŸå›¾ä¸åˆ 去åŽä»Žæºç‚¹åˆ°æ±‡ç‚¹ä¸å†è¿žé€šã€‚最å°å‰²å°±æ˜¯è¾¹çš„æƒå€¼ï¼ˆå°±æ˜¯ä¸Šè¿°â€œå®¹é‡â€ï¼‰å’Œæœ€å°çš„å‰²ã€‚æœ€å¤§æµæœ€å°å‰²å®šç†çš„内容就是:网络ä¸çš„æœ€å¤§æµçš„值ç‰äºŽæœ€å°å‰²çš„值。 求解最大æµé—®é¢˜å’Œæœ€å°å‰²é—®é¢˜å¯ä»¥é‡‡ç”¨æ®‹é‡ç½‘络增广路的方法。这在很多很多资料ä¸éƒ½æœ‰å¾ˆå¥½çš„介ç»ã€‚ã€Šç»„åˆæ•°å¦ã€‹è¿™ä¹¦ä¼¼ä¹Žå¹¶ä¸æ˜¯å¦ç½‘络æµçš„好教æã€‚ 第13ç« Ï‡(G)是图G的色数,就是说给图的æ¯ä¸ªé¡¶ç‚¹èµ‹ä¸€ä¸ªé¢œè‰²ä½¿æ‰€æœ‰è¾¹çš„两个端点的颜色ä¸åŒï¼Œéœ€è¦çš„æœ€å°‘颜色数目。它也å¯ä»¥ç†è§£æˆå°†é¡¶ç‚¹åˆ’分æˆè‹¥å¹²ä¸ªé›†åˆï¼Œä½¿æ¯ä¸ªé›†åˆçš„导出åå›¾éƒ½æ˜¯é›¶å›¾çš„æœ€å°‘é›†åˆæ•°ç›®ã€‚求图的色数很困难。 关于图G的色多项å¼pG(k),也就是说将图G用kç§é¢œè‰²çš„æ–¹æ³•数。有一个结论:设T是一棵né˜¶æ ‘ï¼Œåˆ™pT(k)=k(k-1)^(n-1)ã€‚å®ƒçš„è¯æ˜Žä¹Ÿç®€å•:第一个顶点有kç§ç€è‰²æ–¹å¼ï¼Œä»¥åŽæ¯æ·»åŠ ä¸€ä¸ªä¸Žå½“å‰é¡¶ç‚¹ç›¸é‚»çš„顶点都k-1ç§ç€è‰²æ–¹å¼ï¼ˆå› ä¸ºå®ƒä»…ä¸Žä¸€ä¸ªé¡¶ç‚¹ç›¸é‚»ï¼‰ï¼Œæ ¹æ®ä¹˜æ³•原ç†å¾—è¯ã€‚å¦å¤–,nä¸ªé¡¶ç‚¹çš„é›¶å›¾çš„è‰²å¤šé¡¹å¼æ˜¯k^n。求色多项å¼çš„ä¸€ç§æ–¹æ³•是:当Gä¸ä¸ºé›¶å›¾æ—¶ï¼Œè®¾xã€y是一对邻接顶点,设G1为原图去掉边xã€y的图,G2为原图将xã€yåˆå¹¶æˆä¸€ä¸ªé¡¶ç‚¹çš„图(原æ¥ä¸Žx或y相邻的顶点å‡ä¸Žæ–°é¡¶ç‚¹ç›¸é‚»ï¼‰ï¼Œé‚£ä¹ˆå°±æœ‰pG(k) = pG1(k) – pG2(k),递归求解å³å¯ã€‚这个算法的æ£ç¡®æ€§è¿˜æ¯”较好ç†è§£çš„,ä¸è¿‡æ˜¾ç„¶å®ƒæ˜¯æŒ‡æ•°çº§çš„算法。它å¯ä»¥é‡‡ç”¨éžé€’归的方法实现,就是维护一个图的集åˆï¼Œæ¯æ¬¡å–出一个éžé›¶å›¾çš„å…ƒç´ æŠŠå®ƒåˆ†æˆä¸¤ä¸ªå…ƒç´ 。 å¹³é¢å›¾å°±æ˜¯å¯ä»¥â€œç”»â€åœ¨å¹³é¢ä¸Šè€Œä¸”è¾¹ä¸äº¤å‰çš„图。(更“数å¦â€çš„定义似乎书上没有。)它有一些很好的性质:设一个连通的平é¢å›¾çš„å¹³é¢è¡¨ç¤ºæœ‰n个顶点点ã€eæ¡è¾¹æ›²çº¿ã€r个所围区域,则:n+r-e=2ã€‚è¯æ˜Žçš„æ–¹æ³•æ˜¯å…ˆå¯¹æ ‘è¯æ˜Žï¼Œå†å¾€æ ‘ä¸ŠåŠ è¾¹ï¼Œä¿æŒç‰å¼å§‹ç»ˆæˆç«‹ã€‚一个平é¢å›¾å¿…å˜åœ¨ä¸€ä¸ªé¡¶ç‚¹ï¼Œå®ƒçš„度至多是5,这是欧拉公å¼çš„æŽ¨è®ºã€‚ äº”è‰²å®šç†æ˜¯ï¼šä¸€ä¸ªå¹³é¢å›¾çš„色数至多是5。这个å¯ä»¥æ¯”较简å•åœ°è¯æ˜Žï¼Œä¸»è¦æ ¹æ®ä¸Šé¢çš„æ¬§æ‹‰å…¬å¼çš„æŽ¨è®ºæ¥åˆ©ç”¨é‚£ä¸ªç‰¹æ®Šçš„顶点åšçªç ´å£ã€‚å®ƒçš„åŠ å¼ºç‰ˆæœ¬å››è‰²å®šç†ä¹Ÿæ˜¯æˆç«‹çš„。 图的独立集的定义是一个顶点的集åˆï¼Œå®ƒçš„导出å图是零图。图的独立数α(G)å°±æ˜¯å›¾ä¸æœ€å¤§çš„独立集的大å°ã€‚求图的独立数很难。图的控制集是一个顶点的集åˆï¼Œå®ƒæ»¡è¶³æ‰€æœ‰ä¸åœ¨é›†åˆä¸çš„顶点都与集åˆä¸çš„点有边。最å°çš„æŽ§åˆ¶é›†çš„大å°ç§°ä¸ºå›¾çš„独立数dom(G)。图的团就是一个顶点的集åˆï¼Œå®ƒçš„导出å图是完全图。图ä¸çš„一个团是图的补图的独立集,å之亦然。图的团数ω (G)是最大的团的大å°ã€‚å°†å›¾çš„ç‚¹é›†åˆ’åˆ†æˆæœ€å°‘的团的数目称为团划分数θ(G)。完美图满足它的任何一个导出å图有χ(G)=ω (G)且α(G)=θ(G)。 图的弦就是连接圈的两个顶点且ä¸å±žäºŽè¯¥åœˆçš„一æ¡è¾¹ã€‚如果æ¯ä¸€ä¸ªé•¿åº¦å¤§äºŽ3的圈都有弦,图就被称为弦图。所有的弦图都是完美的。所有的区间图(定义ä¸è¯´äº†ï¼‰éƒ½æ˜¯å¼¦å›¾ã€‚ 以上定ç†çš„è¯æ˜Žå‡ç•¥ï¼Œå› 为第一我也æžä¸å¤ªæ‡‚,第二它们在OIä¸ä¼¼ä¹Žæ²¡ä»€ä¹ˆç”¨ã€‚ 图的顶点连通度κ(G)æ˜¯æœ€å°‘åˆ åŽ»å¤šå°‘ä¸ªé¡¶ç‚¹å¯ä»¥ä½¿å›¾ä¸å†è¿žé€šï¼Œå®šä¹‰Îº(K_n)=n-1。边连通度λ(G)æ˜¯æœ€å°‘åˆ åŽ»å¤šå°‘æ¡è¾¹å¯ä»¥ä½¿å›¾ä¸å†è¿žé€šã€‚å†è®¾Î´(G)表示图ä¸é¡¶ç‚¹çš„æœ€å¤§åº¦ï¼Œåˆ™æœ‰æ˜¾ç„¶çš„ä¸ç‰å¼Îº(G)≤λ(G)≤δ(G)。 顶点连通度κ(G)ä¸å°äºŽk的图称为k-连通图,一个图是2-连通图与以下结论ç‰ä»·ï¼šæ²¡æœ‰å…³èŠ‚ç‚¹ï¼›ä»»ä¸¤ä¸ªé¡¶ç‚¹aã€b都å˜åœ¨ä¸€ä¸ªåŒ…å«aã€b的圈;æ¯ä¸‰ä¸ªé¡¶ç‚¹aã€bã€c,都å˜åœ¨ä¸€æ¡è¿žé€šaã€b且ä¸ç»è¿‡cçš„è·¯å¾„ã€‚è¿™äº›éƒ½å¾ˆå¥½è¯æ˜Žã€‚ 关于图的点连通度的Menger定ç†çš„å†…å®¹æ˜¯è¿™æ ·çš„ï¼šè®¾kæ˜¯ä¸€ä¸ªæ£æ•´æ•°ï¼ŒG是一个阶为n≥k+1的图,则G是k-连通的当且仅当对任æ„两个ä¸åŒçš„顶点aå’Œb都å˜åœ¨è¿žæŽ¥aã€bçš„kæ¡è·¯å¾„使得æ¯å¯¹è·¯å¾„åªæœ‰aå’Œb两个公共点。
About Me
-
Recent Posts
Categories
Tag Cloud
ACM-ICPC Avril blog Code Complete Emacs GCC GDB Linkin Park LLVM matrix67 NOI NOIP OI OIBHæ¯ OIBH队 Paul Potts PKU python Scheme SICP USACO wiki ZJU ä¹ é¢˜ ä¹¦ç± ä»£ç 伊朗åŒå¦ åˆç§Ÿ 北京 动æ€è§„划的æ€è€ƒè‰ºæœ¯ æ ¡èµ› æ•°å¦ æ•°è®º 笔记 算法 ç»„åˆæ•°å¦ 翻墙 çœé˜Ÿé›†è® çœé€‰ 百度之星 计划 诗 软件工程 éŸ³ä¹ éƒ‘å·žArchives