无向图的度数与边的关系

Question

如题所述

Answer 1

当图为无向图是边数为e时，那么度数为2e，当图为有向2图时，那么度数也为2e，所以说边数e和度数之间的关系为2e。

基本图：把有向图D的每条边除去定向就得到一个相应的无向图G，称G为D的基本图。称D为G的定向图

图G的顶点数和边数e的关系：若G是无向图，则0≤e≤n(n-1)/2。若G为无向图，则0≤e≤n(n-1)。

扩展资料：

有向图和无向图求解最短路径区别：

1、无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号。

2、有向最短路问题使用双标号法。双标号法是对每一点赋予两个标号：路径和路权。

完全图具有最多的边数。任意一对顶点间均有边相连。

图的遍历算法：

1、广度优先搜索法

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1，vi2，…，vi t，并均标记已访问过。

然后再按照vi1，vi2，……，vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

2、深度优先搜索法

深度优先搜索法是树的先根遍历的推广，基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。

如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。