耿素云等清华版离散数学pp

耿素云等清华版离散数学ppTag内容描述：<p>1、第八章 一些特殊的图 定义2 给定简单无向图G=，若E*E，且E*中任意两条 边都是不相邻的，则E*称为G的一个匹配或边独立集，若在E*中再 加入任何一条边都不是匹配，称E*为极大匹配，边数最多的极大匹 配为最大匹配，最大匹配中边的个数称为G的匹配数，记为 令M是G的一个匹配，若结点v与M中的边关联，则称v是M饱和 点；否则，称v是M非饱和点；若G中的每个结点都是M饱和点，则 称M是完美匹配。显然，每个完美匹配是最大匹配，但反之不真。 定义3 设G=为一个二部图,M为G中一个最大匹配， 若|M|=min|V1|，|V2|，称M为G中的一个完备匹配，且 若|V1。</p><p>2、第八章 一些特殊的图,定义2 给定简单无向图G=，若E*E，且E*中任意两条边都是不相邻的，则E*称为G的一个匹配或边独立集，若在E*中再加入任何一条边都不是匹配，称E*为极大匹配，边数最多的极大匹配为最大匹配，最大匹配中边的个数称为G的匹配数，记为 令M是G的一个匹配，若结点v与M中的边关联，则称v是M饱和点；否则，称v是M非饱和点；若G中的每个结点都是M饱和点，则称M是完美匹配。显然，每个完美匹配是最大匹配，但反之不真。 定义3 设G=为一个二部图,M为G中一个最大匹配，若|M|=min|V1|，|V2|，称M为G中的一个完备匹配，且 若|V1|V2|,。</p><p>3、第四部分 图论 1 2 3 第七章 图的基本概念 4 5 第一节 无向图及有向图 6 图1 7 V=a,b,c,d E=, , 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第二节 通路、回路、图的连通性 26 27 28 29 30 31 不是，删除 v5后，p(G- v5)p(G),不满足极小性 32 33 34 35 第三节 图的矩阵表示 36 37 38 39 40 41 42 第四节 最短路径与关键路径 43 2.最短路径问题： （1）定义18 设带权图G=,G中每条边的权都大于等于0，u，v为G中 任意两个顶点，从u到v中的所有通路中带权最小的通路称为u到v的 最短路径，求给定两顶点之间的最短路径问题称为最短路。</p><p>4、第四部分 图论 珠 掺 释 褪 誉 伤 娱 七 忙 译 锨 章 价 驮 篆 哇 摈 报 误 恫 剖 挣 弯 粉 然 挡 苞 脑 雁 牵 捅 伶 耿 素 云 等 清 华 版 离 散 数 学 p p t 课 件 ： 第 七 章 图 的 基 本 概 念 耿 素 云 等 清 华 版 离 散 数 学 p p t 课 件 ： 第 七 章 图 的 基 本 概 念 骏 灶 醒 胚 诡 亿 沛 襄 扇 滋 恤 裸 努 制 攀 斡 沉 羽 峪 起 嵌 屏 锚 遗 沸 淤 拍 讼 瞥 烩 女 店 耿 素 云 等 清 华 版 离 散 数 学 p p t 课 件 ： 第 七 章 图 的 基 本 概 念 耿 素 云 等 清 华 版 离 散 数 学 p p t 课 件 ： 第 七 章 图 的 基 本 。</p><p>5、第四部分 图论 第七章 图的基本概念 第一节 无向图及有向图 图1 V=a,b,c,d E=, , 第二节 通路、回路、图的连通性 不是，删除 v5后，p(G- v5)p(G),不满足极小性 第三节 图的矩阵表示 第四节 最短路径与关键路径 2.最短路径问题： （1）定义18 设带权图G=,G中每条边的权都大于等于0，u，v为G中 任意两个顶点，从u到v中的所有通路中带权最小的通路称为u到v的 最短路径，求给定两顶点之间的最短路径问题称为最短路径问题 （2）Dijkstra算法 问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶 点的最短路径。限定各边上的权值大于或。</p><p>6、第四节 联结词全功能集,一、3种常用联结词 定义 设p, q为两个命题， 复合命题“p, q之中恰有一个成立”称为p与q的排斥或，记为pq称作排斥或（异或）联结词， pq为真当且仅当p、q中恰有一个为真。 pq (p q) (p q), 定义 设p, q为两个命题，复合命题“p与q的否定”称为p与q的与非式，记为：pq， 称为与非联结词， pq为真当且仅当p，q不同时为真。 pq。</p>