这一章主要介绍了一些图的基本概念:
1.顶点,边:图中的点就是顶点,连接顶点的线就是边。
2.孤立点:没有任何边与之相连的顶点。
3.图同构:给定两个图G1,G2,对于G1中的边(U1,V1)在G2中总能找到(U2,V2)与之相对应,且所有的边是一一对应的,那么这两个图是同构的
4.自环:边(V,V)叫做自环
5.简单图:不含自环的图叫做简单图
6.二分图:把图中的顶点分成两个集合Set1,Set2,任意一条边(U,V)有U在Set1中,V在set2中,那么该图叫做二分图。
7.完全图:对于任意两个顶点都有直接边相连的图,叫做完全图。
8.补图:把与G相同阶数的完全图边集中包含G中的边的子集去掉,那么得到的图就是G的补图
9.顶点的度:边与该顶点关联的次数。(无向图)
10.度有关定理:图的度数和为偶数,奇数度的顶点一定是偶数个。
11.道路:边序列,(e1,e2,e3,e4,e5,......,en)叫做一条道路,其中ei的终点为ei+1的起点,
12.回路:en的终点等于e1的起点的道路叫做回路.
13.欧拉回路:从一个顶点出发,走完图里的所有边,回到起点,经过的回路叫做欧拉回路。
14.内点:道路中除端点以外的点。
15.轨道:没有经过同一个顶点超过1次的道路。
16.圈:起点和终点相同的轨道。
17.K阶圈:K条边构成的圈。
18.连通图:任意两个顶点都有道路相连。
19.几个结论:
(1)若图有2K个奇点,那么图G最少能用K笔画成。
(2)如果图G有2个奇点,和K个相互没有公共顶点的连通子图,那么图G可以分解成K-1条回路和1条道路。
(3)G为二分图的充要条件时G中无奇点。(貌似不对)
20.树:有n-1条边的n阶连通图。
21.平凡树:孤立点
22.树的性质:
(1)去掉任意1边,图不连通
(2)添加任意1边,图中出现圈。
(3)任意两顶点之间有且只有一条道路。
23.一个结论:
Kn完全图可以产生N^n-2个不同的树.
分享到:
相关推荐
《图论的算法与程序设计》(作者)吴文虎 清华大学 1997年3月第1版
本书是和吴文虎编著的枟程序设计基础(第 2 版)枠(清华大学出版社 2004 年出版)配合使用的参考 书 。 内容包括 2部分 :第 1部分包括了枟程序设计基础(第 2 版)枠书中全部习题和参考解答 ;第 2 部分 ...
学习acm必备 吴文虎 王建德的图论必备书籍
ACM黑书-实用算法的分析与程序设计_s10205419-吴文虎、王建德.part1,压缩成了两卷,完整版,含完整书签和辅助页(版权页、前言页、目录页、附录页、插页)...
清华大学吴文虎老师的c++教学课件 深入浅出 感觉非常实用 希望对学习软件的同学有帮助
这个是吴文虎的C语言课件PPT,现在只上传了一章。
吴文虎个人简介 讲解个人的思想 以及个人的算法
程序设计基础(第二版) 吴文虎ppt第一讲
ACM黑书-实用算法的分析与程序设计_s10205419-吴文虎、王建德.part1,压缩成了两卷,完整版,含完整书签和辅助页(版权页、前言页、目录页、附录页、插页)...
吴文虎的C++课件 通俗易懂 易理解 适合初学者用
计算机网络(第五版)吴文虎编著课后习题答案,内容很详细,很全面,对学习计算机网络的同学很有帮助。
清华大学 吴文虎清华大学 吴文虎 怎样上课
清华大学吴文虎教授团队制作的《程序设计》课程教案!
实用的算法分析和程序设计,比较实用的东西
《程序设计基础》 吴文虎 清华大学出版社 此版本是讲义ppt
实用算法的分析与程序设计(吴文虎 王建德).rar
看这个,跟在清华学编程一样。 清华大学计算机科学与技术专业。
本书重点讲授在C/C++语言环境下,编写程序的思路和方法,涉及计算机语言、数据结构和常用算法等内容。全书内容丰富,强调动手实践,深入浅出地引导读者理性思维和理性实践,教学方法引入人胜,便于自学。...
这是清华大学教授吴文虎的关于C++程序设计的课件,是学习C++的好资料,对于程序员的编程风格以及已经注意的事项,讲的很详细。
相当全面 优秀的一套c++课件 吴文虎程序设计基础 课件