Mth/221 Discrete Math for Information Technology Week 4

In: Computers and Technology

Submitted By achintmaxwell
Words 1159
Pages 5
* MTH/221 Week Four Individual problems:
Ch. 11 of Discrete and Combinatorial Mathematics
Exercise 11.1, problems 8, 11 , text-pg:519
Exercise 11.2, problems 1, 6, text-pg:528
Exercise 11.3, problems 5, 20 , text-pg:537
Exercise 11.4, problems 14 , text-pg:553
Exercise 11.5, problems 7 , text-pg:563
Ch. 12 of Discrete and Combinatorial Mathematics
Exercise 12.1, problems 11 , text-pg:585
Exercise 12.2, problems 6 , text-pg:604
Exercise 12.3, problems 2 , text-pg:609
Exercise 12.5, problems 3 , text-pg:621

Chapter 11

Exercise 11.1

Problem 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?

Figure 11.10

Problem 11:

Let G be a graph that satisfies the condition in Exercise 10.
(a) Must G be loop-free? (b) Could G be a multigraph? (c) If
G has n vertices, can we determine how many edges it has?

Exercise 11.2

Problem 1:

Let G be the undirected graph in Fig. 11.27(a).
a) How many connected subgraphs ofGhave four vertices
and include a cycle?

b) Describe the subgraph G1 (of G) in part (b) of the figure
first, as an induced subgraph and second, in terms of
deleting a vertex of G.

c) Describe the subgraphG2 (ofG) in part (c) of the figure
first, as an induced subgraph and second, in terms of the
deletion of vertices of G.

d) Draw the subgraph of G induced by the set of vertices
U _ {b, c, d, f, i, j}.

e) For the graph G, let the edge e _…...