圖與網(wǎng)絡(luò)

內(nèi)容概要

　　本書主要闡述網(wǎng)絡(luò)最優(yōu)化問(wèn)題中運(yùn)用的一些重要的圖論方法和用圖論方法解決的實(shí)際問(wèn)題，如最小連接問(wèn)題、最優(yōu)線路問(wèn)題、工作分派問(wèn)題、網(wǎng)絡(luò)流問(wèn)題，以及圖的染色和標(biāo)號(hào)在實(shí)際中的應(yīng)用等。書中附有大量的例子說(shuō)明圖論在自然科學(xué)和社會(huì)科學(xué)中的應(yīng)用。對(duì)于圖論中的某些重要結(jié)論和著名定理，本書給出了簡(jiǎn)要而精彩的證明，使得讀者能夠體會(huì)到圖論方法的精妙之處。同時(shí)，我們也提出一些沒有解決的問(wèn)題。

作者簡(jiǎn)介

　　劉桂真，1944年生人，1968年大學(xué)畢業(yè)于山東大學(xué)數(shù)學(xué)系，1981年研究生畢業(yè)于山東大學(xué)數(shù)學(xué)系。1985年至1987年在加拿大SimonFraser大學(xué)訪問(wèn)兩年。自1981年以來(lái)一直從事圖論和組合優(yōu)化等方面的研究工作，共發(fā)表論文160余篇，出版著作4部，其中《運(yùn)籌學(xué)》獲教育部科技進(jìn)步二等獎(jiǎng)。先后共承擔(dān)教學(xué)項(xiàng)目2項(xiàng)，其中國(guó)家級(jí)教學(xué)研究項(xiàng)目1項(xiàng)，國(guó)家和省部級(jí)科研項(xiàng)目16項(xiàng)，其中承擔(dān)國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目2項(xiàng)，面上項(xiàng)目6項(xiàng)。并獲教學(xué)獎(jiǎng)6項(xiàng)，其中省部級(jí)4項(xiàng)，廳局級(jí)獎(jiǎng)勵(lì)2項(xiàng)；獲科技進(jìn)步獎(jiǎng)11項(xiàng)，其中省部級(jí)7項(xiàng)，廳局級(jí)獎(jiǎng)勵(lì)4項(xiàng)。1996年至2002年期間曾先后6次赴香港4所大學(xué)進(jìn)行合作研究。目前為山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院教授，國(guó)務(wù)院聘任的博士生導(dǎo)師，曾任該院第一任院長(zhǎng)。曾是國(guó)家教委高等學(xué)校數(shù)學(xué)與力學(xué)教學(xué)指導(dǎo)委員會(huì)委員，中國(guó)圖論研究會(huì)理事長(zhǎng)。目前兼任威海分校數(shù)學(xué)系系主任，是山東省科學(xué)技術(shù)拔尖人才，校聘關(guān)鍵崗位人員。1993年起享受政府特殊津貼，曾是《數(shù)學(xué)進(jìn)展》和《應(yīng)用數(shù)學(xué)》編委會(huì)編委，全國(guó)高校理科高等數(shù)學(xué)研究會(huì)理事長(zhǎng)，全國(guó)組合數(shù)學(xué)和圖論研究會(huì)副理事長(zhǎng)等。目前是國(guó)家自然科學(xué)基金、博士點(diǎn)基金、博士后基金、優(yōu)秀博士論文等通訊評(píng)議專家，是數(shù)學(xué)國(guó)家教學(xué)獎(jiǎng)、數(shù)學(xué)和力學(xué)國(guó)家自然科學(xué)獎(jiǎng)評(píng)審專家，國(guó)家科技部重大項(xiàng)目咨詢專家，863項(xiàng)目評(píng)審專家等。目前是國(guó)際學(xué)術(shù)刊物GraphsandCombinatorics的編委。由于在科研方面的成績(jī)突出，被“美國(guó)數(shù)學(xué)評(píng)論”聘為評(píng)論員及美國(guó)數(shù)學(xué)會(huì)會(huì)員，分別被美國(guó)和英國(guó)劍橋國(guó)際名人傳記中心認(rèn)為是有突出貢獻(xiàn)的科學(xué)家而載入“世界名人錄”，“世界科技工程名人錄”等。曾是全國(guó)第九、十屆政協(xié)委員，民盟山東省委員會(huì)副主任委員。曾被評(píng)為全國(guó)先進(jìn)教職工、山大三八紅旗手和山大十大女杰。2006年被評(píng)為山東省教學(xué)名師，2007年被評(píng)為國(guó)家教學(xué)名師?！　～@獎(jiǎng)情況　　“圖論與最優(yōu)化問(wèn)題研究”于1997年獲山東省科技進(jìn)步二等獎(jiǎng)（第一位）　　“關(guān)于圖的因子理論的研究”于1995年獲國(guó)家教委科技進(jìn)步二等獎(jiǎng)（第一位，獨(dú)立完成）　　“關(guān)于擬陣基圖理論的研究”于1992年獲山東省科技進(jìn)步二等獎(jiǎng)（第一位，獨(dú)立完成）　　“關(guān)于圖論和擬陣中的組合拓?fù)浞椒ā钡难芯坑?991年獲國(guó)家教委科技進(jìn)步三等獎(jiǎng)（第三位）　　關(guān)于擬陣?yán)碚摰难芯坑?991年獲山東省教委科技進(jìn)步論文一等獎(jiǎng)（第一位）　　1989，1990，1992年分別獲山東省教委科技進(jìn)步論文二等獎(jiǎng)各一項(xiàng)（第一位）　　“運(yùn)籌學(xué)”獲1999年國(guó)家教育部教材科技進(jìn)步二等獎(jiǎng)（第一位）　　“運(yùn)籌學(xué)課程的改革與實(shí)踐”獲2001年山東省優(yōu)秀教學(xué)成果二等獎(jiǎng)（第二位）　　圖的正交因子分解和哈密爾頓圈問(wèn)題研究，獲2001年山東省科技進(jìn)步三等獎(jiǎng)（第一位）。

書籍目錄

前言1．圖論方法與問(wèn)題2．最小連接問(wèn)題3．最優(yōu)路線問(wèn)題4．圖的匹配問(wèn)題5．圖的染色6．有向圖7．網(wǎng)絡(luò)流8．圖的標(biāo)號(hào)問(wèn)題9．圖論方法應(yīng)用實(shí)例參考文獻(xiàn)

章節(jié)摘錄

　　1．圖論方法與問(wèn)題　　哥尼斯堡（Konigsberg）七橋問(wèn)題　在哥尼斯堡城的普萊格爾（Pregel）河中有兩個(gè)小島。在河的兩岸和小島之間有七座橋，如圖1—1所示。問(wèn)題是能否從某地出發(fā)通過(guò)每一座橋恰好一次而回到出發(fā)地？很多人嘗試過(guò)，都沒有成功，但卻沒有人說(shuō)明為什么不能成功。直到1736年歐拉用圖論方法證明了這個(gè)問(wèn)題是不可能的。他將該問(wèn)題轉(zhuǎn)化為圖1—2中的圖，問(wèn)能否從一個(gè)頂點(diǎn)開始一筆畫出這個(gè)圖形而回到該頂點(diǎn)？由于這個(gè)圖的頂點(diǎn)的度全為奇數(shù)，因此答案是否定的。在第3節(jié)將詳細(xì)討論有關(guān)這方面的問(wèn)題。由于歐拉1736年在他的論文中解決了這個(gè)問(wèn)題并得到了更一般性的結(jié)論，使他成為圖論的創(chuàng)始人，他的論文被認(rèn)為是圖論方面的第一篇論文而聞名于世?！　‖F(xiàn)實(shí)生活中的許多問(wèn)題都可以用一個(gè)圖來(lái)表示。例如，用頂點(diǎn)表示城市，若兩個(gè)城市之間有一條鐵路相連，則在兩個(gè)頂點(diǎn)之間連一條邊，于是一個(gè)交通網(wǎng)絡(luò)就可以用一個(gè)圖來(lái)表示。同樣地，用頂點(diǎn)表示電話，用邊表示兩個(gè)電話之間的線路，則通訊網(wǎng)絡(luò)就可以用一個(gè)圖來(lái)表示；用頂點(diǎn)表示人，若兩個(gè)人認(rèn)識(shí)，則在對(duì)應(yīng)的頂點(diǎn)之間連一條邊，一個(gè)圖就表示一個(gè)人際關(guān)系的網(wǎng)絡(luò)。類似地，化學(xué)中的分子結(jié)構(gòu)、物理學(xué)中的電網(wǎng)絡(luò)、計(jì)算機(jī)的聯(lián)網(wǎng)等問(wèn)題都可以用一個(gè)圖來(lái)表示。將優(yōu)化與決策中的實(shí)際問(wèn)題用一個(gè)圖來(lái)表示，通過(guò)研究圖的性質(zhì)并設(shè)計(jì)優(yōu)化的算法來(lái)解決這些問(wèn)題，這就是優(yōu)化的圖論方法。

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    圖與網(wǎng)絡(luò) PDF格式下載

---