标签:   离散数学   第3章   基本   概念  
文档信息
上传用户 ༈དཔལ་     
文档格式 ppt
文档价格 7.3 元
文档大小 424 KB
文档页数 31 页
相关文档推荐
doc 广东省重点小学四年级数学下学期期末摸底考试试卷C卷 附解析
doc 2019-2020学年高二英语上学期第十二次双周考试题
doc 实验小学二年级数学下学期开学考试试题沪教版 含答案
doc 2019-2020年高三上学期期中调研生物试题 含答案
doc 实验小学二年级数学下学期开学考试试题湘教版B卷 含答案
doc 2019-2020年高三上学期期中调研考试政治试题含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) 附解析
doc 2020年六年级数学【上册】期末考试试题上海教育版B卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) (附解析)
doc 实验小学二年级数学下学期开学考试试题浙教版(II卷) 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合检测B卷 附答案
doc 云南省2020年实验小学一年级数学期中考试试卷A卷 含答案
doc 实验小学二年级数学下学期开学考试试题湘教版A卷 附答案
doc 实验小学二年级数学下学期开学考试试题湘教版 附解析
doc 实验小学二年级数学下学期开学考试试题苏教版C卷 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 (含答案)
doc 2020年六年级数学【上册】期末考试试题上海教育版 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版C卷 含答案
ppt 《技术进步与》PPT课件
doc 山东省重点小学三年级数学【上册】期末摸底考试试题 含答案
doc 实验小学二年级数学下学期开学考试试题浙教版 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷D卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 含答案
doc 山东省重点小学三年级数学【上册】期末摸底考试试题 附答案
ppt 《技术进步与发展》PPT课件
ppt 《把掌声分给她一半》PPT课件
doc 实验小学二年级数学下学期开学考试试题沪教版(II卷) 含答案
ppt 《把握商机创造需求》PPT课件
doc 2020年六年级数学【上册】期末考试试题上海教育版(II卷) 含答案
doc 2019-2020学年高二英语上学期第十四次双周考试题
ppt 《把字句偏误分析》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试卷C卷 (附解析)
doc 山东省重点小学三年级数学【上册】期中考试试题 含答案
ppt 《把握思维的奥妙》PPT课件
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 附解析
doc 山东省重点小学三年级数学【上册】开学考试试题 附答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测A卷 (附解析)
doc 实验小学二年级数学下学期开学考试试题苏教版(I卷) 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合检测B卷 附解析
doc 云南省2020年实验小学一年级数学期中检测试卷(I卷) 含答案
ppt 离散数学第三章谓词演算基础-唯一性量词与摹状词
doc 2019-2020年高三上学期期中质量抽测英语试题 Word版含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 附答案
doc 2020年六年级数学【上册】期末考试试题人教版 (附答案)
doc 2019-2020年高三上学期期中调研考试化学试题 含解析
doc 2020年六年级数学【上册】期末考试试题人教版C卷 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版(I卷) 附答案
ppt 《把握时代脉搏作》PPT课件
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 附解析
doc 山东省重点小学三年级数学【上册】期末摸底考试试题 (附答案)
doc 山东省重点小学三年级数学【上册】期中摸底考试试题 (含答案)
doc 实验小学二年级数学下学期开学考试试题沪教版 附解析
doc 实验小学二年级数学下学期开学考试试题西南师大版 附答案
doc 云南省2020年实验小学一年级数学期中考试试题(I卷) 含答案
doc 2019-2020年高三上学期期中调研测试化学试题含答案
doc 云南省2020年实验小学一年级数学期末考试试卷(II卷) 含答案
doc 云南省2020年实验小学一年级数学期末考试试题A卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测A卷 附答案
doc 云南省2020年实验小学一年级数学期中考试试题C卷 含答案
doc 实验小学二年级数学下学期开学考试试题湘教版C卷 含答案
ppt 《把不可能变成可能》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》综合检测A卷 (含答案)
doc 2019-2020学年高二英语上学期第十五次双周考试题
doc 云南省2020年实验小学一年级数学期中检测试卷C卷 含答案
doc 2019-2020年高三上学期期中质量抽测数学试题 Word版含答案
doc 云南省2020年实验小学一年级数学期中测试试题B卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 (附解析)
ppt 离散数学第一章命题逻辑
doc 山东省重点小学三年级数学【上册】开学考试试卷 (附解析)
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) (附答案)
doc 云南省2020年实验小学一年级数学期末测试试卷(II卷) 含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测D卷 附答案
doc 2019-2020学年高二英语上学期第二次统考试题
doc 2019-2020学年高二英语上学期第六次双周考试题 (I)
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 (附解析)
ppt 离散数学第6章图论
ppt 离散数学是研究离散数量关系和离散结构数学模型的数学
doc 云南省2020年实验小学一年级数学期中检测试题C卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测C卷 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版(II卷) 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 附答案
doc 云南省2020年实验小学一年级语文【上册】开学摸底考试试卷 附解析
ppt 《把握青春拍》PPT课件
doc 2019-2020学年高二英语上学期第二次统练试题
doc 2019-2020学年高二英语上学期第二次阶段考试试题
doc 2020年六年级数学【上册】期末考试试题人教版A卷 附答案
doc 实验小学二年级数学下学期开学考试试题苏教版A卷 附解析
doc 2020年六年级数学【上册】期末考试试题人教版 附答案
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 附答案
ppt 《把握古诗情感》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试卷C卷 (含答案)
doc 2020年六年级数学【上册】期末考试试题人教版 附解析
doc 2020年六年级数学【上册】期末考试试题人教版A卷 附解析
doc 2019-2020年高三上学期期中调研测试化学试题含解析
doc 实验小学二年级数学下学期开学考试试题湘教版A卷 附解析
doc 2020年六年级数学【上册】期末考试试卷长春版(II卷) 含答案
doc 山东省重点小学三年级数学【上册】期末摸底考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题浙教版C卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 含答案
doc 实验小学二年级数学下学期开学考试试题湘教版(II卷) 附答案
doc 实验小学二年级数学下学期开学考试试题湘教版B卷 附答案
doc 2019-2020年高三上学期期中质量抽测历史试题含答案
doc 山东省重点小学三年级数学【上册】期中考试试题 附解析
doc 2019-2020年高三上学期期中质检 英语试题
doc 实验小学二年级数学下学期开学考试试题苏教版(I卷) 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 (附答案)
ppt 《把句子和被句子》PPT课件
ppt 《把句子变漂亮》PPT课件
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 附解析
doc 2019-2020学年高二英语上学期第八次双周考试题 (I)
doc 广东省重点小学四年级数学下学期期末摸底考试试卷D卷 (附解析)
doc 实验小学二年级数学下学期开学考试试题苏教版C卷 附答案
doc 2019-2020年高三上学期期中质检化学试题
doc 云南省2020年实验小学一年级数学期末考试试卷C卷 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版A卷 附解析
doc 2019-2020年高三上学期期中质量抽测物理试题 Word版含答案
doc 实验小学二年级数学下学期开学考试试题沪教版(II卷) 附答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测B卷 (附答案)
doc 实验小学二年级数学下学期开学考试试题湘教版C卷 附答案
ppt 《把心智的杯子倒空》PPT课件
doc 实验小学二年级数学下学期开学考试试题浙教版(I卷) 含答案
ppt 《技术部岗位职责新》PPT课件
ppt 离散数学第2章一阶逻辑
doc 2019-2020年高三上学期期中质量抽测英语试题含答案
doc 云南省2020年实验小学一年级数学期末测试试卷B卷 含答案
doc 实验小学二年级数学下学期开学考试试题浙教版B卷 附答案
doc 山东省重点小学三年级数学【上册】期中考试试题 (附答案)
doc 山东省重点小学三年级数学【上册】期中考试试题 (含答案)
doc 实验小学二年级数学下学期开学考试试题西南师大版 含答案
doc 2020年六年级数学【上册】期末考试试题人教版 (含答案)
doc 2019-2020学年高二英语上学期第八次双周考试题
doc 实验小学二年级数学下学期开学考试试题浙教版(I卷) 附解析
doc 云南省2020年实验小学一年级数学期末检测试题(II卷) 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版(I卷) 含答案
doc 山东省重点小学三年级数学【上册】开学考试试题 (附解析)
ppt 《把握食品质量安全》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试卷D卷 附答案
doc 山东省重点小学三年级数学【上册】期中考试试题 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷(II卷) (附解析)
doc 2019-2020年高三上学期期中调研测试数学试卷含答案
doc 2020年六年级数学【上册】期末考试试卷长春版(II卷) 附解析
ppt 《把液体倒入水中》PPT课件
doc 云南省2020年实验小学一年级数学期中考试试题A卷 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 附解析
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版 附解析
doc 山东省重点小学三年级数学【上册】期中考试试卷 附解析
doc 云南省2020年实验小学一年级数学期中测试试卷C卷 含答案
doc 实验小学二年级数学下学期开学考试试题苏教版 附答案
ppt 《把握情感的节奏》PPT课件
ppt 《把句子写具体》PPT课件
ppt 《把握人物形象》PPT课件
doc 山东省重点小学三年级数学【上册】期中考试试卷 附答案
doc 山东省重点小学三年级数学【上册】开学考试试卷 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 (附答案)
doc 云南省2020年实验小学一年级语文【上册】开学摸底考试试题 含答案
ppt 《技能大比武解读》PPT课件
doc 2019-2020学年高二英语上学期第二次质量检测试题
doc 2019-2020年高三上学期期中调研测试数学试题 含答案
doc 山东省重点小学三年级数学【上册】期末摸底考试试卷 含答案
doc 2019-2020学年高二英语上学期第六次双周考试题
doc 云南省2020年实验小学一年级数学期末测试试题(II卷) 含答案
doc 实验小学二年级数学下学期开学考试试题苏教版 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版(II卷) 附答案
ppt 《抄袭系统检测》PPT课件
doc 实验小学二年级数学下学期开学考试试题浙教版A卷 附解析
doc 云南省2020年实验小学一年级数学期中考试试题(II卷) 含答案
doc 2019-2020年高三上学期期中调研测试语文试题
ppt 《技能鉴定培训》PPT课件
doc 实验小学二年级数学下学期开学考试试题苏教版B卷 附解析
doc 山东省重点小学三年级数学【上册】期末摸底考试试卷 (附解析)
doc 实验小学二年级数学下学期开学考试试题湘教版 含答案
doc 山东省重点小学三年级数学【上册】期中摸底考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题苏教版 含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测C卷 (附答案)
ppt 《把握青春把握情感》PPT课件
ppt 《把人往好处想》PPT课件
doc 2020年六年级数学【上册】期末考试试卷长春版(II卷) 附答案
doc 云南省2020年实验小学一年级数学期中检测试卷(II卷) 含答案
doc 实验小学二年级数学下学期开学考试试题苏教版(II卷) 含答案
doc 云南省2020年实验小学一年级数学期末测试试卷A卷 含答案
doc 2020年六年级数学【上册】期末考试试题人教版(II卷) 含答案
doc 云南省2020年实验小学一年级数学期中检测试题A卷 含答案
doc 实验小学二年级数学下学期开学考试试题苏教版(II卷) 附解析
ppt 《技术问题总结》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试卷D卷 (附答案)
doc 2020年六年级数学【上册】期末考试试题上海教育版A卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 (附答案)
doc 云南省2020年实验小学一年级数学期末检测试题B卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 含答案
doc 2019-2020年高三上学期期中调研考试化学试题含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测C卷 附答案
ppt 《把握课程性质》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 含答案
doc 山东省重点小学三年级数学【上册】开学考试试题 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版C卷 附解析
doc 实验小学二年级数学下学期开学考试试题沪教版A卷 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷D卷 附解析
doc 山东省重点小学三年级数学【上册】期中摸底考试试题 附答案

离散数学第3章图的基本概念

 版权申诉  ppt " "计算机数学基础(上) 第2编 图 论" "第三章 图的基本概念" "3.1 图的概念与性质 " "一、图的定义与表示 1。图 由结点的集合V和边的集合E组成的有序对 称为图G。 2。有向图、无向图 每条边都是有向边的图称为有向图,每条边都是 无向边的图称为无向图,否则称为混合图。 3。孤立点、零图 不与其它结点相关联的结点称为孤立点,全部由 孤立点构成的图叫做零图。" "4。边的重数 具有相同始点和终点的边称为平行边,平行边的 条数称为边的重数。 5。n 阶图 具有n个结点的图称为n阶图,具有n个结点和m 条边的图称为(n,m)图 6。结点的度数 图中与某结点v相关联的边数(自回路算两条边), 称为该结点的度数,记作deg(v)。其中以v为始点的边 数称为出度deg+(v),以v为终点的边数成为入度deg-(v) 因此有 图G中结点的最大、最小度数记做Δ(G)、δ(G)" "二、图的基本概念与握手定理 1。握手定理 图G中所有结点的度数之和等于边数的二倍。 [推论1] 在任何图中,度数为奇数的结点数必为偶数。 [推论2] 在有向图中,所有结点的入度之和等于所有结点的出度之和。 例题1: 已知图G中有1个1度结点,2个2度结点,3个3度结 点,4个4度结点,则G的边数是 。 解: " "例题2: 设图G=,则下列结论成立的是 。 A) B) C) D) 例题3: 设简单连通无向图G有12条边,G中有2个1度结点, 2个2度结点,3个4度结点,其余结点度数为3,求G中 有多少个结点。试作一个满足该条件的简单无向图。 解:设G中有x个结点,则3度的结点有x-7。 根据握手定理有," "解得 ,故G中有9个结点。 满足条件的图如下: 2。简单图 不含平行边和环(自回路)的图称为简单图。 在简单图中,任何结点的度数都小于等于n-1。这 是判断一个度数序列能否构成简单图的主要依据。 3。二部图 若将无向图G的结点集分为两部分,而每一部分中 任何两个结点之间都没有边相连,则G称为二部图。" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "4。完全图 每一对结点之间都有边相连的无向简单图称为无 向完全图,每一对结点之间都有方向相反的两条边相 连的有向简单图称为有向完全图。 具有n个结点的无向完全图Kn的边数为: 例题4: 设图G是有n个结点的无向完全图,则G的边数为 。 A) n(n-1) B) n(n+1) C) D)" "C" "5。正则图 若无向简单图G中每个结点的度数都为k,则G称 为k-正则图。 6。赋权图 若图G中的每一条边都有一个表示长度的实数, 则图G称为赋权图或网络。图G为无向图称为无向赋权 图,图G为有向图称为有向赋权图。 7。补图 由图G中的所有结点和构成完全图需添加的边所组成的图称为G的补图,记作 。" "例题5: 已知图的结点集 以及图G和图D的 边集合分别为: 试作图G和图D,写出各结点的度数,回答图G、图D 是简单图还是多重图?  解:a d a d       b c b c 图G 图D" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "图G: 图D: 图G不是简单无向图,图D是简单有向图。 8、子图 1。已知图G=,如果 则G’=称为G的子图。 2。如果 ,则称G’为G的真子图。 3。如果 ,则称G’为G的生成子图。" "" "" "三、图的同构 如果图G中的结点集V与图G’中的结点集V’具有 一一对应的关系,并且对应的边都具有相同的重数, 则称G与G’同构,记作 。 因此,两图同构必须满足下列条件: ⑴结点数相同, ⑵边数相同, ⑶度数相同的结点数相同。 上述条件是两图同构的必要条件,但不是充分条 件,也就是说,两个图即使满足上述条件也不一定同 构。如果把其中一个图中的结点重新排列,边跟着结 点移动,并且可以任意弯曲,能够与另一图完全 重合,那么这两个图是同构的。" "四、通路与回路 1。通路、回路 在G=中,如果从结点v0依次经过边和结 点可以到达vn,则称v0与vn间存在通路,或v0与vn连 通,记作v0~vn ,如v0=vn则称为回路。通路经过 的边数称为通路的的长度。 2。简单通路、简单回路 没有重复边的通路称为简单通路,没有重复边 的回路称为简单回路。 3。基本通路、基本回路 没有重复结点的通路称为基本通路,没有重复 结点的回路称为基本回路。" "例题6: 设G如图,已知通路 ⑴ ⑵ ⑶ ⑷ 试回答它们各是简单通路、简单回路、基本通路 和基本回路。 解:⑴是简单通路,基本通路,⑵是简单回路,但不 是基本回路,⑶是简单回路,基本回路,⑷是简单通 路,但不是基本通路。" " v1 v2 v5 v3 v4" "" "" "" "" "" "" "" "" "" "" "" "" "" "一、连通性 若在无向图G中,任何两个不同的结点都是连通的 则称G是连通图。 无向图中结点的连通关系具有自反性、对称性和 传递性,所以结点的连通关系是等价关系。 若图G不是连通图,但如果把G分成几个部分,每 一个部分都是连通的,则每一个部分称为一个连通子 图,每一个连通子图G’称为G的一个连通分支。 G中相互连通的结点一定在同一连通分支中。 无向图G的连通分支数记作W(G)。 " "3.2 图的连通性 " " 例如G: G不是连通图,但可以划分为三个连通分支。 是一个连通分支, 是一个连 通分支, 是一个连通分支。 称为V的一个划分。 " "" "" "" "" "" "" "" "" "" "" "二、有向连通图 1。强连通图、单侧连通图、弱连通图 在有向简单图D中, (1) 若任何两个结点间都可以到达则称为强连通图 (2) 若任何两个结点间,总有一个结点可以到达另一 个结点,则称为单侧连通图, (3) 若在不考虑边的方向的情况下图是连通的,则称为弱连通图。 连通图举例 强连通图 单侧连通图 弱连通图 " "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "2。两个定理 [定理6] 一个有向图是强连通的充分必要条件是存在一条至少经过每个结点一次的回路。 [定理7] 在有向图中,它的每个结点必位于且仅位于一个强分图中。 例题7: 设V={a,b,c,d},与V能构成强连通图的边集E=( ) (A) {,,,,} (B) {,,,,} (C) {,,,,} (D) {,,,,}" "三、连通度 1。点割集 在无向连通图G=中,若删除结点集V’(包括 所有与V’中的结点关联的边),得到子图G-V’。若V’ 是使G-V’不连通的最小点集,则称V’是G的一个点 割集。若V’中只有一个结点则称为割点。 换句话说,点割集是指使图G从连通图变成不连 通图需要删除的最小点集。 例如,G: 删除v1后G1 " "" "" "" "" "" "" "" "" "删除v3后G2 删除v1,v3后G3 因此,{v1}不是点割集,W(G1)=1, {v3}是点割集,又是割点,W(G2)=2 {v1,v3}不是点割集,因为它不是最小点集。 例题8: 给定图G,则图G的点割集 是 。" " " "2。边割集 在无向连通图G=中,若删除边集E’,得到 子图G-E’。若E’是使G-E不连通的最小边集,则称 E’是G的一个边割集。若E’中仅一条边则称为割边。 换句话说,边割集是指使图G的从连通图变成不 连通图需要删除的最小边集。 例如,G: 删除边(v1,v2)后G1 " "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "删除(v1,v2),(v2,v3)后G2 删除(v3,v5)后G3 因此,{(v1,v2)}不是边割集,W(G1)=1, {(v1,v2),(v2,v3)}是边割集,W(G2)=2, {(v3,v5)}是边割集,也是割边, W(G3)=2。" "" "" "" "" "" "" "" "" "" "" "3。连通度 (一)点连通度 若G是无向连通图,V’是G的结点数最少的点割集 或G-V’是平凡图(孤点),则V’中的结点数称为G的点 连通度,记作 。 因此, (1) 若G是平凡图,则V’=φ, , (2) 若G是完全图,去掉n-1个结点才能成为平凡 图,所以 , (3) 若G存在割点,则 , (4) 若G是非连通图,则 。" "(二)边连通度 若G是无向连通图,E’是G的边数最少的边割集, 则E’中的边数称为G的边连通度,记作 。 因此, (1) 若G是平凡图,则E’=φ, , (2) 若G存在割边,则 , (3) 若G是非连通图,则 。 (三) 之间的关系 在无向图G中,一定有: 即点连通度不大于边连通度,边连通度不大于结 点的最小度数。 " "3.3 图的矩阵表示" "一、无向图的邻接矩阵 对于无向图G=,若|V|=n,作n阶方阵A(G) 其中的 表示 相关联的边数。 例如图G如下, 可以看出,A(G)是对称矩阵。 主对角线上的元素表示各结点的自回路数。 " "" "" "" "" "" "" "" "二、有向图的邻接矩阵 对于有向图D=,若|V|=n,作n阶方阵A(D) 其中的 表示从 的边数。 从下例中可以看出A(D)不再是对称矩阵。 矩阵中所有元素之和等于有向图中的边数。 第 行元素之和表示结点 的出度, 第 列元素之和表示结点 的入度, 图D: " "" "" "" "" "" "" "" "" "" "例题9: 设有向图D=的邻接矩阵为 A(D)= , 那么E= 。 例题10: 有向图D的邻接矩阵A(D)= 中第 行元素的 和 是D中的结点 的 。 " "三、计算边数 在邻接矩阵A(D)中, 为长度为1的边数。 在A2(D)中, 为长度为2的边数。 一般地说,在 中, 为长度为 的边 数。 位置 上的数表示从 长度为 的边数。 在A(D)+A2(D)+ +Ak(D)中, 为长度小于等 于k的边数之和,位置 上的数表示从 长度小 于等于k的边数之和。" "例如,在前例中 长度为2的边共有5条,从 的回路有1条。 长度小于等于2的边共有9条。" "例题11: 设有向图D=, 求D中v2到v4长度分别为 1,2,3 的通路的条数。 解: " "" "" "" "" "" "" "" "" "" "例题12: 已知图D的邻接矩阵为 求从v2到v4长度为2和从v3到v3长度为2的通路条数, 并将它们具体写出. 解: " "" "" "" "" "" "" "" "" "" "" "例题13: 设有向图D=,其中 ⑴求D的邻接矩阵; ⑵判断图D是强连通图、单侧连通图还是弱连通图。 解:








































 版权投诉/申诉   非法内容举报    本页不提供全部页面预览,未展示部分请购买并下载后观看使用