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

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

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

環,多重邊,簡單圖如果邊e的兩個端點相重，稱該邊為環。如右圖中邊e1為環。如果兩個點之間多于一條，稱為多重邊，如右圖中的e4和e5，對無環、無多重邊的圖稱作簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的基本概念與模型

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

一個圖的次等于各點的次之和。圖的基本概念與模型

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

網絡（賦權圖）設圖G＝（V，E），對G的每一條邊(vi,vj)相應賦予數量指標wij，wij稱為邊(vi,vj)的權,賦予權的圖G稱為網絡(或賦權圖）。權可以代表距離、費用、通過能力(容量)等等。端點無序的賦權圖稱為無向網絡，端點有序的賦權圖稱為有向網絡。①②③④⑤⑥910201571419256圖的基本概念與模型

出次與入次

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

n

其中：圖的基本概念與模型權矩陣圖的基本概念與模型v5v1v2v3v4v643322