资源描述：
《ch1(图论概述及基本概念)_上传_921307348》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章第一章基本概念基本概念计算机系网络所：张小平计算机系网络所：张小平zhxp@tsinghua.edu.cnzhxp@tsinghua.edu.cn主要内容主要内容•图论概述•图的基本概念及定义•图的代数表示图论概述图论概述•离散数学：–离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般是有限个或可数个元素。–离散数学充分契合了计算机科学的特点–离散数学是计算机科学重要的基础理论之一•离散数学主要包括以下四个方面：–数理逻辑、集合论、图论、代数结构图论概述图论概述•图论〔GraphTheory〕是数学的一个分支，它以图为研究对象
2、。•世界上各事物之间，自然界内诸现象之间经常存在着某些必然的联系，需要人们通过研究分析，去揭示这些关系。•人们常把事物、现象用结点表示，用有向的或无向的边来表示它们之间的联系。这就构成了图论中所讨论的图。图论概述图论概述•历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，其原始问题有很强的实际背景。•18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结。图论概述图论概述•欧拉与哥尼斯堡城七桥问题图论概述图论概述•欧拉对“七桥问题”的研究是图论研究的开始。图论概述图论概
3、述•早期的图论与数学游戏有密切的联系：–周游世界问题、渡河问题、三家三井问题…•20世纪后，图论的应用渗透到其他学科领域，如物理、化学、运筹学、博弈论、计算机网络、社会学、语言学等等•对于基础图论来说，不要求事先掌握高深的数学工具，只需要有集合论和线性代数的基本概念，即可进行学习图论概述图论概述•学习目标：–掌握图论的基本概念、基本方法–掌握图论的基本理论和重要定理、算法–同时学习将实际问题转化为图论问题的能力图论是一个非常有用的数学工具图论概述图论概述•如何学好图论：–注意图论中解题或证明的方法：与微积分不同，反证法、构造法是图论解题的主要方法。–从
4、基本概念入手充分掌握定义、定理，并重视定理的证明过程。–必须保质保量完成作业。主要内容主要内容•图论概述•图的基本概念及定义•图的代数表示图的基本概念及定义图的基本概念及定义•定义1.1.1二元组GVGEG=((),())称为图。其中VG()是非空集，称为结点集；E(G)为VG()各结点之间边的集合，称为边集。•常用GVE=(,)表示图。•当VE,都是有限集合时，称G为有限图。•当或VE是无限集合时，称G为无限图。•一般情况下，给定GVE=(,)，如不加特殊说明，认为Vvvvv={}123,,,,"n，，E={eee123,,,,"em}即结点数，Vn
5、=边数。Em=图的基本概念及定义图的基本概念及定义•有向图和无向图：–若图中的边为有向的，则称为有向图–若图中的边为无向的，则称为无向图–若图中既有有向边又有无向边，则称为混合图图的基本概念及定义图的基本概念及定义•图的边可用ek=(vi,vj)表示–称与是vivj相邻结点–称分别与ekvi,vj相关联–如果是有向边，称是的ekviek始点，是的vjek终点，并称是的vivj直接前驱，是的vjvi直接后继–如果是无向边，称ekvi,vj是的两个ek端点图的基本概念及定义图的基本概念及定义•只与一个结点相关联的边称为自环•在同一对结点之间可以存在多条边，
6、称为重边•含有重边的图叫多重图图的基本概念及定义图的基本概念及定义•定义1.1.2G=(V,E)的某结点所关联的边数称为该结点的度，用d(v)表示。如果v带有自环，则自环对d(v)的贡献为2。•有向图中：–以结点v为始点的边数目称为v的正度，记为d+(v)–以结点v为终点的边数目称为v的负度，记为d-(v)•显然，有d+(v)＋d-(v)＝d(v)图的基本概念及定义图的基本概念及定义•定义1.1.3任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。•没有任何边的简单图叫空图，记为N。n•任何两结点间都有边的简单图称为完全图,记为K。n–K中每
7、个结点的度为n-1n图的基本概念及定义图的基本概念及定义•性质1.1.1设G=(V,E)有n个结点，m条边，则∑d(v)=2mv∈V(G)•性质1.1.2G中度为奇数的结点必为偶数个•性质1.1.3有向图G中正度之和等于负度之和1•性质1.1.4K中的边数为n()n−1n2•性质1.1.5非空简单图中一定存在度相同的结点图的基本概念及定义图的基本概念及定义•定义1.1.4如果图G=(V,E)的每条边ek=(vi,vj)都赋予一个实数w做为该边的权，则称G为赋k权图。如果这些权都是正实数，就称G为正权图。图的基本概念及定义图的基本概念及定义•定义1.1.
8、5给定G=(V,E)，如果存在另外一个图G’=(V’,E’)，满足V’包含于V，E’包含于E，
