作业帮离散数学中,图论部分,同构的概念怎么理解,比较形象的说出来
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/02 13:05:08
离散数学中,图论部分,同构的概念怎么理解,比较形象的说出来
离散数学中,图论部分,同构的概念怎么理解,比较形象的说出来
离散数学中,图论部分,同构的概念怎么理解,比较形象的说出来
两个图同构,实际上就是一个图,只是标号不同或画法不同而已.
概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。
2.\x09权图中的最短路
严格执行迪克斯特拉（Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。
3.\x09权图中的最优支撑树...
全部展开
概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。
2.\x09权图中的最短路
严格执行迪克斯特拉（Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。
3.\x09权图中的最优支撑树
权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal）算法。
[典型例题]
1、\x09在具有n个顶点的完全图Kn中删去多少条边才能得到树？
n个顶点的完全图Kn中共有n（n-1）/2条边，
n个顶点的树应有n-1条边，
于是，删去的边有：n（n-1）/2-（n-1）=（n-1）（n-2）/2
2、\x09一棵树有两个节点度数为2，一个节点度数为3，三个节点度数为4，问它有几个度数为1的节点？
我们知道一个有限图中，各点的度数总和是边数的2倍；而树中的边数为点数减1。
根据这两点，可知树中各点的度数总和=2*（树中点数-1），设树叶有x个，
于是，2*2+3+3*4+x=2*（2+1+3+x-1）
得，x=9。
收起