91Ó°ÊÓ

A zoo wants to set up natural habitats in which to exhibit its animals. Unfortunately, some animals will eat some of the others when given the opportunity. How can a graph model and a coloring be used to determine the number of different habitats needed and the placement of the animals in these habitats?

Draw these graphs. $$ \begin{array}{llll}{\text { a) } K_{7}} & {\text { b) } K_{1,8}} & {\text { c) } K_{4,4}} \\ {\text { d) } C_{7}} & {\text { e) } W_{7}} & {\text { f) } Q_{4}}\end{array} $$

In a round-robin tournament the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles, and the Cardinals beat the Orioles. Model this outcome with a directed graph.

Construct the call graph for a set of seven telephone numbers \(555-0011,555-1221,555-1333,555-8888\) \(555-2222,555-0091,\) and \(555-1200\) if there were three calls from \(555-0011\) to \(555-8888\) and two calls from \(555-8888\) to \(555-0011\) , two calls from \(555-2222\) to \(555-0091,\) two calls from \(555-1221\) to each of the other numbers, and one call from \(555-1333\) to each of \(555-0011,555-1221,\) and \(555-1200\)

Show that the edge chromatic number of a graph must be at least as large as the maximum degree of a vertex of the graph.

Devise an algorithm for constructing Euler paths in directed graphs.

a) Explain how graphs can be used to model electronic mail messages in a network. Should the edges be directed or undirected? Should multiple edges be allowed? Should loops be allowed? b) Describe a graph that models the electronic mail sent in a network in a particular week.

Find the edge chromatic number of \(K_{n}\) when \(n\) is a positive integer.

Suppose that there are four employees in the computer support group of the School of Engineering of a large university. Each employee will be assigned to support one of four different areas: hardware, software, networking, and wireless. Suppose that Ping is qualified to support hardware, networking, and wireless; Quiggley is qualified to support software and networking; Ruiz is qualified to support networking and wireless, and Sitea is qualified to support hardware and software. a) Use a bipartite graph to model the four employees and their qualifications. b) Use Hall’s theorem to determine whether there is an assignment of employees to support areas so that each employee is assigned one area to support. c) If an assignment of employees to support areas so that each employee is assigned to one support area exists, find one.

Find a route with the least total airfare that visits each of the cities in this graph, where the weight on an edge is the least price available for a flight between the two cities.