离散数学 --- 图论基础 --- 图的同构,通路与回路,可达性与最短通路

这篇具有很好参考价值的文章主要介绍了离散数学 --- 图论基础 --- 图的同构,通路与回路,可达性与最短通路。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

离散数学同构,离散数学,图论

同一个图(这里的图是抽象的数学定义)可以有不同的图形表示方法离散数学同构,离散数学,图论

1.重数:两点之间的平行边的个数离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

1.得到 n! 的过程,一个图中的一个结点在另一个图中对应的结点有n种可能(黄框中定义的图来讨论),这个对应好后下一个结点有 n - 1 种可能,再下一个有n-2种,直到最后一个为1,所有可能的结果就等于 n * (n - 1) *(n - 2)*....*1 = n! 

2.虽然说找对应结点很困难,但不是没有规律可循的。比如1.两个相互对应的结点的度数要相同;2.两个相互对应的结点的邻接点的度数也要相同(和结点A具有边关系的结点都是结点AA的邻接点)离散数学同构,离散数学,图论

1.如果两个图之间不满足上面这三个条件中的任意一个,则这两个图不同构,但是即使满足了这三个条件也不一定同构离散数学同构,离散数学,图论


第二部分 --- 通路与回路

离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

 确定了边之后自然就能跟确定边两端的端点了离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

1.注意这里的A的m次幂表示的是通过矩阵乘法一步步乘过来的新矩阵,然后(aij(m))表示的是计算完A的m次幂后得到的新矩阵的第 i 行 j 列的元素

离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

 上面那个是无向图,下面这个是有向图离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

1.(bij)n*n表示的是矩阵Bm的第 i 行 j 列的元素

2.矩阵之间的加法只有在两个矩阵的行数和列数都相同的时候才能够进行,然后相加的方式是对应元素相加后得到新矩阵对应位置的元素值


第三部分 --- 可达性

在实际情况中,我们往往不关系两点之间有多少通路,我们一般只关心两点:

1.两点之间有没有通路? --- 可达性

2.两点之间如果有通路的话,最短通路是那条?--- 最短通路                  离散数学同构,离散数学,图论

1.上面这种穷举法只是举个例子,实际上我们判断是否可达采用的是下面这个原理离散数学同构,离散数学,图论

1.如果从长度1到长度为 n-1(n为结点数)都找不到一条通路的话,则这两点之间是不可达,如果找到了,那这两点之间就是可达的

2.根据下面的证明我们可以得知,两点之间任意一条长度大于 n - 1 的通路(如果存在的话)都等价于一条长度小于等于 n - 1 的通路

(由结点数限制可证:长度为K,代表你有K条边,这就有K+1个结点,如果K+1个结点大于n个结点(总结点数),则证明这条通路上必定会出现重复的结点,此时的通路等价于将重复的结点之间的路径省掉的新通路,这样不停的省下去,最终一定能使得K小于等于n-1)

所以可知如果我们没有在 长度 <= n-1的范围内找到通路的话,则就再也找不到了离散数学同构,离散数学,图论

回路的判断同理

(不过有一个区别,就是回路的边数等于回路的结点数,通路的边数等于通路的结点数 减 1)离散数学同构,离散数学,图论

离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

1.对于无向图而言,i 结点能够到达 j 结点,则j结点一定能够到达 i 结点,反应到可达性矩阵就是:

Pij = Pji

2.对于有向图则不是如此,如果 i 结点能作为始点,j 结点能作为终点形成通路,并不意味着 j 结点作为始点 ,i 结点作为终点能够形成通路:

反应到可达性矩阵就是: Pij 不一定等于 Pji离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

 由于可达性矩阵只需要知道通还是不通,所以我们可以对可达性矩阵的求解进行简化:

1.将原本的A的1次幂到A的n次幂的矩阵乘法计算转变为矩阵的布尔乘法(n为结点数)计算

2.将得到的次幂从1到n的布尔矩阵取并集,取完并集后得到的新的矩阵就是我们的可达性矩阵

原本的计算方法:

1.计算矩阵A从1次幂到n次幂(n为结点数)的矩阵

2.将得到的所有矩阵求和得到新矩阵B

3.如果B矩阵的 Bij 元素不等于0,则可达性矩阵中对应位置的元素的值为1,如果等于0,则对应位置的元素也为0


第四部分 --- 最短通路

1.上面的最后一点为什么有向图不行呢? --- 这是因为定义中只给定了 从 i 到 j 结点是通路,并没有说从 j 到 i 结点是不是通路(对于无向图而言是的),既然连 j 到 i 结点是不是通路都不知道,自然也就没有对应的短程线了,连短程线都没有的话哪来的相等性质呢

2.规定任何的结点自身到自身的距离为0

离散数学同构,离散数学,图论

 离散数学同构,离散数学,图论

 文章来源地址https://www.toymoban.com/news/detail-822184.html

到了这里,关于离散数学 --- 图论基础 --- 图的同构,通路与回路,可达性与最短通路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 离散数学:图的基本概念

    本帖子讨论图的基本概念,这一章,我们将利用有序对和二元关系的概念定义图。图分为了无向图和有向图,他们有共性也有区别,请大家注意体会,用联系和辩证的观点去认识。 注意无向图和有向图的表示,最大区别在于边的集合的表示,无向图中边集为无序集VV的子集,

    2024年02月09日
    浏览(53)
  • 离散数学·图的着色

    k -着色 —— 用k个颜色上色的 色数 —— 最少需要的颜色数 k -色图 —— 最少需要的色 的图 χ(……) —— 相应 色数 χ(G) 点色数 =1 —— 为零图 全是孤立点 χ(K n )=n χ(G)=2 —— G为非零图二部图 二部图:一个图的点集可以分为2个互不相交的点集A,B的并,并且在G中的每一条边

    2024年02月12日
    浏览(35)
  • 离散数学 第十章 图的基本概念

    目录 10.1 图的基本概念 10.2 道路与回路 10.3 图的连通性 10.4 图的矩阵表示 ①什么是图:一个序偶(V,E),记作G=(V,E)                          V(G)={v1,v2,...,vn} 结点集,n为G的阶                         E(G)={e1,e2,...,em} 边集,m为G的边数 ②图的分类: 1.无向图

    2024年02月07日
    浏览(46)
  • [离散数学]图论

    点相同 边相同 $$ 必要条件 节点数相同 边相同 度数相同节点数目相同 m = C n 2 = 5 ∗ 4 / 2 = 10 m=C_n^2=5*4/2=10 m = C n 2 ​ = 5 ∗ 4/2 = 10 n = 5 n=5 n = 5 由推论 m ≤ 3 n − 6 le3n-6 ≤ 3 n − 6 得 m ≤ 9 le9 ≤ 9 相互矛盾 ∑ d e g ( v i ) = 2 e = 2 V − 2 sum deg(v_i)=2e =2V -2 ∑ d e g ( v i ​ ) = 2 e =

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

    目录 图论  系列文章 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日
    浏览(40)
  • 离散数学-图论-树(13)

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

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

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

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

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

    2024年02月13日
    浏览(41)
  • 离散数学——图论

    图的定义 现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。 例子:a,b,c,d 4个篮球队进行友谊比赛。为了表示4个队之间比赛的情况,我们作出图7.1.1的图形。在图中4个小圆圈分别表示这4个篮球队,称之为 结点 。如果两队

    2024年02月02日
    浏览(191)
  • 离散数学 图论

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

    2024年02月08日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包