MATH: Discrete Mathematics and Graph Theory
数学图论代写 1.Complete the following definitions. (a) If v and w are vertices of a weighted graph, a walk from v to w is said to be minimal if ________
Practice Class 9 数学图论代写
1.Complete the following definitions.
(a) If v and w are vertices of a weighted graph, a walk from v to w is said to be minimal if ________
(b) A tree is ________
2.Consider the following weighted graph.
(a) A minimal walk from A to Z is ________
(b) A solution of the Chinese Postman Problem is ________
(c) A solution of the Travelling Salesman Problem is ________
3.Consider the following as weighted graphs where every edge has weight 1.
4.For each of the following statements, write T for true or F for false.
(a) For any vertex v of a weighted graph, d(v, v) = 0.
(b) For any vertices v, w of a weighted graph, d(v, w) = d(w, v).
(c) The weight of a solution of the Chinese Postman Problem in a weighted graph is at most the sum of the weights of the edges.
(d) The weight of a solution of the Travelling Salesman Problem in a weighted graph is at most the sum of the weights of the edges.
(e) The weight of a solution of the Travelling Salesman Problem in a weighted graph is at least 2d(v, w) for any v, w.
(f) If v is a vertex of a tree, T − v is a tree.
Practice Class 10 数学图论代写
1. Complete the following definition and theorem.
(a) If G is a connected graph, a spanning tree is a subgraph of G which ________
(b) If G is a connected graph with vertex set {1, 2, · · · ,n}, and M is the Laplacian matrix of G, the number of spanning trees of G equals ________
2.Consider the following tree.
When you have a choice, select vertices in alphabetical order.
(a) If you apply the Breadth-First Search Algorithm starting with the vertex a, the resulting order of the vertices is:________
(b) If you apply the Breadth-First Search Algorithm starting with the vertex f, the resulting order of the vertices is: ________
(c) If you apply the Depth-First Search Algorithm starting with the vertex a, the resulting order of the vertices is: ________
(d) If you apply the Depth-First Search Algorithm starting with the vertex f, the resulting order of the vertices is: ________
3.Without using the Matrix-Tree Theorem, find the number of spanning trees in the following graphs.
(a) P4
(b) C4
(c) K4
