• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            xiaoguozi's Blog
            Pay it forword - 我并不覺的自豪,我所嘗試的事情都失敗了······習慣原本生活的人不容易改變,就算現狀很糟,他們也很難改變,在過程中,他們還是放棄了······他們一放棄,大家就都是輸家······讓愛傳出去,很困難,也無法預料,人們需要更細心的觀察別人,要隨時注意才能保護別人,因為他們未必知道自己要什么·····
            給定一個非負整數序列,若存在一個無向圖使得圖中各點的度與此序列一一對應,則稱此序列可圖化。進一步,若圖為簡單圖,則稱此序列可簡單圖化。

            可圖化的判定比較簡單:

            關于具體圖的構造,我們可以簡單地把奇數度的點配對,剩下的全部搞成自環。

            可簡單圖化的判定,有一個Havel定理,是說: 我們把序列排成不增序,即

            則d可簡單圖化當且僅當

            可簡單圖化。這個定理寫起來麻煩,實際上就是說,我們把d排序以后,找出度最大的點(設度為d1),把它和度次大的d1個點之間連邊,然后這個點就可以不管了,一直繼續這個過程,直到建出完整的圖,或出現負度等明顯不合理的情況。

            定理的簡單證明如下:

            (
            <=)若d'可簡單圖化,我們只需把原圖中的最大度點和d'中度最大的d1個點連邊即可,易得此圖必為簡單圖。 (=>)若d可簡單圖化,設得到的簡單圖為G。分兩種情況考慮:

            (a)若G中存在邊,則把這些邊除去得簡單圖G
            ',于是d'可簡單圖化為G'

            (b)若存在點Vi,Vj使得i
            =dj,必存在k使得(Vi, Vk)在G中但(Vj,Vk)不在G中。這時我們可以令GG=G-{(Vi,Vk),(V1,Vj)}+{(Vk,Vj),(V1,Vi)}。GG的度序列仍為d,我們又回到了情況(a)。
            題目練習:http://acm.hdu.edu.cn/showproblem.php?pid=2454
            posted on 2008-11-02 17:06 小果子 閱讀(1290) 評論(0)  編輯 收藏 引用 所屬分類: 學習筆記
            久久精品视频网| 精品国产福利久久久| 99精品国产免费久久久久久下载| 人人狠狠综合88综合久久| 热RE99久久精品国产66热| 伊人久久免费视频| 国产福利电影一区二区三区久久久久成人精品综合 | 久久久久久久人妻无码中文字幕爆 | 亚洲欧美日韩久久精品| 国产免费久久精品丫丫| 久久久久久国产精品美女| 国产精品99久久久精品无码| 久久水蜜桃亚洲av无码精品麻豆 | 777米奇久久最新地址| 国产精品成人精品久久久| 亚洲AV无码1区2区久久| 久久综合亚洲色HEZYO国产| 国产午夜久久影院| 亚洲级αV无码毛片久久精品| 日韩精品国产自在久久现线拍| 综合久久国产九一剧情麻豆| 久久国产高清一区二区三区| 国产精品99精品久久免费| 伊人久久精品无码av一区| 欧美亚洲日本久久精品| 久久精品国产一区二区| 99久久综合狠狠综合久久| 91精品国产高清91久久久久久| 伊人久久大香线蕉综合影院首页| 深夜久久AAAAA级毛片免费看 | 久久这里只精品99re66| 精品欧美一区二区三区久久久| 99久久精品国内| 久久精品国产半推半就| 97久久超碰成人精品网站| 精品久久久久久久无码| 精品久久久久久无码专区不卡| 色婷婷综合久久久中文字幕 | 人妻中文久久久久| 中文国产成人精品久久亚洲精品AⅤ无码精品| 久久久九九有精品国产|