• 离散数学·图的矩阵表示、平面图

    有向图关联矩阵

    在这里插入图片描述

    无环，有向（可以表示平行边）
    M(D)【direction】

    在这里插入图片描述

    每一列的和都是0，每一行中所有元素的绝对值是点的度数

    性质

    在这里插入图片描述

    1. 所有列相加一定是0（每一列都是0）
    2. 第i行第j列是1的情况的和是出度数
    3. 同1
    4. 平行边的表示就是再加一条一样的列

    无向图关联矩阵

    在这里插入图片描述

    无向，无环
    M(G)

    在这里插入图片描述

    性质

    在这里插入图片描述

    看一下（3）吧🎱🎱🎱

    基本关联矩阵

    在这里插入图片描述

    简而言之——原矩阵删掉了一行就是基本关联矩阵
    删掉的那一行应该是 1 最多的

    无向图关联矩阵和基本关联矩阵的秩

    矩阵的秩：化简之后的非零行的行数
    在这里插入图片描述

    基本关联矩阵和生成树

    在这里插入图片描述

    例

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2，3，4指代的是e2，e3，e4的导出子图

    有向图的邻接矩阵

    在这里插入图片描述

    即为 相邻（点与点是连通的）

    性质

    在这里插入图片描述

    邻接矩阵和通路数

    在这里插入图片描述
    回路看对角线
    A2中的a12表示从v1到v2长度为2的通路的数量2023.2.13复习
    r表示长度
    Ar矩阵表示的是长度为r的通路
    Br相当于是A1+A2+……+An，所以Br表示的是通路长度≤r的通路

    可达矩阵

    在这里插入图片描述

    就是2个点是连通的，矩阵相应位置就为1（注意是在有向图）
    可达 —— 有向

    性质

    在这里插入图片描述

    默认对角线元素全为1

    无向图的相邻矩阵

    在这里插入图片描述

    性质

    在这里插入图片描述

    连通矩阵

    在这里插入图片描述
    连通 —— 无向
    不难看出，有向图的邻接矩阵、可达矩阵和无向图的相邻矩阵、连通矩阵是有很多相似的

    平面图

    在这里插入图片描述
    边与边不在非顶点处相交 —— K4是可平面图，K5不是

    K4平面图
    在这里插入图片描述

    例

    在这里插入图片描述
    不难看出，对于K5或者K3,3来说，在画图的时候，会发现，存在至少一个点是被周围的边包围起来的（这一页中紫色线指向的点靠近与其他边相交的地方，都是被周围的边无死角地包围起来了）

    面和次

    在这里插入图片描述

    面的次数——边界的条数

    例

    在这里插入图片描述

    悬挂边的次数是2——（那FE举例，内部区域为FECD）相当于从起点走到终点，F–E–C–D–E–F，通过这个轨迹可以看出FE这条边走了2次

    定理

    在这里插入图片描述

    类似握手定理，没什么好说的

    极大平面图

    在这里插入图片描述

    只用知道一下：极大平面图是连通的，每个区域的次数都为3
    n≥3时，没有割点和桥2023.2.13复习

    欧拉公式

    在这里插入图片描述

    连通

    如果非连通——n-m+r=1+p
    p为连通分支数

    在这里插入图片描述
    不太需要背下来

    在这里插入图片描述
    简单平面图， l l l ≥ 32023.2.13复习
    若为简单极大平面图——m=3n-6

    Kuratowski定理

    在这里插入图片描述
    拿K5和K33到图G中找2023.2.13复习

    对偶图

    在这里插入图片描述

    这一页就图一乐🥙🥙🥙
    用例子讲会好一些

    在这里插入图片描述

    • 每个区域在对偶图中变成一个点，如果存在区域与区域间共有的边界，那2个区域间连线（每有一条相应画一条线与之相交【图中虚线处】，悬挂边或桥就自身穿出和穿入）

    性质

    在这里插入图片描述

    对偶图是连通的

    作业

    5

    在这里插入图片描述
    在这里插入图片描述

    没什么难的🥪🥪🥪
    但是，要知道定理：简单平面图，有m≤3n-6

    6

    在这里插入图片描述
    在这里插入图片描述

    虽然思维上没什么难度，但是要熟练掌握定理（特别是成立的条件）：

    • 连通平面图，有n-m+r=2
    • 简单平面图，有deg®≥3
    • 任意平面图，都有∑deg®=2m

    11 自对偶

    在这里插入图片描述
    在这里插入图片描述

    同样没什么思维难度，但是要掌握相应知识点

    自对偶：对偶图与原图同构（点、边的数量相同）
    对偶图是连通的

    12

    在这里插入图片描述
    在这里插入图片描述

    13

    在这里插入图片描述
    在这里插入图片描述

  • 相关阅读:
    堆叠式自动编码器（SAE）--学习笔记
    【学习笔记】Maven
    如何从内核漏洞造一个容器逃逸
    RFSoC应用笔记 - RF数据转换器 -07- RFSoC关键配置之RF-DAC内部解析（一）
    APP广告变现痛点，开发者如何解决？
    【C++】unordered_map和unordered_set
    四、Qt自定义UI界面（细节的使用）
    项目开发好用工具
    外汇天眼：交易的本质就是要解决这两个问题！
    lnmp架构之mysql部署
  • 原文地址：https://blog.csdn.net/qq_61786525/article/details/127421419