下下回回停停1.图论的基本概念2.最短路问题及算法3.最小生成树及算法4.旅行售货员问题5.循环比赛的名次“图论”亦称“网络论”是组合数学的一个分支用直观图形、数学方法来研究图的组合关系。图论开创于瑞士数学家欧拉Euler解决了哥尼斯堡“七桥问题”的1736年。ABCDABDC是否可从某处出发经过每座桥恰只一次然后再回到起点七桥问题欧拉欧拉17071707--17831783年出生在瑞士的年出生在瑞士的巴塞尔巴塞尔BaselBasel城城1313岁就进巴塞尔大岁就进巴塞尔大学读书得到当时最有名的数学家约学读书得到当时最有名的数学家约翰翰··伯努利伯努利16671667--17481748年的精心指年的精心指导导1515岁大学毕业岁大学毕业1616岁获得硕士学位岁获得硕士学位欧拉是科学史上最多产的一位杰出的数学家据统计他那不倦的一生共写下了886本书籍和论文几乎涉及所有数学分支彼得堡科学院为了整理他的著作足足忙碌了四十七年他在双目失明以后也没有停止对数学的研究在失明后的17年间他还口述了几本书和400篇左右的论文欧拉对数学分析作出了巨大的贡献是变分法的奠基人、复变函数的先驱、拓扑学之父。他还把数学应用于天文学、力学以及物理学的各个领域并作出了重要贡献。“读读欧拉著作这是我们一切人的老师。”——拉普拉斯“欧拉的研究仍旧是对数学的不同范围的最好的学校并且没有任何别的可以代替它。”——高斯欧拉还创设了许多数学符号例如π1736年i1777年e1748年sin和cos1748年tg1753年△x1755年Σ1755年fx1734年等2007年4月15日对于数学界来说是一个特别的日子——瑞士数学家、物理学家兼工程师莱昂哈德?欧拉LeonhardEuler公元1707-1783年诞辰300周年。瑞士政府、中国科学院及中国教育部于4月23日下午在北京的中国科学院文献情报中心共同举办纪念活动回顾欧拉的生平、工作及对现代生活的影响。瑞士教育与研究国务秘书瑞士教育与研究国务秘书CharlesKleiberCharlesKleiber在开幕致词中说在开幕致词中说“今天我们在这里纪念近代历史上最伟大的学者之一。没有欧拉的众多科学发现今天的我们将过着完全不一样的生活。”1.1.1图的概念2赋权图与子图3图的矩阵表示4图的顶点度5路和连通1图的概念1图的概念定义一个图G是指一个二元组VGEG其中:其中元素称为图G的顶点.组成的集合即称为边集其中元素称为边.jivv定义图G的阶是指图的顶点数VG用来表示v图的边的数目EG用来表示.也用来表示边jivv.jivv21vvvGV是非空有限集称为顶点集12EG是顶点集VG中的无序或有序的元素偶对.EVGGEGVG表示图简记用定义若一个图的顶点集和边集都是有限集则称其为有限图.只有一个顶点的图称为平凡图其他的所有图都称为非平凡图.例设GEGVG其中4321vvvvGV21eeGE6543eeee111vve322vve313vve414vve435vve436vve.见图2定义若图G中的边均为有序偶对称G为有向图jivv边为无向边称e连接和顶点和称称边为有向边或弧称jivve是从jivveiv连接jv称为e的尾称为e的头.ivjv若图G中的边均为无序偶对称G为无向图.称jivv为e的端点.jivveivjvivjv既有无向边又有有向边的图称为混合图.例设HEHVH其中54321uuuuuHV21aaHE76543aaaaa211uua222uua243uua544uua345uua436uua317uua.见右图3常用术语1边和它的两端点称为互相关联.2与同一条边关联的两个端点称为相邻的顶点与同一个顶点点关联的两条边称为相邻的边.3端点重合为一点的边称为环端点不相同的边称为连杆.4若一对顶点之间有两条以上的边联结则这些边称为重边含有重边的图称为多重图.5既没有环也没有重边的图称为简单图6任意两顶点都相邻的简单图称为完全图.记为Kv.8若且X中任意两顶点不YXGVYX相邻Y中任意两顶点不相邻则称为二部图或偶图若X中每一顶点皆与Y中一切顶点相邻称为完全二部图或完全偶图记为mXnYnmK9图叫做星.nK1:X1x2x3x:Y1y2y3y4y二部图6K:X1x2x3x:Y1y2y3y4y41K43K7一个有向图的基图是完全图称为竞赛图.2赋权图与子图2赋权图与子图定义若图的每一条边e都赋以GEGVG一个实数we称we为边e的权G连同边上的权称为赋权图.定义设和是两个图.EVGEVG1若称是的一个子图记EEVVGG.GG2若则称是的生成子图.VVEEGG3若且以为顶点集以两端点VVVV均在中的边的全体为边集的图的子图称VG为的由导出的子图记为.GVVG4若且以为边集以的端点EEEEE集为顶点集的图的子图称为的由导出的GGE子图