The Web Graph:
The web can be modeled as a directed graph where each web page is represented by a vertex and where an edge starts at the web page a and ends at the web page b if there is a link on a pointing to b. What do the in-degree and the out-degree of a vertex in the web graph represent?
For which values of n are these graphs bipartite?
(a) Kn (b) Cn (c) Wn (d) Qn
Copyright By PowCoder代写 加微信 powcoder
Suppose that a new company has five employees: Z, A, S, C, and M. Each employee will assume one of six responsibilities: planning, publicity, sales, marketing, devel- opment, and industry relations. Each employee is capable of doing one or more of these jobs: Z could do planning, sales, marketing, or industry relations; A could do planning or development; S could do publicity, sales, or industry relations; C could do planning, sales, or industry relations; and M could do planning, publicity, sales, or industry relations.
(a) Model the capabilities of these employees using a bipartite graph.
(b) Find an assigment of responsibilities such that each employee is assigned one responsibility.
1/3 CSI2101/UOttawa/MdH/W22
(c) Is the matching of responsibilities you found in part (b) a complete matching? Is it a maximum matching?
Determine whether an undirected graph is sparse, dense, or neither, and explain your answer, if it is used to model
(a) the street network in a city (where the vertices street intersections) . (b) buildings in a city are within two miles of one another.
(c) two people in the world are sibilings.
(d) two people work for the same company.
Find an adjacency matrix for each of these graphs.
(a) Kn (b) Cn (c) Wn (d) Km,n (e) Qn
2/3 CSI2101/UOttawa/MdH/W22
Determine whether the given pair of graphs is isomorphic.
Determine whether the given pair of graphs is isomorphic.
3/3 CSI2101/UOttawa/MdH/W22
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com