649 words - 3 pages

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?

I think {a}→{a,d,e,b},{i}→{i,h,e,j},{g}→{f,c,k,g}, where {x}→{T} is meant that we put a guard at x that covers all elements in T. Now we have to prove that we cant get what we desire with a smaller number of guards. Therefore we take 2 guards, and if not possible with 2 its not with one, as well. To cover the elements in the set ...view middle of the document...

It cant be since eliminating from a vertex with degree more than 1 will still result in a connected graph.

It can be verified that these sorts of graphs are tress, therefore the number of edges is n-1.

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.

Beginning with v we can continue to v on the cirle once again or to go to w and then back to v. Therefore beginning with v then we have an arbitrary number of whether v or wv. Therefore the generated sequences are of the form v(v)(v)..(wv)(wv)(wv)…(v)..v. Lets have k elements (v) is l elements (wv). Therefore totally we get k+1 as the length of the walk. So we can represent n as the sum of two non negative intergers:

n=0+n=1+(n-1)=2+(n-2)=⋯=n+0 so n+1 ways.

Exercise 11.2

6. Find all (loop-free) nonisomorphic undirected graphs with four vertices. How many of these graphs are connected?

11 graphs, 6 connected.

13. Let G be a cycle on n vertices. Prove that G is self complementary if and only if n _ 5.

We have e(C_n )= n→e(C_n )=(n(n-1))/2-n. As it is self complementary we get n=(n(n-1))/2-n→n(n-5)=0→n=5

Exercise 11.3

20. a) Find an Euler circuit for the graph in Fig. 11.44. b) If the edge {d, e} is removed from this graph, find an Euler trail for the resulting sub graph.

Edbadhiebcgkjgbfjife

Dabeihdbcgbfijgk

21. Determine the value(s) of n for which the complete graph Kn has an Euler circuit. For which n doesKn have an Euler trail but not an Euler circuit?

For an odd n each vertex on k{n} has even degree therefore k{n} has an Euller circuit, The graph h{2} has an Euler path however not an Euler circuit. For even values of n>2 K{n} has more than 2 vertices of odd degree, therefore k{n} has neither an Euler path nor an Euler circuit.

Draw inspiration from millions of example essays and papers