圖論教案final

1、圖論與網(wǎng)絡(luò)專題第1頁共22頁1圖論的著名問題與歷史圖論的著名問題與歷史圖論是數(shù)學(xué)中一個既古老又年輕的數(shù)學(xué)分支歐拉1736年關(guān)于哥尼斯堡七橋問題論文的發(fā)表標(biāo)志著圖論的誕生自二十世紀(jì)五十年代開始，由于運籌學(xué)、計算機科學(xué)的促進(jìn)，以及應(yīng)用領(lǐng)域的擴大，圖論已成為一個獨立的數(shù)學(xué)分支特別在近三十年，圖論正經(jīng)歷著一個蓬勃發(fā)展的時期，表現(xiàn)出年輕學(xué)科所具有的強大生命力一.圖論中的幾個著名問題例1.哥尼斯堡七橋問題哥尼斯堡歷史上曾是德國東普魯士的省會，第二次

2、世界大戰(zhàn)后歸蘇聯(lián)所有，也就是現(xiàn)在的加里寧格勒市.普列格爾（Pregel）河穿城而過，河中有兩個小島，島與河岸及島與島之間有七座橋.當(dāng)時流行很廣的一個難題是：能否從河岸或兩個小島中的任一處出發(fā)，經(jīng)過每一座橋一次且僅一次再回到出發(fā)地呢？這個問題被瑞士數(shù)學(xué)家歐拉解決了.如下圖所示，A、B、C、D表示陸地.1736年，歐拉（17071783）在俄國彼得堡科學(xué)院院報上發(fā)表了一篇論文.他在論文中引進(jìn)了圖的概念和方法，用抽象分析法將這個問題化為第一個

3、圖論問題：即把每一塊陸地用一個點來代替，將每一座橋用聯(lián)接相應(yīng)的兩個點的一條線來代替，從而相當(dāng)于得到一個「圖」，將七橋問題轉(zhuǎn)化為一筆畫問題.歐拉證明了這個問題沒有解——這是由于此「圖」與每個頂點相關(guān)聯(lián)的邊數(shù)均為奇數(shù)，并且推廣了這個問題.給出了對于一個給定的圖可以某種方式一筆畫的判定法則.這項工作使歐拉成為圖論﹝及拓?fù)鋵W(xué)﹞的創(chuàng)始人.引深：圖G是歐拉圖的充要條件是什么？例2哈密爾頓多面體問題1856年英國數(shù)學(xué)家哈密爾頓（17901868）提出

4、了這樣一個問題：用一個規(guī)則的實心十二面體，它的二十個頂點標(biāo)出世界著名的二十個城市，要求游戲者找一條抽象成圖論與網(wǎng)絡(luò)專題第3頁共22頁頓的理論.1857年，英國數(shù)學(xué)家凱萊在研究飽和碳?xì)浠衔锏耐之愋泽w時，發(fā)現(xiàn)了“樹”的概念和理論，并由此預(yù)見了未知化合物的存在.1936年，匈牙利數(shù)學(xué)家哥尼科，總結(jié)前人的成果，發(fā)表了第一部圖論專著《有限圖和無限圖的理論》.自二十世紀(jì)五十年代開始，由于運籌學(xué)、計算機的促進(jìn)以及應(yīng)用領(lǐng)域的擴大，圖論已成為了一個獨

5、立的數(shù)學(xué)分支.特別在近二十年，圖論正經(jīng)歷著一個蓬勃發(fā)展的時期，表現(xiàn)出年輕學(xué)科所具有的強大生命力.許多大學(xué)的系，如數(shù)學(xué)系、計算機科學(xué)系、運籌系、組合優(yōu)化系、電機系等都開設(shè)了圖論這門課.圖論是一門應(yīng)用廣泛的數(shù)學(xué)分支，它不但在自然科學(xué)的許多領(lǐng)域有重要的應(yīng)用，還應(yīng)用于社會科學(xué)的諸多方面.許多實際問題（離散）所建立的數(shù)學(xué)模型就是一個圖論模型.圖論不但與大學(xué)生數(shù)學(xué)建摸競賽聯(lián)系甚緊，而且在中小學(xué)數(shù)學(xué)競賽中經(jīng)常出現(xiàn)來源于圖論的題目.2圖的基本概念一.無

6、向圖、有向圖、子圖1.（無向）圖（無向）圖無向圖是指三元組，其中是一個非空集合，稱為G??fEVV頂點集頂點集；是任意集合，稱為邊集邊集；是到的映射，記作EfE????Vvvvvjiji?或??fEVG???EVG?在E中重復(fù)次的邊稱為重邊重邊；兩端點重合的邊稱為環(huán)kk2.有向圖有向圖有向圖是指三元組，其中是非空頂點集，是邊的集D??fEVVE合，是到的映射記作或fE????VvvvvVVjiji?????fEVD???EVD?有向圖與