计算机系统中图与网路分析(ppt 45页)
所属分类:信息化知识
文件大小:900 KB
下载要求:10 学币或VIP
点击下载计算机系统中图与网路分析目录:
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)
精品资料网 m.cnshu.cn
Copyright © 2004- 粤ICP备10098620号-1