会计学图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到(dédào)了充分的发展。第八章图论(túlùn)内容(nèiróng)：有向图，无向图的基本概念。内容(nèiróng)：有向图，无向图的基本概念。//2、图的表示法。例1、(1)无向图图形(túxíng)表示如右：3、相关(xiāngguān)概念。3、相关(xiāngguān)概念。3、相关(xiāngguān)概念。3、相关(xiāngguān)概念。如例1的(1)中，4、完全(wánquán)图例如(lìrú)：二、顶点(dǐngdiǎn)的度数，握手定理。二、顶点的度数，握手(wòshǒu)定理。如例1的(2)中，设定理(dìnglǐ)2：三、子图，补图。三、子图，补图。例3、2、补图定义(dìngyì)。如例3中，四、图的同构。例4、例5、(1)画出4个顶点，3条边的所有非同构例5、(2)画出3个顶点，2条边的所有非同构第二节路径(lùjìng)和回路（1）内容(nèiróng)：图的通路，回路，连通性。一、路径(lùjìng)，回路。一、路径(lùjìng)，回路。一、路径(lùjìng)，回路。例1、(1)例1、(1)例1、(2)例1、(2)4、性质(xìngzhì)。4、性质(xìngzhì)。二、图的连通(liántōng)度。2、短程(duǎnchénɡ)线，距离。3、无向(wúxiànɡ)图的连通。3、无向(wúxiànɡ)图的连通。4、有向图的连通(liántōng)。例2、例2、8.2路径(lùjìng)与回路（2）内容(nèiróng)：欧拉、哈密尔顿路径、赋权图中的最短路径。一、欧拉回路问题(wèntí)的提出。二、定义(dìngyì)。注意(zhùyì)：三、无向图是否具有欧拉通路(tōnglù)或回路的判定。例1、以下图形(túxíng)能否一笔画成？例1、以下图形能否(nénɡfǒu)一笔画成？例2、两只蚂蚁(mǎyǐ)比赛问题。四、有向图是否具有欧拉通路或回路(huílù)的判定。例3、判断以下(yǐxià)有向图是否欧拉图。二、哈密尔顿图一、问题(wèntí)的提出。二、哈密尔顿图。注意(zhùyì)：注意(zhùyì)：例1、判断下图是否具有(jùyǒu)哈密尔顿回路，通路。例1、判断下图是否具有(jùyǒu)哈密尔顿回路，通路。例1、判断(pànduàn)下图是否具有哈密尔顿回路，通路。哈密尔顿回路存在(cúnzài)的两件个充分条件7071727374A,b,d,c,e,f68.3图的矩阵(jǔzhèn)表示内容(nèiróng)：邻接矩阵，关联矩阵，可达矩阵。一、有向图的邻接矩阵。例1、有向图2、性质(xìngzhì)。3.的元素(yuánsù)的意义4.的元素(yuánsù)的意义5、求5、求5、求例4、在例1的有向图二、无向(wúxiànɡ)图的关联矩阵。例2、无向图2、性质(xìngzhì)。(4)三、有向简单(jiǎndān)图（无环）的关联矩阵。例2、有向图2、性质(xìngzhì)。四、有向图的可达性矩阵(jǔzhèn)。(了解)四、有向图的可达性矩阵(jǔzhèn)。(了解)8.7树内容(nèiróng)：无向树，生成树。一、无向树。例1、例1、2、树的六个等价(děngjià)定义。2、树的六个等价(děngjià)定义。3、性质(xìngzhì)。例2、画出所有(suǒyǒu)的6个顶点的非同构的树。例2、画出所有(suǒyǒu)的6个顶点的非同构的树。例2、画出所有(suǒyǒu)的6个顶点的非同构的树。例2、画出所有(suǒyǒu)的6个顶点的非同构的树。例2、画出所有(suǒyǒu)的6个顶点的非同构的树。二、生成(shēnɡchénɡ)树。例4、2、连通(liántōng)图的性质。3、最小生成(shēnɡchénɡ)树。求最小生成(shēnɡchénɡ)树的方法解：解：解：解：注意(zhùyì)：第八章小结(xiǎojié)与例题一、无向(wúxiànɡ)图与有向图。一、无向(wúxiànɡ)图与有向图。二、通路(tōnglù)，回路，图的连通性。二、通路(tōnglù)，回路，图的连通性。三、欧拉图。四、哈密尔顿图。五、图的矩阵(jǔzhèn)表示。六、无向(wúxiànɡ)树及生成树。七、应用(yìngyòng)例1、设图例1、设图例2、下列各序列中，可以构成无向简单图的例3、右图所示的无向图中，例4、下图所示的六个图中，强连通，单