一筆成畫游戲課件

一筆成畫游戲五斤葫蘆三斤瓢，八斤油兩下約引例1：一個(gè)投遞員要投遞郵件，從郵局出發(fā)，經(jīng)過所有他負(fù)責(zé)投送的街道，完成任務(wù)后返回郵局，問該投遞員應(yīng)如何行走才能使路程最短？（V1是郵局，V2-V10是街道交叉點(diǎn)）V1V4V6V5V7V10V9V8V3V211111111111引例2：一個(gè)旅行商人要到某些城鎮(zhèn)去經(jīng)商，他想經(jīng)過每一個(gè)城鎮(zhèn)一次，且僅僅一次，而且要行程最短，應(yīng)如何安排路線？v1v2v3v4v52611120813913

引例3：最短路問題一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？V1V2V3V4V5V6V76101232557691481116引例4：某物流中心有9個(gè)分銷點(diǎn)，道路如圖所示，要以V0為中心建立有限廣播網(wǎng)絡(luò)，要求沿著道路架設(shè)廣播線，問如何拉線才能使線最短？V1V2V8V7V6V5V3V4V02532144441551132圖的基本概念與模型圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。圖的定義： 若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖G可以定義為點(diǎn)和邊的集合，記作：其中:V——點(diǎn)集E——邊集※圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。圖的基本概念與模型(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示。圖的基本概念與模型定義:圖中的點(diǎn)用v表示，邊用e表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5

端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。圖的基本概念與模型

環(huán),多重邊,簡(jiǎn)單圖如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的基本概念與模型

次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。每個(gè)環(huán)視作兩條邊。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:

一個(gè)圖的次等于各點(diǎn)的次之和。圖的基本概念與模型

鏈，圈，連通圖圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意vi,t-1和vit均相鄰稱為鏈。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。圖的基本概念與模型

網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖G＝（V，E），對(duì)G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過能力(容量)等等。端點(diǎn)無(wú)序的賦權(quán)圖稱為無(wú)向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256圖的基本概念與模型

出次與入次

有向圖中，以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用d+(vi)表示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用表示d-(vi)；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次。※有向圖中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。圖的基本概念與模型圖的模型應(yīng)用例1有甲,乙,丙,丁,戊,己6名運(yùn)動(dòng)員報(bào)名參加A,B,C,D,E,F6個(gè)項(xiàng)目的比賽。下表中打√的是各運(yùn)動(dòng)員報(bào)告參加的比賽項(xiàng)目。問6個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。ABCDEF甲√√乙√√√丙√√丁√√戊√√√己√√√圖的基本概念與模型解：用圖來(lái)建模。把比賽項(xiàng)目作為研究對(duì)象，用點(diǎn)表示。如果2個(gè)項(xiàng)目有同一名運(yùn)動(dòng)員參加，在代表這兩個(gè)項(xiàng)目的點(diǎn)之間連一條線，可得下圖。ABCDEF在圖中找到一個(gè)點(diǎn)序列，使得依次排列的兩點(diǎn)不相鄰，即能滿足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A圖的基本概念與模型圖的矩陣描述：如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來(lái)表示一個(gè)圖，圖的矩陣表示：權(quán)矩陣。對(duì)于賦權(quán)圖G=(V,E),其中邊有權(quán),構(gòu)造矩陣B=(bij)n

n

其中：圖的基本概念與模型權(quán)矩陣圖的基本概念與模型v5v1v2v3v4v643322