# 给出一个算法求解最大生成树。这比求解最小生成树更难吗？

将 Kruskal 算法生成最小生成树关于最小值选择比较的语句改成最大值比较即可，和求解最小生成树相比一样难度。

# 证明寻找割点的算法的正确性

假设存在一个矛盾，即非根节点$a$ 和后代节点和正确的祖先节点没有正确的建立联系，因为存在这个矛盾且确实存在，因此存在寻找割点的算法的可能。

# 证明：在一个有向图的深度优先生成森林所有的交叉边都是从右到左的。

设$(v,w)$ 为交叉边，当检查点$w$ 时，标记，若点$v$ 不是$w$ 的后代，按照左右子树的规定，则应该是$w -> v$, 即从右到左。

# 给出一个算法以决定在一个有向图的深度优先生成森林中的一条边$(v,w)$ 是否是树，背向边，交义边或前向边。

树边：遍历时有$num_v < num_w$。
交叉边：遍历时有$num_v \notin num_w$ 且$num_w \notin num_v$, 且$v,w$ 不在同一棵树上。
背向边：顶点$v$ 有大的权重且不是交叉边就是背向边。
前向边：不是以上三种边的边就是前向边 (感觉这是废话)。
判别这几种边可以使用$dfs$ 搜索，同时使用一个栈来记录路过的路径，并比较上面四种情况是那种边。

# 编写一个程序以找出一一个有向图的强连通分支。

实际上叫你实现 Tarjan 算法，只要满足 Tarjan 算法的路径就是强连通分量。

void Tarjan(Graph G) {

    /* 

    * Note: if your camke project build in VS, you should

    * use int n = 6 replace int n = G->Vertex_Num

    * otherwise it will fail build

    */

    int n = G->Vertex_Num;

    // int DFN[n],LOW[n];

    // bool stack[n];

    int DFN[6],LOW[6];

    bool stack[6];

    Stack S = Stack_Init();

    for (int i = 0; i < n; i++) {

        DFN[i] = LOW[i] = NIL;

        stack[i] = false;

    }

    for (int i = 0; i < n; i++)

      if (DFN[i] == NIL) 

        Tarjan1(G, i, DFN, LOW, S, stack);

}

# 给出一个算法，在只用一次深度优先搜索内找出强连通分支来。使用类似于双连通性算法的算法。

其实就是 Tarjan 算法的步骤，原始的 Tarjan 算法确实需要两次$dfs$, 但使用栈记录路径过后可以合并为一次$dfs$。

# 一个图$G$ 的双连通分支 (biconnected component) 是把边分成一些集合的划分，使得每个边集所形成的图是双连通的，修故图 9-67 中的算法使能找出双连通分支而不是割点。

建立一个栈储存遍历的点，当满足割点条件时，出栈，即双连通分量。大致思路见图的割点、桥和双连通分支的基本概念

# 设我们对一个无向图进行广度优先搜索并建立一棵广度优先生成树。证明该树所有的边要么是树边要么是交叉边。

假设$(u,v)$ 是广度优先搜索树上一条连通的边，令从根节点到 u 的距离为$d_u$, 同样根节点到 v 的距离为$d_v$, 假设$(u,v)$ 是一条后向边，则有$d_u>d_v$, 但是$(u,v)$ 是连通的，有$d_u<d_v$, 且$v$ 是先遍历的，与假设相矛盾，前向边同理，所以只有树边和交叉边这种可能。

# 给出一个算法在一无向（连通）图中找出一条路径使其在每个方向上恰好通过每条边一次。

执行一次深度优先遍历，并设立一个数组，每遍历一个点标记并存入数组。

# 编写一个程序以找出一个图中的一条欧拉回路或欧拉环游 (如果存在的话)。

在一定程度上欧拉回路和欧拉环游是有基本解的，所有我这里直接通用的使用 Hierholzer 算法求基本解。

// This function only works for undirected graphs

void Find_EulerCircuit(Graph G) {

    int index = IS_EulerGraph(G);

    Stack S = Stack_Init();

    if (index == 0) {

        printf("The graph is Euler Graph\n");

        Hierholzer(G, 0, S);

    }

    else if (index == 2) {

        printf("The graph is Semi Euler Graph\n");

        Hierholzer(G, 0, S);

    }

    else

       printf("The graph is not Euler Graph\n");

    while (!Stack_IsEmpty(S)) {

        printf("%d ",Pop(S));

    }

}

# 令$G=(V,E)$ 是一个无向图，使用深度优先搜索设计一个线性算法把$G$ 的每条边转换成有向边使得所得到的图是强连通的，或者确定这是不可能的。

实际是可能的。只需要对 Hierholzer 算法改进一下，改变内容为只删$(v,u)$, 并标记$(u,v)$ 为有向图。

# 给你一把棍共$N$ 根，它们以某种结构相互叠压平放，每根棍由它的两端点确定：每个端点是由$x$ 和$y$ 和$z$ 坐标确定的有序三元组：没有棍垂直摆。一根棍仅当其上没有棍放置时可以取走：

# 解释如何编写一个例程接收两根$a$ 和$b$，并报告$a$ 是否$b$ 上面、$b$ 下面，或是与$b$ 无关：(本问与图论毫无关系)

把木棍当作一个点，监测点$a$ 在点$b$ 的位置，若满足上述三种情况则提示，否则则不可能。

# 给出一个算法确定是否能够取走所有个棍，如果能，那么提供完成这项工作的拾取次序。

能。定义一个图，其中每根棍子由一个顶点表示。 如果$s_i$ 在$s_j$ 之上，因此必须先将其移除，然后将边缘从$s_i$ 放置到 $s_j$。 合法的取货顺序由拓扑排序给出； 如果图形有循环，则无法拾取木棍。