题目
无向图G如下图所示,实线对应的为G的一棵生成树T,(1)写出对应T的弦e3,e10,e11的基-|||-(2)写出对应树枝e1,e5,e9的基本割集;(3)写出图G的圈秩和割集秩。-|||-el-|||--e2--|||-es e10
题目解答
答案
:(1)对应T的弦e,e10,e11的基本回路分别为:(2)对应树枝e1,e5,e9的基本割集分别为:(3)G的圈秩为2,割集秩为3。答案:(1)对应T的弦e,e10,e11的基本回路分别为:(2)对应树枝e1,e5,e9的基本割集分别为:(3)G的圈秩为2,割集秩为3。
:(1)对应T的弦e,e10,e11的基本回路分别为:(2)对应树枝e1,e5,e9的基本割集分别为:(3)G的圈秩为2,割集秩为3。答案:(1)对应T的弦e,e10,e11的基本回路分别为:(2)对应树枝e1,e5,e9的基本割集分别为:(3)G的圈秩为2,割集秩为3。
:(1)对应T的弦e,e10,e11的基本回路分别为:(2)对应树枝e1,e5,e9的基本割集分别为:(3)G的圈秩为2,割集秩为3。答案:(1)对应T的弦e,e10,e11的基本回路分别为:(2)对应树枝e1,e5,e9的基本割集分别为:(3)G的圈秩为2,割集秩为3。
解析
步骤 1：确定基本回路
对于生成树T，弦e3、e10、e11分别与生成树中的树枝形成基本回路。基本回路是包含一条弦和生成树中的一条路径，使得这条路径与弦一起形成一个回路。
步骤 2：确定基本割集
对于生成树T，树枝e1、e5、e9分别与生成树中的弦形成基本割集。基本割集是包含一条树枝和生成树中的一条路径，使得这条路径与树枝一起形成一个割集。
步骤 3：计算圈秩和割集秩
圈秩是图中基本回路的数量，割集秩是图中基本割集的数量。根据生成树的性质，圈秩等于图中弦的数量，割集秩等于图中树枝的数量。
对于生成树T，弦e3、e10、e11分别与生成树中的树枝形成基本回路。基本回路是包含一条弦和生成树中的一条路径，使得这条路径与弦一起形成一个回路。
步骤 2：确定基本割集
对于生成树T，树枝e1、e5、e9分别与生成树中的弦形成基本割集。基本割集是包含一条树枝和生成树中的一条路径，使得这条路径与树枝一起形成一个割集。
步骤 3：计算圈秩和割集秩
圈秩是图中基本回路的数量，割集秩是图中基本割集的数量。根据生成树的性质，圈秩等于图中弦的数量，割集秩等于图中树枝的数量。