圖論的基本思想培訓講座課件

1、圖論的基本思想培訓講座圖論的基本思想培訓講座一、引言二、圖的定義三、頂點的度四、K部圖-托蘭定理五、邊數最少連通圖-樹六、一筆畫-歐拉問題七、環(huán)游世界-哈密頓問題八、染色-拉姆賽問題一、引言一、引言圖論最早起源于一些數學游戲的難題研究，如歐拉所解決的哥尼斯堡七橋問題，以及在民間廣泛流傳的一些游戲難題，如迷宮問題、博奕問題、棋盤上馬的行走路線問題等 這些古老的難題，當時吸引了很多學者的注意在這些問題研究的基礎上又繼續(xù)提出了著名的四色猜想和哈密頓（環(huán)游世界）數學難題 一、引言圖論最早起源于一些數學游戲的難題研究，如歐拉所解決的一、引 言1847年，圖論應用于分析電路網絡，這是它最早應用于工程科學，

2、以后隨著科學的發(fā)展，圖論在解決運籌學，網絡理論，信息論，控制論，博奕論以及計算機科學等各個領域的問題時，發(fā)揮出越來越大的用在人們的社會實踐中，圖論已成為解決自然科學、工程技術、社會科學、生物技術以及經濟、軍事等領域中許多問題的有力工具之一，因此越來越受到數學家和實際工作者的喜愛我們這里只是介紹一些基本概念、原理以及一些典型的應用實例，目的是大家在今后學習過程中，可以把圖論的基本知識、方法作為工具 一、引 言1847年，圖論應用于分析電路網絡，這是它最早應用二、圖的定義首先要注意，我們這里所討論的圖論中的“圖”，并不是以前學過的通常意義下的幾何圖形或物體的形狀圖，也不是工程設計圖中的“圖”，而是

3、以一種抽象的形式來表達一些確定的對象，以及這些對象之間具有或不具有某種特定關系的一個數學系統(tǒng)也就是說，幾何圖形是表述物體的形狀和結構，圖論中的“圖”則描述一些特定的事物和這些事物之間的聯(lián)系它是數學中經常采用的抽象直觀思維方法的典型代表 二、圖的定義首先要注意，我們這里所討論的圖論中的“圖”，并不二、圖的定義一提到圖論的起源，人們總要講述早在1736年，歐拉就把所謂的哥尼斯堡7橋問題化為圖論問題 :圖G=(V,E) ; | V |=n, | E |=e;二、圖的定義一提到圖論的起源，人們總要講述早在1736年，歐二、圖的定義同構子圖相鄰環(huán)平行邊簡單圖完全圖有限圖二、圖的定義同構二、圖的定義問題1

4、: 某大型舞會有2019個人參加，已知他們每個人都至少和其中的一個人握過手,則必有一個人至少和其中的兩個人握手.問題2: 9人相遇,發(fā)現(xiàn)他們中的任意3人中,至少有兩人可以用同一種語言.對話如果每人至多可以說3中語言,則至少有3人可以用同一種語言對話. v2把9改成8,命題不成立. 反例: 1,12表示12種顏色，則下圖無同色三角形。V2V3V4V1V6V7V5V8V1V2V3V5V6二、圖的定義問題1: 某大型舞會有2019個人參加，已知他們二、圖的定義問題3: 一次會議有n名教授 .則可以將這n個人分為兩組，使得每個人 在另一組中認識的人數 不少于他在同一組中認識的人數(i=1,2,3,n)

5、. 想法:調整法 設S為兩組之間的連線條數.由于分法有限,必存在一種分法使S最大,則問題得證.否則,S增加.二、圖的定義問題3: 一次會議有n名教授 三、頂點的度度 ： d(v) ;(G),(G) 表示最大度與最小度.奇頂點，偶頂點.正則圖：d(v)=k(常數）.在二百多年前，歐拉給出這樣的一個著名的結論：“如果許多人在見面時握了手，被握過手的人數為偶數.” 進而得到：“握過奇數次手的人有偶數個.”握手原理：d(v1)+d(vn)=2e.問題1：在n（n2)個人中，至少有兩個人，他們的朋友數是一樣多的.三、頂點的度度 ： d(v) ;(G),(G) 表示最三、頂點的度問題2：國際乒乓球男女混合

6、雙打比賽有24對選手參加.賽前一些選手握了手，但同一對選手之間不握手.賽后某個男選手問每個選手的握手次數，個人回答各不相同，問這名男選手的女搭檔和多少人握了手？三、頂點的度問題2：國際乒乓球男女混合雙打比賽有24對選手參四、托蘭定理1941年，匈牙利數學家托蘭為了回答這樣的問題：“n個頂點的圖G不包含m個頂點的完全圖 ,則圖G的最大邊數是多少？”而提出的他的著名的定理，從而開創(chuàng)了圖論研究的一個新的方向“極圖理論”.K部圖完全k部圖完全偶圖的邊數： ，四、托蘭定理1941年，匈牙利數學家托蘭為了回答這樣的問題：四、托蘭定理托蘭定理1： 有n 個頂點且不含三角形的圖G的最大邊數為 .定理證明的想法

7、是：用極端性原理. 問題2：設圖G有20個頂點，101條邊，則G中一定有兩個具有公共邊的三角形.托蘭定理2：設n階圖G不含 ，則G的邊數 . 當且僅當四、托蘭定理托蘭定理1： 有n 個頂點且不含三角形的圖G的最四、托蘭定理四、托蘭定理四、托蘭定理問題3： 設 是平面上的6點，其中任意三點不共線. （1）如果這些點之間連13條線段，則必存在4點，它們每兩點之間都有線段連接； （2）如果這些點之間只有12條線段，請你畫一個圖形，說明（1）結論不成立. 分析：（1）問題等價存在 ; （2）構造完全3部圖 ，從中任取4點，總有兩點屬于同一部分，而這兩點是不相鄰的，因此任4點均不構成 .四、托蘭定理問題

8、3：五、樹鏈圈連通圖樹樹葉（懸掛點）連通分支生成樹（圖G的一個生成子圖是一棵樹） 常用的方法是：破圈法 避圈法五、樹鏈五、樹如果樹T的頂點數 2，則T中至少有兩個懸掛點；設樹T的頂點數為n，則它的邊數e=n-1;設T是有n個頂點，e條邊的圖，則 （1）圖T是樹； （2）圖T無圈, 且e=n-1； （3）圖T連通，且e=n-1. 這三個命題是等價的.五、樹如果樹T的頂點數 2，則T中至少有兩個懸掛點；五、樹問題1： n 個城市，每個城市都可以通過一些中轉城市與另一個城市通話，則至少有n-1條直通的電話線路，每條連結兩個城市. 分析：破圈法，得到樹.問題2： 在一次講演中，有五位數學家每人打2次盹

9、，并且每兩人均有同時在打盹的時刻，則一定有三人，他們有同時打盹的時刻. 分析：每兩個數學家均有同時打盹的時刻連邊，圖G中至少有 條邊，而圖G的頂點為10,問題得證. 五、樹問題1：六、歐拉問題一筆畫定理：有限圖G是一條鏈（即可以一筆畫成）的充分必要條件是：G是連通的，且奇頂點個數等于0或2.當且僅當奇頂點的個數等于0時，連通圖G是一個圈.推廣：如果連通圖G有2k個奇頂點，則圖G可以用k 筆畫成，且至少要用k筆畫成. 將2k個奇頂點分成k對，每對連邊，構成一個圈。六、歐拉問題一筆畫定理：有限圖G是一條鏈（即可以一筆畫成）的六、歐拉問題如圖，大三角形的三個頂點分別涂以A、B、C三種.顏色在大三角形

10、內取若干個點，將它分為若干個小三角形，每兩個三角形或者有一條公共邊，或有一個公共頂點，或者完全沒有公共點.將每個小三角形的頂點也分別涂以A、B、C三種顏色之一，則不管怎樣涂色，都有一個小三角形，它的三個頂點的顏色全不相同. 分析： 當兩個三角形有一條公共邊AB時，連一邊，如圖.反證.假設沒有，則度為0或者2，由于d(u)=1,所以至少有一個奇頂點v.六、歐拉問題如圖，大三角形的三個頂點分別涂以A、B、C三種.七、哈密頓問題1856年，英國著名數學家哈密頓提出一個名為“環(huán)游世界”的游戲，他用一個正十面體的二十個頂點代表二十個大城市，要求沿著棱，從一個城市出發(fā)經過每個城市恰好一次，然后回到出發(fā)點。

11、這種鏈（圈）（它經過圖上各頂點一次且僅一次），稱為哈密頓鏈（圈），一個圈若包含哈密頓圈，則稱這個圖是哈密頓圖。七、哈密頓問題1856年，英國著名數學家哈密頓提出一個名為“七、哈密頓問題一般地，對于一個偶圖 ，如果 那么G一定無哈密頓圈。如果 的差大于1 那么G一定無哈密頓鏈。 證明的想法是如圖：七、哈密頓問題一般地，對于一個偶圖 七、哈密頓問題問題1： 下圖中是國際象棋盤，一匹馬在右下角，試問：馬能否連續(xù)地把棋盤上所有的格都跳到一次且僅僅一次？如果去掉了棋盤對角上的兩個黑格，又將怎樣？ 問題 是否存在一條哈密頓鏈？1518722112852482116276232291714191031122

12、54209321326330馬七、哈密頓問題問題1：1518722112852482116七、哈密頓問題對于一個連通圖，是否存在哈密頓鏈（圈）的問題.這是個充分條件，不必要，比如：七、哈密頓問題對于一個連通圖，是否存在哈密頓鏈（圈）的問題.七、哈密頓問題七、哈密頓問題七、哈密頓問題問題3：一只老鼠吃333立方體乳酪，其方法是借助于打洞通過所有的27個111正立方體。如果它在一個角上開始，然后依次走向未吃的立方體，問它吃完時能否恰在立方體的中心。分析：作圖G：頂點表示111的立方體，當且僅當兩個小正方體有公共面時，對應的兩頂點以邊相連。則G是偶圖， 則G無哈密頓鏈。七、哈密頓問題問題3：一只老鼠吃333立方體乳酪，其方法八、拉姆賽問題英國邏輯學家拉姆賽通常，我們把與圖的染色、拉姆賽數、抽屜原則關聯(lián)的問題拉