课程分类

课程介绍
课程目录
用户评论
课程介绍
课程目录
用户评论

你将获得

  • 掌握某些知识点
  • 学会某些技巧(或思路)

教学服务

  • icon

    1v1专属答疑服务

  • icon

    BAT专家面试辅导

讲师介绍

  • 大学老教授,从事科研教学工作  参加过国家自然科学基金项目 擅长解决数学物理方面的难题 重视基础教学工作 能够从本质上上剖解问题

  • 南京大学老师  从事教育工作 对教学很有研究 擅长生物医学方面的教育

  • 课程详情

    基本知识点: 
    一、图的基本定义: 
    平凡图:只有一个顶点无边的图。            非平凡图:其他所有图。 空图:边集合为空的图。 
    简单图:既没有环也没有重边的图。            复合图:其他所有的图。 同构图:顶点集合之间存在双射(一一对应关系),对应边重数和端点对应相等。 
    标定图:给图的点和边标上符号。           非标定图:不标号。非标定图代表一类相互同构的图。 
    完全图:每两个不同顶点之间都有一条边相连的简单图。N个顶点的完全图只有一个,记为
    nK。 
    偶图(二部图):具有二分类(,)XY的图,他的点集可以分解为两个(非空)子集X和Y,使得每条边的一个端点在X中,另一个端点在Y中。 
    完全偶图 :指具有二分类(,)XY的简单偶图,其中X的每个顶点与Y的每个顶点相连。若
    ,XmYn,则这样额完全偶图记为:,mnK。 
    k—正则图:设(,)GVE为简单图,如果对所有的结点vV,有()dvk,称G为k—正则图。 完全图和完全偶图,nnK 均是正则图。 
    图划分:若一个n阶简单图G各点的度为id,则分正整数k为n个部分的划分id称为是图划分。 子图:边集合和点集合均是原图的子集,且待判定图中的边的重数不超过原图中对应的边的重数。 
    生成子图:点集合相等,边集合为原图子集的图。 
    导出子图:由顶点集为原图G真子集的所有点,及两端点均在该集合中的边的全体组成的
    子图V‘
    。 
    '
    []GV 和Gv。 
     
    边导出子图:由原图G边的真子集,该图中边的断点全体为顶点组成的子图E‘
    。 
    '
    []GE 和{}Ge。 
    图的运算: 
    并,交,差,对称差,联图,积图,合成图,极图  
    路与图的联通性: 途径: 
    迹:边互不相同的途径。 
    路:边和点都互不相同的途径。 连通的:两个顶点之间存在路。 
    连通图:每一对顶点之间都有一条路。 


    连通分支:将V划分为一些等价类12,,...kVVV。两个顶点u和v是连通的当且仅当他们属于同一个子集iV,称子图()iGV为连通分支。 
    闭的:一条途径如果有正的长,且起点和终点相同。 回路:闭途径。 
    圈:起点和内部顶点互不相同的闭迹。k圈、奇圈、偶圈 
    直径:联结u和v中长度最短的途径的长度称为u与v的距离。记为(,)duv。
    ()max{(,)|,}dGduvuvV为图G的直径。 
     
    赋权图:对图的每条边e赋以一个实数()e称为权。G连同它边上的权称为赋权图。  
    邻接矩阵:表示点与点之间的关系。nn  n为点数,m为边数。 关联矩阵:表示点与边之间的关系。nm  
    树的等价命题:            1.连通无圈图。 
                              2.任意两顶点之间有且仅有一条路相连。                           3.G是连通的,且1mn。                           4.G中无圈,且1mn。                           5.G中无圈,任意两顶点之间增加一条边就得到唯一的一个圈。 非平凡无向图G是树的充要条件是G为最小连通图。          非平凡无向图G是树的充要条件是当且仅当他的每条边均为割边。
    温馨提示
    • 请勿私下交易
      请勿在平台外交易。与机构和老师私下交易造成的任何损失及纠纷,腾讯课堂不承担任何责任
    • 听课说明

      1、电脑:访问腾讯课堂官网 ke.qq.com 查看我的课表或下载win/mac客户端听课

      2、手机/平板:下载腾讯课堂APP, 进入学习页面听课