会计学引论(yǐnlùn)近代图论的历史(lìshǐ)可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。Euler回路(huílù)问题四色猜想(cāixiǎng)Euler回路(huílù)问题Ramsey问题(wèntí)第一节：图的基本概念1.图的概念(gàiniàn)图的基本概念1.图的概念(gàiniàn)2.关联(guānlián)的概念如图9-5中，v2和v5是边e4的两个端点(duāndiǎn)，e4为v2和v5的关联边；v2和v5是边e4的两个端点(duāndiǎn)，边e8是v4和v5的关联边。v4和v5均与e8相关联，所以v4和v5相邻(xiānꞬlín)。e6和e7有一个公共的端点v3，e6和e7相邻(xiānꞬlín)。e1即为一个环2.关联(guānlián)的概念v2和v5之间存在(cúnzài)e4和e5二条边，所以称v2和v5之间具有二重边d(v1)=4、d(v2)=4、d(v5)=5、d(v4)=1。v5和v4为奇点,v4为悬挂点,v1、v2、v3为偶点2.关联(guānlián)的概念3.简单图、完全(wánquán)图和二分图简单(jiǎndān)图、完全图和二分图图的基本概念4.连通(liántōng)与回路4.连通(liántōng)与回路5.部分(bùfen)图与子图5.部分(bùfen)图与子图图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)对于赋权图G=(V,E),其中边有权,构造(gòuzào)矩阵B=(bij)nn其中：图的基本概念与模型(móxíng)图的基本概念与模型(móxíng)第二节：树图树与图的最小树树与图的最小树1.树的概念(gàiniàn)2.树的性质(xìngzhì)3.部分(bùfen)树4.最小部分(bùfen)树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树5.最小部分(bùfen)树的求解树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法（1）破圈（回路(huílù)）法避圈法:从图中任选一点vi，让其他各点均属于；从沟通集合V和的连线中找出最小边，使之包含在最小部分树内。不妨假设最小边为（vi,vj）令，其他各点均属于；重复寻找从集合V到的最小边并使之包含在最小部分树内，直到(zhídào)图中的所有点都包含在集合V中为止。树与图的最小树树与图的最小树（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法（2）避圈（回路(huílù)）法树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树（3）顺序(shùnxù)生枝法（3）顺序(shùnxù)生枝法（3）顺序(shùnxù)生枝法（3）顺序(shùnxù)生枝法（3）顺序(shùnxù)生枝法（3）顺序(shùnxù)生枝法最短路(duǎnlù)问题最短路(duǎnlù)问题最短路(duǎnlù)问题最短路(duǎnlù)问题最短路(duǎnlù)问题最短路(duǎnlù)问题第三节：最短路(duǎnlù)问题令若用Lij代表从点到点的最短路，那么求从点i到点j的最短路的Dijkstra算法的具体步骤可概括如下：从点s出发，因Lss=0，将“0”标