《离散数学》图论中的各种名词的解释表格整理版

1、第一章命题逻辑原式P-Q逆换式Q-P反换式PQ逆反式QP第七章图论孤立结点不与任何结点相邻接的结点零图仅由孤立结点构成的图平凡图仅由一个孤立结点构成的图邻接边关联于同一结点的两条边自回路/环关联于同一结点的一条边度数与节点关联的边数，成为结点的度数多重图含有平行边的任何一个图简单图由无向图衍生出,一个结点对有且仅有一条边。完全图Kp简单图G二V,E，每一对结点间都有边相连Kn有n个结点的无向完全图补图给定一个图G,由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的相对于完全图的补图。生成子图若G的子图包含G的所有结点，该子图成为G的生成子图。相对补图设G=V,E是G=V,E的子图，

2、若给定另外一个图G二V,E使得E二E-E：且V中仅包含E的边所关联的结点。则称G是子图G的相对于图G的补图。同构设图G=V,E及图G-V,E,如果存在对应的映射g：Vi一*且e=(Vj,Vj)(或*“)是G的一条边，当且仅当e=(g(vi),g(vj)(或g(vi),g(vj)是G的一条边，则称G与G同构，记作GG路vOe1v1e2envn称作联结vo到vn的路回路路中,vO=vn时，就称作回路迹/简单路径条路中所有的边e1,e2,en均不同通路/基本路径条路中所有的结点v0,v1,vn均不相同圈闭的通路;除vO=vn外，其余节点均不相同连通两节点之间存在条路连通图图G中只有一个分支点割集设无

3、向图G二V,E为连通图，若有点集V1uV,使图G删除了V1的所有结点后，所得的子集是不连通图，而删除了V1的任意真子集后，所得到的图仍是连通图，则称V1是G的一个点割集。割点若某一个结点构成一个点割集，则称该结点为割点边割集设无向图G二V,E为连通图，若有边集E1uE,使图G删除了E1的所有边后，所得的子集是不连通图，而删除了E1的任意真子集后,所得到的图是不连通图，则称E1是G的一个边割集。边/桥某一个构成一个边割集的边k(G)/(点)连通度min|V1|V1是G的一个点割集（平凡图）久（G）连通度（非平凡图）min|E1|E1是G的边割集单侧连通有向图:任何一对结点间，至少有一个结点到另一

4、个结点是可达的强连通有向图:任何一对结点，两者之间是相互可达的弱连通有向图:看成无向图后图是连通的强分图有向图:具有强连通性质的最大子图单侧分图有向图:具有单侧连通性质的最大子图弱分图具有弱连通性质的最大分图连接矩阵书P288adj邻接nadj不邻接可达性矩阵书P291完全关联矩阵无向图:P294欧拉图给定孤立结点图G,若存在一条路，经过图中每边一次且仅一次。欧拉回路给定孤立结点图G,若存在一条回路，经过图中每边一次且仅一次。单向欧拉路（回路）有向图G通过图中每边一次且仅一次的一条单向路（回路）汉密尔顿路给定图G,若存在一条路经过图中的每个结点恰好一次汉密尔顿回路若存在一条回路，经过图中的每个

5、结点恰好一次汉密尔顿图具有汉密尔顿回路的图W(G-S)G-S中连通分支数平面图设G-V,E是个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的父点。面设G是一连通平面图.由图中的边所包围的区域.在区域内不包含图的结点，也不包含图的边，这样的区域称为G的一个面。边界包围一个面所构成的回路称为这个面的边界无限面不受约束的面面的次数deg（r）面的边界的回路长度ViVj=Vi,j有向图：Vi,j=Vi+Vj无向图：Vij=(Vi+Vj)%2闭包C(G)给定图G二V,E有n个结点，若将图G中度数之和至少是n的非邻接节点连接起来得图G,对图G重复上述步骤，直到不再有这样

6、的结点对存在为止，所得到的图，称为是原图G的闭包。在2读节点内同构给定两个图G1和G乙如果它们是同构的，或者通过反复插入或除去度数为2的结点后，使G1与G2同构，则称该两图是在2读结点内同构的。K3,32步图。上下顶点分别为3.对偶图书P318树个连通且无回路的无向图森林的每个连通分图无回路且e=v-1连通且e=v-1无回路但增加一条新边，得到一个且仅有一个回路连通，但删去任一边后便不连通每一对结点之间有一条且仅有一条路树叶度数为1的结点分至点/内点度数大于1的结点森林一个无回路的无向图生成树若图G的生成子图是一棵树，则称该树为G的生成树树枝设图G有一棵生成树T,则T中的边称作树枝弦图G的不在牛成树的边补所有弦的集合称为生成树T的补树权C(T)T的所有边权的和最小生成树在图G的所有生成树中，树权最小的那棵生成树有向树个有向图在不考虑边的方向时是颗树根树棵有向树，如果恰有一个结点的入度为0,其余所有的入度都为1根根树中入度为0的结点叶根树中出度为0的结点分枝点/内点出度不为0的结点m叉树在根树中，若每一个结点的出度小于或等于m,则称这棵树为m叉树完全m叉树如果每一个结点的出度恰好等于m或0正则m叉树完全m叉树所有树叶层数相同二叉树这则m叉树当m=2时通路长度个结点的通路长度，就是从树根到此结点的通路中的边数内部通路长度分枝点的通路长度外部通路长度树叶的通路长度带权