第8章 图论 第8章 图论 8.1 图的基本概念 8.2 路径和回路 8. 图的矩阵表示 8. 二部图 8.5 平面图 8.6 树 8.7 有向树 8.8 运输网络 问题是要从这四块陆 地中任何一块开始， 通过每一座桥正好一 次，再回到起点。 欧拉在1736年解决了 这个问题 。 判定法则：如果通 奇数座桥的地方不 止两个，那么满足 要求的路线便不存 在了。如果只有两 个地方通奇数座桥 ，则可从其中任何 一地出发找到所要 求的路线。若没有 一个地 方通奇数座 桥，则从任何一地 出发，所求的路线 都能实现 第8章 图论 定义8.11一个图G是一个三重组V(G),E(G), G ,其中 V(G)是一个非空的结点(或叫顶点)集合,E(G)是边的集合, G 是从 边集E到结点偶对集合上的函数。一个图可以用一个图形表示。 例1设G=V(G),E(G), G ,其中V(G)=a,b,c,d,E(G)=e 1 ,e 2 ,e 3 ,e 4 , e 5 ,e 6 ,e 7 , G (e 1 )=(a,b), G (e 2 )=(a,c), G (e 3 )=(b,d), G (e 4 )=(b,c),
