Discrete and Combinatorial Mathematics (Week 4) Assignment

Discrete and Combinatorial Mathematics (Week 4) - Assignment Example 8.) Figure 11.10 shows an undirected graph representing a section of a department store. The vertices indicate where cashiers are located; the edges denote unblocked aisles between cashiers. The department store wants to set up a security system where (plainclothes) guards are placed at certain cashier locations so that each cashier either has a guard at his or her location or is only one aisle away from a cashier who has a guard. What is the smallest number of guards needed? 15.) For the undirected graph in Fig. 11.12, find and solve a recurrence relation for the number of closed v-v walks of length n ≠¥ 1, if we allow such a walk, in this case, to contain or consist of one or more loops. 22.) For the graph in Fig. 11.37(b), what is the smallest number of bridges that must be removed so that the resulting subgraph has an Euler trail but not an Euler circuit? Which bridge(s) should we remove? You are an electrical engineer designing a new integrated circuit involving potentially millions of components. How would you use graph theory to organize how many layers your chip must have to handle all of the interconnections, for example? Which properties of graphs come into play in such a circumstance? If the likelihood of the edge (v1, v2) is 50%, then there are equal chances that that edge will not be a section of the edge set. Similarly, for all the pair of vertices we can say that there is equal probability of having or not having an edge between those two. So, if there are n vertices in the vertex set then there can be maximum n "single connected component" (in which no edge is there) of that graph or minimum one connected component in which all the vertices are connected to each