点割集和边割集的理解

这篇具有很好参考价值的文章主要介绍了点割集和边割集的理解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

边割集,离散数学,图论

点割集

其实就是一个点如果从图中去除后,该图的连通分量增加就是该图的割点,但是我们需要注意一个地方,看上面的图,v5是一个割点,它可以将图分割开,然后使得图的连通分量增加,而{v2,v5}似乎也可以做到将图的连通分量增加,但是需要注意的地方是v5就可以做的事情其实就不需要{v2,v5}去做,这样多出来一个点去做图的分割的操作其实并不是我们要的。那么其实我们就可以得到点割集的定义:

点割集的定义:

点割集是原生图的结点,同时当我们将结点从图中删去后会使得图的连通分量增加,并且该结点是最小的的分割集合,也就是说不应该存在某个同样可以使得图的连通分量增加的分割集合是该分割集合的真子集。

边割集

边割集的定义:

边割集其实和点割集差不多,同样的,某个原生边中的边子集从图中删去后,使得图的连通分量增加,同时不存在任何可以增加图连通分量的分割集合是该分割集合的真子集。 

边割集,离散数学,图论

如上图所示,因为e9去除后已经可以使得图的连通分量增加了,所以{e6,e7,e9}就不能作为一个边割集,其实可以这么想当出现仅有一个元素的边割集,那么任何包含该集合的边的集合(除了自己)都不能视为是一个边割集。再比如上图中的{e1,e2}是一个边割集,那么{e1,e2,e5}就不能作为是一个边割集文章来源地址https://www.toymoban.com/news/detail-517685.html

到了这里,关于点割集和边割集的理解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 离散数学 图论

    1、V,E是一个图 2、零图:图的边集E为空集 3、平凡图: 只有一个结点 的零图 4、平行边: 5、多重图:有平行边的图 6、简单无向图:一个无向图( 没有平行边 )( 没有自回路 ) 7、简单有向图:一个有向图( 没有平行边 )( 没有自回路 ) 8、简单图:( 没有平行边 )( 没有自回路 )的

    2024年02月08日
    浏览(34)
  • 【离散数学】图论

    目录 ​ 无向图与有向图 定义 特殊的图 顶点与边的关联与相邻 无向图和有向图的度数 握手定理 度数列 可图化 最大度和最小度 多重图与简单图 无向完全图与有向完全图  子图与补图 子图 ​ 生成子图​  补图 通路与回路 定义 图的连通性 连通图 可达 几种连通 图的矩阵

    2024年02月13日
    浏览(38)
  • 【离散数学】测试五 图论

    目录 图论  系列文章 1. n层正则m叉树一共有()片树叶。 A. nm B. mn C. mn 正确答案: B 2. 下图是一棵最优二叉树 A. 对 B. 错 正确答案: B 3. 要构造权为1,4,9,16,25,36,49,64,81,100一棵最优二叉树,则必须先构造权为5,9,16,25,36,49,64,81,100一棵最优二叉树

    2024年02月09日
    浏览(36)
  • 离散数学-图论-树(13)

    定义1: 连通无回路的无向图称为无向树,简称树.每个连通分支都是树的无向图称为森林.平凡图称为平凡树.在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支点. 定义2 设G=V,E是n阶m条边的无向图,则下面各命题是等价的: (1)G是树 (2)G中任意两个顶点之间存在惟一的

    2024年02月03日
    浏览(42)
  • 离散数学——图论部分

    目录 概述考点: 邻接矩阵,矩阵的计算及含义,完全图,补图,平面图的相关概念,欧拉图,最小生成树,最优二叉树 一.图 ​编辑   二.路和回路 2.1 2.2连通与可达 1.可达 2.连通 三.图的矩阵表示 3.1邻接矩阵 3.2可达性矩阵 3.3无向图的完全关联矩阵 3.4有向图的完全关联矩阵

    2024年02月04日
    浏览(37)
  • 离散数学 | 图论 五色定理证明

    看来一下午终于看懂了,甚至差点睡过去…… 趁热打铁记录一下自己的理解。 任意一个简单的连通平面图 点着色 至多 五色 。 一、 设 G 为一个至少有三个结点的连通平面图,则 G 中必有一个结点 u,u 的度数 deg(u)≤5。 Step1:证明简单连通平面图 G 中一定存在一个顶点,其

    2024年02月01日
    浏览(31)
  • 头歌实训-离散数学-图论!

    5阶无向完全图的边数为:10 设图 G 有 n 个结点, m 条边,且 G 中每个结点的度数不是 k ,就是 k+1 ,则 G 中度数为 k 的节点数是: n(k+1)-2m 若一个图有5个顶点,8条边,则该图所有顶点的度数和为多少?16 他让输出关联矩阵和邻接矩阵这不简单么? 我是直接摆烂了 输出个球呀

    2024年02月04日
    浏览(69)
  • 离散数学之图论复习笔记

    图的定义 一个图 G 是一个序偶〈 V ( G ), E ( G )〉,记为 G =〈 V ( G ), E ( G )〉。其中 V ( G )是非空结点集合, E ( G )是边集合,对 E ( G )中的每条边,有 V ( G )中的结点的有序偶或无序偶与之对应。 图G的结点与边之间的关系 邻接点 :同一条边的两个端点。 孤立点 :没有边与之关

    2024年02月08日
    浏览(36)
  • 离散数学期末复习(4):图论(Graphs)

    目录 10.1 Graphs and Graph Models (图和图模型) 10.2 Graph Terminology and Special Types of Graphs (图的术语和几种特殊图) 1.基础概念 2. 度(degree) (1)无向图中一个顶点v的度是这个点相关的边的数量,写作deg(v) (2)握手定理  (3)出度和入度  3.图的分类 (1)圈图(Cycles)  (2)轮图

    2024年02月03日
    浏览(35)
  • 离散数学-图论-图的基本概念(11)

    1.1 图的定义 定义1: 一个 无向图 G是一个有序的二元组V,E,其中 (1)V是一个非空有穷集,称为顶点集,其元素称为顶点或结点。 (2)E是无序积VV的有穷多重子集,称为边集,其元素称为无向边,简称边。 定义2: 一个 有向图 D是一个有序的二元组V,E,其中 (1)V是一个非

    2024年02月13日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包