求图18.7所示无向图G中的两个不同的极大匹配，一个最大匹配及匹配数β₁

0。

图7中所示的无向图G中，实线边所表示的子图为G的一棵生成树T。（1)求G对应T的所有基本回路。（2)求G

图7中所示的无向图G中，实线边所表示的子图为G的一棵生成树T。

(1)求G对应T的所有基本回路。

(2)求G对应T的所有基本割集。

无向图G如图14.19所示（1)求G的全部点割集和边割集，并指出其中的割点和桥（割边),（2)求G的点连

无向图G如图14.19所示

(1)求G的全部点割集和边割集，并指出其中的割点和桥(割边),

(2)求G的点连通度k(G)和边连通度λ(G).

所谓单目标最短路径（single-destinationshortestpath)问题是指在一个带权有向图G中求从各个顶

点到某一指定顶点v的最短路径，例如，对于图8-47(a)所示的带权有向图，用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.

关于最短路径的读法以顶点0为例，在从顶点0到顶点2的最短路径上，顶点0的后继为顶点1(即path[0]=1)，顶点1的后继为顶点3(即path[1]=3)，顶点3的后继顶点为2(即path[3]=2).

编写一个算法，求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char，边上权值的数据类型为float。

证明定理15.8.

定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.