运筹学大学课件12-1图论概念文档_第1页
运筹学大学课件12-1图论概念文档_第2页
运筹学大学课件12-1图论概念文档_第3页
运筹学大学课件12-1图论概念文档_第4页
运筹学大学课件12-1图论概念文档_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

图与网络分析问题提出应用：生产组织，邮递员问题，通讯网络等。哥尼斯堡七桥问题ABCD哥尼斯堡七桥问题在图中找一条经过每边一次且仅一次的路——欧拉回路。ADBC由点和边组成“环球旅行”问题在图中找一条经过每个点一次且仅一次的路——哈密尔顿回路。“中国邮路问题”在图中找一条经过每边的最短路——类似带权的欧拉回路。“货郎担问题”在图中找一条经过每个点一次且仅一次的最短路——带权的哈密尔顿回路。12.1图的基本概念

图论是专门研究图的理论的一门数学分支，主要研究点和线之间的几何关系。点:表示研究对象.连线：表示两个对象之间的某种特定关系。关系的对称性：两对象之间的关系可互换。

边：不带箭头的联线，表示对称关系。弧：带箭头的联线，表示不对称关系。无向图：简称图，有点和边组成。表示为：G=（V，E）V--点集合(非空）E--边集合例：右图V={v1，v2，v3，v4}E={e1，e2，…,e7}e1=[v1,v2]e2=[v1,v2],…,e7=[v4,v4]

有向图：由点和弧组成。表示为：

D=（V，A）V--点集合A--弧集合点数:n(G)或

n(D)边数:m(G)弧数:m(D)v1v2v3v4v5例：右图V={v1，v2,…,v5}A={a1，a2,…,a7}a1={v1,v5},a2={v5,v4},…,a7={v1,v4}无向图的有关概念端点:

e=[u,v]∈E,则u,v是e的端点,称u,v相邻.关联边:e是点u,v的关联边.环:若u=v,e是环.多重边:两点之间多于一条边.简单图:无环,无多重边的图.多重图:无环,允许有多重边的图.

次:以点v为端点的边的个数称为v的次.表示为:d(v)悬挂点:次为1的点.悬挂边:悬挂点的关联边.孤立点:次为0的点.奇点:次为奇数的点.偶点:次为偶数的点.孤立点悬挂边定理1:图G=(V,E)中,所有点的次之和是边数的两倍,即:定理2:任意一图中,奇点的个数为偶数.

证明:设V1--奇点的集合,

V2--偶点的集合偶数偶数偶数

链：点边交错系列，记为：圈：的链。初等链：点均不相同。初等圈：点均不相同。简单链：链中边均不相同。简单圈：圈中边均不相同。例：右图无重复点,无重复边有重复点,无重复边

连通图：任意两点之间至少有一条链。不连通图：连通分图：对不连通图，每一连通的部分称为一个连通分图。支撑子图：对G=（V，E），若G`=(V`,E`),使V`=V,E`E,则G`是G的一个支撑子图（生成子图）.有向图的有关概念基础图:对D=(V,A),去掉图上的箭头.始点和终点:对弧a=(u,v),u为a的始点

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论