`
Coco_young
  • 浏览: 125898 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

吴文虎-图论学习日志——第一章

 
阅读更多

这一章主要介绍了一些图的基本概念:


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版

    《图论的算法与程序设计》(作者)吴文虎 清华大学 1997年3月第1版

    程序设计基础习题解答与上机指导-吴文虎第2版.pdf

    本书是和吴文虎编著的枟程序设计基础(第 2 版)枠(清华大学出版社 2004 年出版)配合使用的参考 书 。 内容包括 2部分 :第 1部分包括了枟程序设计基础(第 2 版)枠书中全部习题和参考解答 ;第 2 部分 ...

    黑书-吴文虎.zip

    《黑书-吴文虎.zip》是一部聚焦于实用算法分析和程序设计的资源包,它由吴文虎编著,提供了丰富的编程实践知识。在这个压缩包中,包含了一个名为“实用算法的分析与程序设计”的文件,这很可能是一个文档或者电子书...

    程序设计基础第二版 吴文虎

    《程序设计基础第二版》由吴文虎撰写,是一本以C/C++语言为背景,讲解编程思维和方法的教科书。书中涵盖了计算机语言、数据结构和常见算法等多个核心主题,旨在帮助读者掌握编程的基本技能,培养逻辑思维和实践能力...

    图论经典书籍(acm)

    学习acm必备 吴文虎 王建德的图论必备书籍

    清华大学 导师吴文虎简介

    吴文虎教授的主要研究方向之一是非平稳噪声环境下的语音检测技术。这项研究对于提高自动语音识别系统的性能至关重要,尤其是在存在各种背景噪声的情况下。其研究成果发表在《计算机科学与技术杂志》(Journal of ...

    清华大学吴文虎C++课件

    吴文虎教授以其深入浅出的教学风格,使得这套课件不仅在清华大学内部广受欢迎,也对全国乃至全球的C++学习者提供了宝贵的教育资源。 C++是现代计算机科学中不可或缺的一部分,是一种静态类型的、编译式的、通用的、...

    计算机语言与程序设计基础(清华教材)讲师-吴文虎

    《计算机语言与程序设计基础》...通过吴文虎讲师的《计算机语言与程序设计基础》课程,学生不仅可以掌握编程语言的基本语法,还能培养逻辑思维能力,学习如何有效地解决问题,并为后续的计算机科学学习打下坚实的基础。

    吴文虎课件 程序设计基础

    【程序设计基础】是计算机科学领域中的核心课程之一,它为初学者提供了构建软件和解决实际问题的基础。吴文虎教授的C++课件正是针对这个...通过吴文虎教授的课件,初学者可以期待一个既有趣又富有挑战性的学习过程。

    ACM黑书-实用算法的分析与程序设计-吴文虎、王建德.part2

    ACM黑书-实用算法的分析与程序设计_s10205419-吴文虎、王建德.part1,压缩成了两卷,完整版,含完整书签和辅助页(版权页、前言页、目录页、附录页、插页)...

    c语言课件(吴文虎)

    这个是吴文虎的C语言课件PPT,现在只上传了一章。

    实用算法的分析与程序设计(吴文虎 王建德).rar

    《实用算法的分析与程序设计》是由吴文虎和王建德两位知名计算机科学家共同编著的一本经典教材。这本书深入浅出地介绍了算法的设计、分析及其在程序设计中的应用,是ACM竞赛和计算机科学学习者的宝贵资源。以下是...

    清华大学 吴文虎

    吴文虎教授是清华大学的一位教育专家,他的教学观念深受多元智能理论的影响。他强调课堂教学是实施素质教育的核心途径,教师应当珍惜每一分课堂时间,高效地完成教学任务。他认为,教师的首要任务是树立正确的教学...

    ACM黑书-实用算法的分析与程序设计-吴文虎、王建德.part1

    ACM黑书-实用算法的分析与程序设计_s10205419-吴文虎、王建德.part1,压缩成了两卷,完整版,含完整书签和辅助页(版权页、前言页、目录页、附录页、插页)...

    计算机网络(第五版)吴文虎编著课后习题答案

    《计算机网络》第五版吴文虎编著的课后习题答案涵盖了计算机网络的基础知识,对学习者提供了宝贵的参考资料。本章主要讨论了计算机网络的基本概念、交换技术以及因特网的发展历程和标准制定。 首先,计算机网络的...

    清华大学吴文虎教授《程序设计》第一部分ppt

    清华大学吴文虎教授团队制作的《程序设计》课程教案!

    C++程序设计课件(清华大学教授 吴文虎教授)

    C++程序设计是一门深入计算机科学基础的重要课程,由清华大学教授吴文虎主讲的这门课件,为学习者提供了宝贵的教育资源。吴文虎教授在C++领域有着丰富的教学和实践经验,他的讲解深入浅出,深受学生喜爱。这份课件...

    吴文虎程序设计基础 课件 (c++)

    《吴文虎程序设计基础 课件》是针对C++编程语言的一套全面且优秀的教学资源,由知名教育专家吴文虎教授倾力打造。这套课件深入浅出地介绍了程序设计的基础概念,旨在帮助初学者掌握C++的核心知识,为后续的软件开发...

    吴文虎程序设计基础 ppt

    《程序设计基础》 吴文虎 清华大学出版社 此版本是讲义ppt

Global site tag (gtag.js) - Google Analytics