首页 > 其他分享 >图的基本概念和术语

图的基本概念和术语

时间:2022-12-10 16:59:37浏览次数:42  
标签:术语 vi vj 子图 连通 该子 顶点 基本概念

图的定义和术语

  • 图:G = (V, E)

    V:顶点(数据元素)的有穷非空集合;

    E:边的有穷集合

  • 无向图:每条边都是无方向的;

    无向图

  • 有向图:每条边都是有方向的;

    有向图

  • **完全图:任意两点都有一条边相连;

    完全图

  • 稀疏图:有很少边或弧的图(e < n log n)。

  • 稠密图:有较多边或弧的图。

  • 网:边/弧带权的图。

  • 邻接:有边/弧相连的两个顶点之间的关系。

    ​ 存在(vi, vj),则称 vi 和 vj 互为邻接点

    ​ 存在<vi, vj>,则称vi 邻接到 vj ,vj 邻接于 vi

  • 关联(依附):边/弧与顶点之间的关系。

    ​ 存在(vi, vj) / <vi, vj>,则称该边/弧关联于 vi 和 vj

  • 顶点的度:与该顶点相关联的边的数目,记为TD(v)。

    有向图中,顶点的度等于该顶点的入度出度 之和。

    顶点v的入度是以v为终点的有向边的条数,记作 ID(v)

    顶点v的出度是以v为始点的有向边的条数,记作 OD(v)

    顶点的度

  • 路径:接续的边构成的顶点序列。

  • 路径长度:路径上边或弧的数目/权值之和。

  • 回路(环):第一个顶点和最后一个顶点下个相同的路径。

  • 简单回路:除路径起点和终点可以相同外,其余顶点均不相同的路径。

  • 简单回路(简单环):除路径起点和终点A相同外,其余顶点均不相同的路径。

    1

  • 连通图(强连通图):

    在无(有)向图 G = ( V, { E } )中,若对任何两个顶点 v、u 都存在从 v 到 u 的路径,则称 G 是连通图(强连通图)

    强连通图的每个结点必然是有出度和入度的,没有肯定不强连通

    连通图(强连通图)

  • 子图:

    设有两个图 G = ( V, { E })、G1 = ( V1, { E1 }),若 V1 包含于 V,E1 包含于 E,则称 G1 是 G 的子图。

    子图

  • 连通分量(强连通分量):

    • 无向图 G 的 极大连通子图称为 G 的连通分量

      极大连通子图的意思是:该子图是 G 连通子图,将 G 的任何不在该子图的顶点加入,子图不再连通。

      连通分量

    • 有向图 G 的 极大强连通子图称为 G 的强连通分量

      极大强连通子图的意思是:该子图是 G 强连通子图,将 G 的任何不在该子图的顶点加入,子图不再是强连通。

      强连通分量

  • 极小连通子图:该子图是 G 的连通子图,在该子图中删除任何一条边,该子图不再联通。

  • 生成树:包含无向图G所有顶点的极小连通子图。

    生成树

  • 生成森林:对非联通图,由各个连通分量的生成树的集合。

标签:术语,vi,vj,子图,连通,该子,顶点,基本概念
From: https://www.cnblogs.com/zh-Note/p/16953998.html

相关文章

  • 卡尔曼滤波之基本概念和状态观测器
    OverridetheentrypointofanimageIntroducedinGitLabandGitLabRunner9.4.Readmoreaboutthe extendedconfigurationoptions.Beforeexplainingtheav......
  • 性能测试中常见的专业术语:QPS、TPS、并发数、响应时间(RT)、吞吐率和吞吐量【杭州多测师
    一、QPS: 每秒钟处理完请求的次数,注意这里是处理完,单接口看做是一个事务的话,1TPS=1QPS二、TPS:每秒钟处理完的事务次数,一般TPS是对整个系统来讲的。一个应用系统1s能完成多......
  • 【每天一个java设计模式(零)】 - 设计模式基本概念及七大设计原则
    设计模式概述设计模式是什么?它是软件开发人员在软件开发过程中经过相当长的一段时间的试验和错误总结出来的面临的一般问题的解决方案;它是一套被反复使用的、多数人知晓的、......
  • HTTP 基本概念
    一、HTTP是什么?HTTP是超文本传输协议,也就是HyperText Transfer Protocol。(一)能否详细解释「超文本传输协议」?HTTP的名字「超文本协议传输」,它可以拆成三个部分:超......
  • java并发编程(二十二)-并发安全的基本概念
    类的线程安全定义  如果多线程下使用这个类,不过多线程如何使用和调度这个类,这个类总是表示出正确的行为,这个类就是线程安全的。类的线程安全表现为:操作的原子性内存的可见......
  • java并发编程(一)-线程相关的基本概念
    CPU核心数和线程数的关系核心数:线程数=1:1intel引入超线程技术之后--》核心数:线程数=1:2CPU时间片轮转机制-又称RR调度 时间片轮转法(Round-Robin,RR)主要用于分时系统......
  • Kafka基本概念大全
    下面给出Kafka一些重要概念,让大家对Kafka有个整体的认识和感知,后面还会详细的解析每一个概念的作用以及更深入的原理•Producer:消息生产者,向KafkaBroker发消息的......
  • Kafka基本概念大全
    下面给出Kafka一些重要概念,让大家对Kafka有个整体的认识和感知,后面还会详细的解析每一个概念的作用以及更深入的原理•Producer:消息生产者,向KafkaBroker发消息的......
  • HashSet、LinkedHashSet基本概念和使用
    java.util.Set接口和java.util.List接口一样,同样继承自Collection接口,它与Collection接口中的方法基本一致,并没有对Collection接口进行功能上的扩充,只是比Collection接口更......
  • rabbitMQ--基本概念
    MQ的概念优点:1.应用解耦,提升系统容错性和可维护性 图中,假如不加入MQ,如果库存系统宕机,则会导致订单系统宕机,从而导致整个分布式宕机。 2.异步提速,提高系统的吞吐......