计算机系统中图与网路分析(ppt 45页)

计算机系统中图与网路分析目录：
1 图与网路的基本概念
2 树图与最小生成树
3 最短路问题
4 网路的最大流和最小截
5 欧拉回路和中国邮递员问题
6 哈密尔顿回路及旅行推销员问题
7 选址问题

 

计算机系统中图与网路分析内容摘要：
    哥尼斯堡七桥问题 (Königsberg Bridge Problem)
    Leonhard Euler (1707-1783) 在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理
很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联
    图中可以只有点，而没有边；而有边必有点
    若节点vi, vj 之间有一条边 eij，则称 vi, vj 是 eij 的端点(end vertex)，而 eij 是节点 vi, vj 的关联边(incident edge)
    同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边
   一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(parallel edges)
既没有自环也没有平行边的图称为简单图(simple graph)
在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为 d ；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(even graph)

..............................