Solution to Problem 1
Each page is a vertex in the web graph. Each weblink is an edge in the web graph. There are a set of edges from each page to other pages. The outdegree of a vertex is the number of weblinks on that page, and the in-degree of a vertex is the number of other pages that have a weblink to it.
Solution to Problem 2
(a) By the definition, Kn is a complete graph of n vertices. It is bipartite only for n = 2.
Copyright By PowCoder代写 加微信 powcoder
(b) By the definition, Cn is a cycle of n vertices, where n ≥ 3. It is bipartite when n is even. It is not bipartite when n is odd.
(c) By the definition, Wn is a wheel consists of Cn and a central vertex. As wheels contain triangles, Wn is not bipartite.
(d) By the definition, Qn is a graph that has 2n vertices to represent 2n bit strings of length n. It is bipartite for all n ≥ 1. We can divide its vertices into two disjoint sets: strings with odd number of 1s and strings with even number of 1s.
Solution to Problem 3
(a) We need to construct a bipartite graph with two set of vertices. The first set V1 to represent the employees and the second set V2 to represent the responsibilities. Thus, V1 = {Z,A,S,C,M} and
V2 ={planning,publicity,sales,marketing,development,industryrelations}. The overall set of vertices is V = V1 ∪ V2. The edges are as follows:
{Z, planning}, {Z, sales}, {Z, marketing}, {Z, industryrelations}, {A, planning}, {A, development}, {S, publicity}, {S, sales}, {S, industryrelations}, {C, planning}, {C, sales}, {C, industryrelations}, {M, planning},
{M, publicity}, {M, sales}, {M, industryrelations}.
(b) There are many possible assignments. If we assume that the same job will not be assigned to more than one employee, then a maximum matching can be obtained. Edges that share no endpoints are required to be selected. For example, {Z, planning}, {A, development}, {S, publicity}, {C, sales}, {M, industryrelations}.
(c) It is a complete matching from the set of employees to the set of jobs, but not the other way around. It is a maximum matching; because there were only five employees, no matching could have more than five edges. One responsibility, {marketing} remains unassigned since |V1| < |V2|.
Solution to Problem 4
(a) The density of G(V,E) is given by 2|E |
|V |(|V |−1)
The average degree of a vertex is 4, so |E| ≈ 2|V |.
2|E| ≈ 4|V| = 4 |V |(|V |−1) |V |(|V |−1) |V |−1
As the density approaches zero with the growth of |V |, it is a sparse graph.
(b) It will be a dense graph unless the city is really huge.
(c) The graph is sparse since only a few nighbours for each vertex.
(d) The graph is sparse since very few adjacent vertices with respect to the world population.
Solution to Problem 5
0 1 1 ... 1 (a)1 0 1 ... 1 ... ... ... ... ...
1 1 1 ... 0
0 1 0 ... 0 1
1 0 1 ... 0 0 (b)0 1 0 ... 0 0 ... ... ... ... ... ...
1 0 0 ... 1 0
(c) It has n + 1 rows. The final row is for the central vertex.
0 1 0 ... 0 1 1 0 1 ... 0 1 0 1 0 ... 0 1 ... ... ... ... ... ... 1 0 0 ... 1 1 1 1 1 ... 1 0
(d) The first m vertices are adjacent to none of the first m vertices but all of the last n, and vice versa,this matrix splits up into four pieces:
0 ... 0 1 ... 1 ... ... ... ... ... ... 0 ... 0 1 ... 1 1 ... 1 0 ... 0 ... ... ... ... ... ... 1 ... 1 0 ... 0
(e) It is defined recurisvely with the help of the identity matrix In.
0 1 Q1 = 1 0
Qn In Qn+1= In Qn
Solution to Problem 6
The given graphs are isomorphic. They can be simply obtained by adding an ad- ditional vertex to a K4. All conditions are mathced.
Solution to Problem 7
These graphs are not isomorphic since there is a mismatch of degrees. The second graph contains a vertex that has a degree of 4. However, none of the vertices on the first graph has a degree of 4.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com