精华内容
下载资源
问答
  • 离散数学复习命题公式的范式 离散数学平面图对偶图和着色问题 离散数学谓词逻辑 离散数学-图的运算与基本概念、导出子图、路与连通 离散数学关系的基本运算和关系的性质闭包 离散数学-欧拉图和哈密顿图 文章目录 图...

    离散数学复习命题公式的范式

    离散数学平面图对偶图和着色问题

    离散数学谓词逻辑

    离散数学-图的运算与基本概念、导出子图、路与连通

    离散数学关系的基本运算和关系的性质闭包

    离散数学-欧拉图和哈密顿图

    图的定义与记号

    概念:
    简单图
    多重图
    完全图
    在这里插入图片描述
    在这里插入图片描述
    平凡图的定义:
    1.仅有一个结点的图的称平凡图;
    2.平凡图是平凡树;
    3.边的集合为空的图叫做零图,1阶零图叫做平凡图,所谓n阶图是指有n个顶点的图;
    4.顶点的集合为空的图叫做空图。
    零图:只有结点没有边的图。(零图可以多个结点,平凡图只有一个结点)
    平凡图是连通图、欧拉图、哈密顿图。
    由孤立点组成的图叫做零图,由一个孤立点组成的图叫做平凡图,因而平凡图一定是零图。
    全关系-恒等关系:完全图
    空关系:零图在这里插入图片描述

    邻接矩阵

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

    关联矩阵

    设G=V,E是无向图,其中V={v1,v2,…,vn},将n×m阶矩阵𝑚𝑖𝑗𝑛×𝑚称为G的关联矩阵,记为M(G)。其中元素𝑚𝑖𝑗表示结点v𝑖与边e𝑗的关联次数,如下所示
    在这里插入图片描述
    设D=V,E是有向图,其中V={v1,v2,…,vn},将n×m阶矩阵𝑚𝑖𝑗𝑛×𝑚称为D的关联矩阵,记为M(D)。其中元素𝑚𝑖𝑗表示结点v𝑖与边e𝑗的关联情况,如下所示:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    [结论]
    (1)对于无向图及其关联矩阵,由于每条非自环边关联2个结点,故矩阵中每列元素之和必为2。
    (2)对于有向图及其关联矩阵,由于每条非自环有向边关联2个结点,且一个为起点一个为终点,故图中每个非自环边在关联矩阵中所对应列元素之和必为0.

     当图模型中的边数较多时,邻接矩阵和关联矩阵比较有效。
     当图模型中的边数较少时,邻接矩阵和关联矩阵的的表示方法比较浪费资源,可用邻接表的方法表示图模型。

    邻接表

    邻接表
    ⨠⨠邻接表主要是分别对图G=V,E中每个结点𝑣𝑖建立一个单链表。
    ⨠⨠对于结点𝑣𝑖的单链表,该表的第一个存储单元为表头,存放结点𝑣𝑖的有关信息,表中其它存储单元存放与所有结点𝑣𝑖相关联边的信息
    在这里插入图片描述

    在这里插入图片描述

    图的运算和算法

    集合运算:
    假设𝐺1=𝑉1,𝐸1和𝐺2=𝑉2,𝐸2是任意给定的图模型,则有:
    (1)如果𝑉1∩𝑉2=∅,则称𝐺1和𝐺2是不交的;
    (2)如果𝐸1∩𝐸2=∅,则称𝐺1和𝐺2是边不交的,或者说是不重的。

    设G1=<V1,E1>和G2=<V2,E2>都是不含孤立结点的图(同为无向图或有向图)。
    ⨠⨠由G1和G2中所有边与结点组成的图称为G1和G2的(union),记作G1∪G2。其中V=V1 ∪ V2 , E=E1 ∪ E2。当 G1和G2不存在公共边时,称G1∪G2为G1和G2的不重并。
    ⨠⨠由G1和G2的公共边组成的图称为G1和G2的交(cap),记作G1∩G2。其中V=V1 ∩ V2 , E=E1 ∩ E2。
    仅由G1中去掉G2中的边组成的图称为G1和G2的差 (difference),
    记作G1-G2。其中V=V1, E=E1 -E2
    在G1和G2的并中去掉G1和G2的交所得到的图称为G1和G2的环和 记作在这里插入图片描述
    在这里插入图片描述

    (1) 若𝑮𝟏=𝑮𝟐,则𝑮𝟏∩𝑮𝟐=𝑮𝟏∪𝑮𝟐=𝑮𝟏(𝑮𝟐), 𝑮𝟏−𝑮𝟐=𝑮𝟐−𝑮𝟏=∅。
    (2) 𝑮𝟏与𝑮𝟐不交时,𝑮𝟏∩𝑮𝟐=∅,𝑮𝟏−𝑮𝟐=𝑮𝟏, 𝑮𝟐−𝑮𝟏=𝑮𝟐,𝑮𝟏⊕𝑮𝟐=𝑮𝟏∪𝑮𝟐。
    (3) 𝑮𝟏⊕𝑮𝟐=𝑮𝟏∪𝑮𝟐−(𝑮𝟏∩𝑮𝟐)

    在这里插入图片描述
    修改运算:

    在这里插入图片描述
    在这里插入图片描述
    例子:
    在这里插入图片描述
    在这里插入图片描述

    •图 (b)表示𝑮−(𝒗𝟐,𝒗𝟑);
    •图 ©表示𝑮−{𝒗𝟏,𝒗𝟐,𝒗𝟏,𝒗𝟕,𝒗𝟐,𝒗𝟐,(𝒗𝟐,𝒗𝟑)};
    •图 (d)表示 𝑮−𝒗𝟕;
    •图 (e)表示𝑮−{𝒗𝟏,𝒗𝟑,𝒗𝟒,𝒗𝟔};
    •图 (f)表示𝑮(𝒗𝟐,𝒗𝟕);
    •图 (g)表示𝑮∪(𝒗𝟒,𝒗𝟔);
    •图 (h)表示𝑮∪((𝒗𝟏,𝒗𝟓)。

    图的运算–子图

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

    图的度

    在这里插入图片描述

    各顶点的度均相同的图称为正则图(regular graph),各顶点度均为k的正则图称为k-正则图。
    8.2.10.对于图G = <V, E>,度数为1的结点称为悬挂结点(Hanging Point),以悬挂结点为端点的边称为悬挂边(Hanging Edge)。
    在这里插入图片描述
    用邻接矩阵表示度数:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    行元素之和为vi的出度
    列元素之和等于vi的入度

    握手定理

    在这里插入图片描述
    可图化序列:
    在这里插入图片描述
    【例题】有一个警察追小偷进了一个有两个出入口的空宅。已知该宅中有奇数个相互连通的房间,每个房间有奇数个通往不同房间的门。若把住出入口,小偷能否逃出空宅?

    【解】由题设及分析可知,空宅内通道图中,结点个数为奇数,每个结点的度数为奇数,根据图的度结构性质。 这是不可能的,所以宅内一定还有一处通往外面的密门,在出入口被堵的情况下,小偷有可能通过密门逃出空宅。

    路与连通

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    基本通路一定是简单通路
    简单边不同,基本点不同
    在这里插入图片描述

    在这里插入图片描述

    求两个结点之间长度为n的通路数目

    在这里插入图片描述
    在这里插入图片描述
    从结点vi到vj长度为3的通路总数为:
    在这里插入图片描述

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

    通路定理

    通路定理
    推论1
    n 阶图中,若从顶点v i到 v j 存在
    通路(两个节点不相等),则从 Vi 到v j 存在长度小于等于n -1的基本通路。
    定理 在一个具有n个结点的图中,如果存在经过结点vi回路,则存在一条经过vi的长度不大于n的回路。
    推论 在一个具有n个结点的图中,如果存在经过结点vi回路,则存在一条经过vi的长度不大于n的基本回路。

    图的可达性

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

    在这里插入图片描述

    可达性矩阵

    在这里插入图片描述
    在这里插入图片描述
    恒等关系IV等于矩阵的零次幂
    在这里插入图片描述
    若无向图每一对不同的顶点之间都有通路,则该图称为连通的,否则称为非连通图或分离图
    无向完全图Kn(n≥1)都是连通图**,而多于一个结点的零图都是非连通图**。
    非平凡无向线图G是连通图当且仅当它的可达性矩阵P的所有元素均为1。
    在这里插入图片描述
    连通分支
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    连通图可以看成是只有一个连通分
    支的图, 即 W(G)=1。
    或者:
    若无向图G只有一个连通分支,则
    称G是无向连通的。
    【例题】: 假设𝐺=𝑉,𝐸 为任一给定的无向简单图,其中𝑉=𝑛,𝐸=𝑚,𝑝𝐺是其连通分支数,
    证明:𝒏−𝒑(𝑮)≤𝒎。
    证明:对𝑚作数学归纳法证明:
    当𝑚=0时,𝐺是零图,𝑝(𝐺)=𝑛,命题成立。
    设不等式对于𝑚−1成立,要证明对𝑚也成立。现从𝐺上删去一条边得𝐺′,则𝐺′有两种可能:
    ① 𝐺′有𝑛个结点,𝑝𝐺个连通分支,𝑚−1条边,根据归纳假设𝑛−𝑝𝐺≤𝑚−1,故有:
    𝒏−𝒑𝑮≤𝒎−𝟏<𝒎;
    ② 𝐺′有𝑛个结点,𝑝𝐺+1个连通分支,𝑚−1条边,根据归纳假设:
    𝑛−(𝑝𝐺+1)≤m−1
    故有:
    𝑛−𝑝𝐺≤m
    成立。
    故对一切𝑚,成立
    𝒏−𝒑𝑮≤𝒎

    割点割边

    ⨠⨠有时删除一个顶点和它所关联的边,就产生带有比原图更多连通分支的子图。把这样的顶点称为割点。从连通图里删除割点,就产生不连通的子图。
    ⨠⨠把一旦删除就产生带有比原图更多的连通分支的子图的边称为割边或桥。

    定义8.3.8 无向图 𝐺=𝑉,𝐸,若存在𝑉的某个子集 𝑉′⊆𝑉 ,使得 𝑝(𝐺−𝑉′)>𝑝(𝐺) ,且对于 𝑉′的任何真子集 𝑉′′,有
    𝒑(𝑮−𝑽′′)=𝒑(𝑮)
    则称 𝑉′为 𝐺 的点割集。如果点割集中只有一个结点 𝑣 ,则称 𝑣 为割点
    在这里插入图片描述
    无向图 𝐺=<𝑉,𝐸>,若存在边集 𝐸的某个子集𝐸′⊆𝐸 ,使得 𝑝(𝐺−𝐸′)>𝑝(𝐺 ),且对于 𝐸′的任何真子集 𝐸′′,有
    𝒑(𝑮−𝑬′′)=𝒑(𝑮) 则称 𝐸′为 𝐺 的边割集。如果边割集中只有一条边 𝑒,则称 𝑒 为割边或桥
    总结:

    ⨠⨠(1)完全图 𝐾𝑛 无点割集,因为从 𝐾𝑛 中删除 𝑘≤𝑛−1个顶点后,所得图仍然是连通的。
    ⨠⨠(2) 𝑛 阶零图既无点割集也无边割集。
    ⨠⨠(3) 对于连通图 𝐺,𝐸′为 𝐺 的边割集,则必有 𝑝𝐺−𝐸′=2 。 因为删除一条边最多只能增加一个连通分支。
    ⨠⨠(4) 对于连通图 𝐺 ,𝑉′为 𝐺 的点割集,则 𝑝𝐺−𝑉′≥2,而且可能 𝑝𝐺−𝐸′>2,因为删除一个结点可能增加多个连通分支。
    连通度:
    (注意是最小的点割集的结点个数)
    在这里插入图片描述
    (1) 如果 𝐺是平凡图或非连通图,则规定
    𝜿𝑮=𝝀𝑮=𝟎;
    (2) 如果𝐺 是完全图 𝐾𝑛 ,由于 𝐺 中无点割集,当删除 𝑛−1个顶点后,𝐺 为平凡图,故
    𝜿𝑮=𝒏−𝟏。
    (3) 如果 𝐺 中存在割点,则 𝜿𝑮=𝟏;
    如果 𝐺 中存在割边,则 𝝀𝑮=𝟏。
    在这里插入图片描述

    有向图的连通性

    强连通图:若图中任何一对结点两者之间相互可达(两个方向)。
    ⨠⨠单连通图:任何一对结点间至少有一个结点到另一结点可达。 (单方向)
    ⨠⨠弱连通图:把有向图看成无向图时图是连通的。
    对于弱分图,存在两个结点之间是不可达的
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    有向图G是强连通图的充分必要条件是G中存在一条经过所有结点的回路。
    该定理给出了判断强连通图的简便方法。
    有向图G是单向连通图的充分必要条件是G中存在一条经过所有结点的通路。
    •该定理给出了判断单向连通图的简便方法。

    在这里插入图片描述
    一、如果不考虑边的方向,弱连通分支对应相应的无向图的连通分支。
    二、注意把握(强、单向、弱)连通分支的极大性特点,即任意增加一个结点或一条边就不是(强、单向、弱)连通的了
    在这里插入图片描述
    强分图 单分图 弱分图
    在这里插入图片描述
    在这里插入图片描述
    强连通的等价性
    若在有向图G = <V, E>的结点集V上定义二元关系R为:<vi,vj>∈R当且仅当vi和vj在同一强(弱)连通分支中,对一切vi,vj∈V。则R是一个等价关系。
    这种等价关系把结点分成等价类,等价类的集合是V上的一个划分,每一个等价类的结点导出一个强(弱)连通分支。有如下三个定理
    【定理】在有向图G = <V, E>中,它的每一个结点位于且仅位于一个强(弱)连通分支中。(对结点的分类)
    【定理】在有向图G = <V, E>中,它的每一个结点至少位于一个单向连通分支中。 (对结点的聚类,相容关系)
    【定理】在有向图G = <V, E>中,它的每一条边至多在一个强连通分支中,至少在一个单向连通分支中,在且仅在一个弱连通分支中。(对边的划分)

    展开全文
  • 子图,生成子图和导出子图

    万次阅读 多人点赞 2016-10-08 23:46:43
    设V1是V的一个非空子集,以V1为顶点集,以两端点均在V1中的边的全体为边集的子图称为G的导出子图,记作G[V1]。导出子图G[V\V1]记为G-V1,它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v},则...

    所有的顶点和边都属于图G的图称为G的子图。含有G的所有顶点的子图称为G的生成子图。 设V1是V的一个非空子集,以V1为顶点集,以两端点均在V1中的边的全体为边集的子图称为G的导出子图,记作G[V1]。导出子图G[V\V1]记为G-V1,它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v},则把G-{v}简记为G-v, 称为主子图。在图1-13中,G1是G的生成子图,G2是G的导出子图,G3是G的主子图。


    展开全文
  •  设V1是V的一个非空子集,以V1为顶点集,以两端点均在V1中的边的全体为边集的子图称为G的导出子图,记作G[V1]。导出子图G[V\V1]记为G-V1,它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v},...
     所有的顶点和边都属于图G的图称为G的子图。含有G的所有顶点的子图称为G的生成子图。
        设V1是V的一个非空子集,以V1为顶点集,以两端点均在V1中的边的全体为边集的子图称为G的导出子图,记作G[V1]。导出子图G[V\V1]记为G-V1,它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v},则把G-{v}简记为G-v, 称为主子图。在图1-13中,G1是G的生成子图,G2是G的导出子图,G3是G的主子图。


    展开全文
  • 1. 各类子图(子图;真子图;生成子图;导出子图) 2. 完全图(无向完全图和有向完全图) 3. 补图 4. 补图的邻接矩阵 5. 补图的应用实例 ...

     

    1. 各类子图(子图;真子图;生成子图;导出子图)

     

    2. 完全图(无向完全图和有向完全图)

     

    3. 补图

     

    4. 补图的邻接矩阵

     

    5. 补图的应用实例

     

     

     

     

    展开全文
  • 离散数学

    2021-09-05 10:41:58
    对称,传递关系,(三者同时满足) 等价类:A中具有同一性质的元素的集合 Ps:等价关系R的关系图(图都是搭配着有序对)(P116)由若干个独立子图组成,每个独立子图都是全域关系图,独立子图的个数等于等价类的个数...
  • 离散数学重点(第四部分)

    千次阅读 2020-08-18 21:20:31
    离散数学的知识只包括本人根据自身前提情况认为有必要一看的内容 1. 边点关联:设ek=(vi,vj)为无向图G的一条边。vi,vj为ek的端点。则ek与vi,vj关联。 若vi≠vj,则关联次数为1;若vi=vj,则关联次数为2. 2. 无向...
  • 离散数学映像笔记

    2021-09-16 21:00:56
    离散数学 8.1 图论 8.1.1 图的基本概念 G = < V, E > 称为图 图中结点集合的基数n称为图的阶数 无序积 记作A&B={(x,y)∣x∈A,y∈B}A\&B = \{(x, y)|x\in A, y \in B \}A&B={(x,y)∣x∈A,y∈B}​ ...
  • 离散数学之图

    千次阅读 2021-03-31 22:53:59
    等价定义,连通图的连通分支为 1 连通分支:连通关系的导出子图,记 W ( G ) W(G) W(G) 强连通图:有向图中,任意两个节点都相互可达 单向连通图:有向图中,任意两个节点至少存在一个点到另一个点 弱连通图:将有向...
  • 离散数学-图的定义和分类计算机科学与工程学院 离散数学教研组 * 第12章图 12.1 图的基本概念 12.1.1 图的定义 无序积 定义12.1 设A,B为任意集合,称集合 A&B={(a,b)|a∈A,b∈B} 为A与B的无序积,(a,b)称为...
  • 离散数学重点概念与公式总结

    千次阅读 2020-12-20 12:32:44
    并称导出子图G[E(G)-E(T)]为T的余树,记作T。 最优二元树:设2叉树T有t片树叶v1,v2,…,vt,权分别为w1,w2,…,wt,称W(t)=wil(vi)为T的权,其中l(vi)是vi的层数。在所有有t片树叶,带权w1,w2,…,wt的2叉树中,权最小...
  • 离散数学期末复习总结

    千次阅读 多人点赞 2021-01-02 00:09:37
    数学中常见数集 6.1.2 集合与元素的关系 有限集:集合中的元素是有限个 有限集的基: 无限集:集合中的元素无限个 6.1.3 集合之间的关系 子集 集合相等 真子集 若 A 中至少有一个元素不属于 B 注意区别元素与集合...
  • 离散数学】图论基础知识

    万次阅读 多人点赞 2019-06-27 13:41:35
    离散数学部分2.1 图的基本概念2.2 图的连通性2.3 图的矩阵表示2.4 几种特殊的图2.4.1 二部图2.4.2 欧拉图2.4.3 哈密顿图2.4.4 平面图2.5 无向树2.6 生成树 1.数据结构部分 2.离散数学部分 2.1 图的基本概念 无向图:...
  • 代数系统、子代数 代数系统的同态映射 代数系统的类型(半群、独异点、群) 群的阶、群中元素的阶 群的幂运算 子群的证明 第四部分 简单图画(握手定理、同构图) 各类图(完全图、竞赛图、生成子图、导出子图) ...
  • 离散数学复习命题公式的范式 离散数学平面图对偶图和着色问题 离散数学谓词逻辑 离散数学-图的运算与基本概念、导出子图、路与连通 离散数学关系的基本运算和关系的性质闭包 离散数学-欧拉图和哈密顿图 文章目录 ...
  • 北航离散数学期末总结

    千次阅读 2019-06-20 16:13:08
    判断子图算法 def issubgraph(V,E,Vs,Es): tv=(Vs <= V) and (Es <= E) # 点集是子集,边集是子集 return tv 判断真子图算法 def ispropersubgraph(V,E,Vs,Es): # 首先要是一个子图,然后点集或者边...
  • 由此定理易得:设G是顶点数n> r(k,k)的简单图,其边数e> 0,且G的所有k阶导出子图的边数相等,那么G是完全图.并给出上述结论的推广:设G是n(n≥4)阶简单图,其边数e> 0,对某个给定的自然数k(2≤k≤n- 2),若G的所有k阶导出...
  • 离散数学精简笔记 ——《图论》

    千次阅读 2018-12-17 13:51:40
    ​:若E1⊆E(G),则以E1为边集,以E1中所有边的顶点为顶点集组成的图,称为图G的边的导出子图,记为G(E1)。​ 补图 :图G的补图,通俗的来讲就是完全图Kn去除G的边集后得到的图Kn-G。 连通性 道路 :两点之间可...
  • 离散数学知识点总结

    千次阅读 2020-07-08 02:01:33
     边的导出子图:设,且,称以为边集,以中变关联的顶点为顶点集的图为G的导出子图,记做 17.同构:两个图的节点和边存在一一对应关系,且相互关联,最简单的例子,下面的五边形和五角星是同构的: 详细定义: 关于...
  • 复习自用,仅供参考 教学用书:离散数学/耿素云,屈婉玲,张立昂编著. --5版. --北京:清华大学出版社,2013 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 范式 1.5 联结词全功能集 ...
  • 本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动,欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外,在本系列学习文章中,为了透彻理解数学知识,...
  • [【离散数学】图论 第七章(3) 图的矩阵表示(邻接矩阵、可达矩阵和沃舍尔算法)] 采用矩阵表示图,便于计算机存储和处理图的信息(只对小图、稠密图有点用),也便于运用代数的方法研究图的性质(这才是重点!),...
  • 离散数学第六章 图

    千次阅读 2016-06-19 10:27:24
    导出子图:顶点导出子图、边导出子图 5. 图的同构 根据图的同构定义,可以给出图同构的 必要条件 : (1) 结点数目相等; (2) 边数相等; (3) 度数相同的结点数目相等。 但这仅仅是必要条件而不是...
  • 离散数学图论整理

    千次阅读 2020-06-04 20:28:56
    生成子图:顶点和母图相同的子图 V’导出子图G[V’]:顶点集+和这些顶点关联的所有边作为边集 E’导出子图G[E’]:边集+和这些边关联的顶点作为顶点集 补图:顶点集和原图G相同,边集和原图G相加为Kn 一些操作 G-e...
  • 离散数学Ⅰ(图论)期末复习第一篇 写这个时的感想 第五章 图的基本概念 5.1 有向图和无向图 5.2 通路、回路和图的连通性 5.3 图的矩阵表示 5.4 最短路径、关键路径和着色 写这个时的感想 第一篇博客!!! 小...
  • 离散数学图论和树的知识点总结

    千次阅读 2020-03-31 12:43:09
    离散数学图论和树的知识点总结 目录 离散数学图论和树的知识点总结 图论 图的定义和表示 无向图和有向图 子图,真子图,导出子图,生成子图,补图 图的连通性及判定条件 欧拉图,哈密顿图,偶图(二分图),平面图 ...
  • 离散数学笔记

    2021-12-09 17:32:17
    图论 4.1 图的基本概念 4.1.1 无序积 4.1.2 无向图 4.1.3 有向图 4.1.4 n阶图 4.1.5 零图 4.1.6 空图 4.1.7 基图 4.1.8 简单图 4.1.9 多重图 4.1.10 度 4.1.11 握手定理 4.1.12 度数列 4.1.13 完全图 4.1.14 子图&...
  • 离散数学 7.图

    千次阅读 2020-04-19 01:30:49
    在图G中以V2为结点集的所有边集和V2结点集组成的子图称为V2的导出子图。(可以用删除图G结点的方法来实现) 任意两个结点间都有边相连,则称(有向,无向)完全图。 G的补图就是从完全图中删除图G中的边。(孤立...
  • 离散数学 总结思路

    万次阅读 多人点赞 2018-07-02 09:56:11
    导出子图 : 都不同 简单通路: 边不同 初级通路 : 点不同 + 简单通路 割点 桥 强连通图 关联矩阵 : 相乘得到点邻接点的长度 二部图 无奇回路 欧拉图(回路) 无奇度顶点 半欧拉图 : 两个奇度顶点 (起点, 终点) 画法 : ...
  • 离散数学 图的基本概念

    万次阅读 多人点赞 2018-07-12 13:23:56
    1.9.4 导出子图 1.10 补图 1.10.1 补图 1.10.2 自补图 1.11 图的操作 1.11.1 删除边(集) 1.11.2 删除顶点(集) 1.11.3 收缩 1.11.4 加新边 2 通路与回路 2.1 通路 2.1.1 ...
  • 离散数学-图论相关

    千次阅读 2019-04-11 16:25:29
    文章目录 图的基本概念 无向图和有向图 无向图 有向图 关联和度 关联 度 握手定理 简单图与完全图 ...T中所有弦的集合的导出子图称为T的 余树 基本回路和基本割集 基本回路 设T是连通图 $G=,E...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 244
精华内容 97
关键字:

离散数学导出子图