网络优化习题

(1) 二分图； （2）网络； （3）连通分支； （4）支撑树； （5）割集； （6）完全图； （7）简单图； （8）关联矩阵； （9）有向图； （10）顶点； （11）全单模阵

2. Find a minimum weight spanning tree in the network below using:

(i) Kruskal’s algorithm (ii) Prim’s algorithm (iii) Prim’s algorithm (matrix method)

3. Is the following matrix a totally unimodular matrix? Why?

1011 011000

0001110111000 114. If e={i, j } is an edge of the weighted graph G=(V, E), where v{1,2,,n}with weight function w, the n*n matrix A[aij][w(e)] is called the weight matrix of G. Suppose the weight matrix of a graph is as follows:

73A2337455432334554554

541543413Obtain an approximate optimal Hamiltonian cycle using the closest insertion method (Method 2),

Method 3 and the MST-DFS (depth-first search) method (Method 4).

5. In the graph below, we take a spanning tree T{{1,2},{1,5},{3,5},{4,5}}. (1) Let e{1,3}. What is the fundamental cycle C(e) with respect to T ? (2) Let f{4,5}. What is the fundamental cutset D(f) with respect to T ?