#### Question Details

Application of Graph Theory to the Food Webs Case Study

- 5.1

In our Food Webs Case Study, how would be categorize the food webs graph and the competition graph? Â How does the intersection graph relate to the Food Webs Case Study? Â

PART III

GRAPH THEORY 224 13

Food Webs Author:

College. Robert A. McGuigan, Department of Mathematics, Westï¬eld State Prerequisites: The prerequisites for this chapter are basic concepts of graph

theory. See Sections 9.1 and 9.2 of Discrete Mathematics and Its Applications. Introduction

A food web is a directed graph modeling the predator-prey relationship in an

ecological community. We will use this directed graph to study the question of

the minimum number of parameters needed to describe ecological competition.

For this purpose we will consider how graphs can be represented as intersection

graphs of families of sets.

We will also investigate the axiomatic description of measures of status in

food webs. Competition

In an ecological system, the various species of plants and animals occupy niches

deï¬ned by the availability of resources. The resources might be deï¬ned in terms

of factors such as temperature, moisture, degree of acidity, amounts of nutrients,

225 226 Applications of Discrete Mathematics and so on.

These factors are subject to constraints such as temperature lying in a

certain range, pH lying within certain limits, etc. The combination of all these

constraints for a species then deï¬nes a region in n-dimensional Euclidean space,

where n is the number of factors. We can call this region the ecological niche

of the species in question.

For example, suppose we restrict ourselves to three factors, such as temperature, nutrients, and pH. Assume that the temperature must be between t1

and t2 degrees, the amount of nutrients between n1 and n2 and the pH between a1 and a2 . Then the ecological niche these deï¬ne occupies the region of

3-dimensional Euclidean space shown in Figure 1. Figure 1. An ecological niche. Euclidean space which has as dimensions the various factors of temperature, pH, etc., is called an ecological phase space. Generally, no two distinct

species will have the same ecological niche in phase space; however, two species

compete if their ecological niches have non-empty intersection. A basic principle of ecology, known as the principle of competitive exclusion, dictates

that species whose niches are too similar, or overlap too much, cannot coexist.

If the factors deï¬ning the niche are independent, then the niche in phase space

would be a box such as that in Figure 1. If the factors are not independent,

i.e. the level of one depends on levels of others, then the niche would be some

other type of set, e.g. convex, but not a box.

For example, consider the two factors temperature (t) and per cent humidity (h). We might have constraints such as: t must be between 0 and 100, and h

must be between 0 and 100t âˆ’ t2 . In this case temperature and humidity are

not independent; the possible values of h depend on the values of t. The region

in two-dimensional space deï¬ned by these constraints is not a rectangle.

Our discussion of ecological communities and related concepts such as Chapter 13 Food Webs 227 species, food webs, and competition will be somewhat oversimpliï¬ed in order

to make a brief presentation possible. Interested readers should consult reference [1] for an in-depth treatment of these topics. Our mathematical treatment

follows that of reference [6]. Food Webs

It may be diï¬ƒcult to know all the factors which determine an ecological niche,

and some factors may be relatively unimportant. Hence it is useful to start with

the concept of competition and try to ï¬nd the minimum number of dimensions

necessary for a phase space in which competition can be represented by niche

overlap.

One approach to this question is to consider the notion of the food web of

an ecological community.

Deï¬nition 1

A food web of an ecological community is a directed graph

with a vertex for each species in the community and a directed edge from the

vertex representing species A to the vertex representing species B if and only

if A preys on B.

Figure 2 shows a simple food web for a community of seven species: robin,

fox, grasshopper, raccoon, salamander, milksnake, and toad. Figure 2.

A simple food web. We can deï¬ne competition using the food web. Two species compete if and

only if they have a common prey. Thus, in the example of Figure 2, raccoon and

fox compete (since robin is a common prey), milksnake and raccoon compete, 228 Applications of Discrete Mathematics while salamander and robin do not compete. We use this competition relation

to deï¬ne a graph called the competition graph. Deï¬nition 2

The competition graph of a food web is a simple graph with a

vertex for each species. Two vertices are joined by an (undirected) edge if and

only if the species they represent have a common prey. Example 1

Solution: Find the competition graph for the food web of Figure 2.

The competition graph for this food web is shown in Figure 3. Figure 3. A competition graph. To represent the competition relation in phase space we want to assign to

each vertex of the competition graph a subset of Euclidean space of some dimension in such a way that two vertices are joined by an edge in the competition

graph if and only if the sets assigned to these vertices have non-empty intersection. Figure 4 shows a representation of the competition graph of Figure 3,

using an interval for each vertex. We have thus represented the competition

graph using only one dimension. Figure 4. Interval representation of a competition graph. We can now state a general mathematical problem, but ï¬rst we need to

develop some terminology. Chapter 13 Food Webs 229 Deï¬nition 3

A graph is an intersection graph for a family of sets if each

vertex is assigned a set in such a way that two vertices are joined by an edge if

and only if the corresponding sets have non-empty intersection. Deï¬nition 4

A graph is called an interval graph if it is the intersection

graph for a family of closed intervals. Our goal is the representation of competition graphs of families of sets

in Euclidean n-space. Clearly the simplest case would be that of competition

graphs that are interval graphs. This would mean that only one ecological

factor is necessary to describe niche overlap. Example 2

Find the interval graph for the family of closed intervals A =

[1, 3], B = [2, 6], C = [5, 8], D = [4, 5].

Solution:

Figure 5. We use the deï¬nition of intersection graph to obtain the graph of Figure 5.

Example 3

graph. An intersection graph. Prove that the 4-cycle graph C4 of Figure 6 is not an interval Solution: The proof depends on the order properties of the real numbers. Let

the interval corresponding to vertex n be [nl , nr ]. Since the intervals for vertices

1 and 2 overlap, we must have either 1l â‰¤ 2l â‰¤ 1r â‰¤ 2r or 2l â‰¤ 1l â‰¤ 2r â‰¤ 1r ,

Assume for speciï¬city that 1l â‰¤ 2l â‰¤ 1r â‰¤ 2r . The argument for the other case

is analogous.

Since the interval for vertex 3 must meet that for vertex 2 and must not

meet that for vertex 1, we must have 1l â‰¤ 2l â‰¤ 1r < 3l â‰¤ 2r . Now the interval

for vertex 4 must meet those for both vertices 1 and 3, so we have to have

1l â‰¤ 4l â‰¤ 1r and 3l â‰¤ 4r â‰¤ 3r since interval 1 lies entirely to the left of interval

3. However, since 2l â‰¤ 1r < 3l â‰¤ 2r , the intervals for vertices 2 and 4 overlap,

which is forbidden. 230 Applications of Discrete Mathematics Figure 6. A graph that is not an interval graph. The 4-cycle can, however, be represented as the intersection graph of a

family of boxes in Euclidean 2-space, as shown in Figure 7.

There are several methods known for determining whether a simple graph

is an interval graph. A detailed discussion of this topic may be found in Robertsâ€™

book [6]. We simply state the characterization due to Gilmore and Hoï¬€man

[3] without proof. Before the characterization can be stated, we need some

deï¬nitions. Figure 7. A box representation. Deï¬nition 5

A graph H is a generated subgraph of a graph G if the vertices

of H are a subset of the vertices of G and vertices in H are adjacent in H if

and only if they are adjacent in G. Deï¬nition 6

The complement of a graph G is the graph G where the vertices

of G are the vertices of G, and two vertices in G are adjacent if and only if they

are not adjacent in G. Deï¬nition 7

An orientation of a graph G is an assignment of a direction to

each edge in G (which makes G into a directed graph).

An orientation is transitive if whenever (u, v) and (v, w) are directed edges,

then (u, w) is a directed edge. Chapter 13 Food Webs 231 The characterization due to Gilmore and Hoï¬€man is given by the following

theorem.

Theorem 1

A graph G is an interval graph if and only if it satisï¬es the

following two conditions:

(i) The four-cycle C4 is not a generated subgraph of G,

(ii) The complement of G is transitively orientable.

Our goal in our study of ecological competition is the representation of

niches in Euclidean space and competition by niche overlap. It seems desirable

in an ideal representation that the factors determining the dimension of the ecological phase space would be independent and the niches would be represented

as â€œboxesâ€, or Cartesian products of intervals. This leads us to the next part

of this discussion, namely, when can we represent a graph as the intersection

graph of a family of boxes in n-space. Boxicity

Deï¬nition 8

The boxicity of a graph G is the smallest n such that G is the

intersection graph of a family of boxes in Euclidean n-space.

Note that an interval graph is simply a graph with boxicity equal to 1.

It is not entirely clear that every simple graph has a boxicity. The following

theorem resolves this diï¬ƒculty.

Theorem 2

Every graph G with n vertices is the intersection graph of a

family of boxes in Euclidean n-space.

Proof: Let v1 , v2 , . . . , vn be the vertices of G. A box in Euclidean n-dimensional space is the set of all n-tuples of real numbers (x1 , x2 , . . . , xn ) such that

each xi is in some closed interval Ii . Now, for each k = 1 . . . , n and each vertex

vi , deï¬ne closed intervals Ik (vi ) as follows.

âŽ§

âŽª [0, 1] if i = k

âŽ¨

Ik (vi ) = [1, 2] if i = k and {vi , vk } is an edge in G

âŽª

âŽ©

[2, 3] if i = k and {vi , vk } is not an edge in G.

For each vertex vi deï¬ne a box B(vi ) in Euclidean n-space by

B(vi ) = {(x1 , x2 , . . . , xn ) | xj âˆˆ Ij (vi ) for j = 1, . . . , n}. 232 Applications of Discrete Mathematics Thus, the box B(vi ) corresponding to vi is the Cartesian product of the intervals

Ij (vi ) for j = 1, . . . , n.

Now we show that vi and vj are adjacent in G if and only if B(vi )âˆ©B(vj ) =

âˆ…. Thus the graph G is the intersection graph of the family of boxes B(vi ). First,

suppose that there is an edge joining vl and vm . If k is diï¬€erent from both l and

m, then according to the deï¬nition, Ik (vl ) âˆ© Ik (vm ) is [1, 2] âˆ© [1, 2], [1, 2] âˆ© [2, 3],

or [2, 3] âˆ© [2, 3]. In any case we have Ik (vl ) âˆ© Ik (vm ) = âˆ…. If k=l or k=m then

Ik (vl ) âˆ© Ik (vm ) = [1, 2] âˆ© [0, 1] = âˆ…. So, if there is an edge joining ve and vm ,

then for all k, Ik (vl ) âˆ© Ik (vm ) = âˆ…. Hence B(vl ) âˆ© B(vm ) = âˆ….

Now suppose that B(vl ) âˆ© B(vm ) = âˆ…. Then for each k from l to n, Ik (vl ) âˆ©

Ik (vm ) = âˆ…. Set k = l then Il (vl ) = [0, 1] and Il (vm ) must be [1, 2] for the

intersection to be nonempty. By deï¬nition of Il (vm ), vl and vm are adjacent.

Thus G is the intersection graph of the family of boxes B(vi ). This theorem shows that boxicity is well-deï¬ned. Unfortunately, there is

no eï¬ƒcient algorithm known for determining the boxicity of a general graph.

There is no characterization known for graphs of any speciï¬c boxicity other

than 1.

In fact, there are not many general classes of graphs for which the boxicity

is known. It is not hard to see that the boxicity of the n-cycle Cn is 2 for n = 4

or larger, and this is left as Exercise 6. Another general class of graphs for which

the boxicity is known is the complete p-partite graphs. These are the graphs

Kn1 ,n2 ,...,np deï¬ned as follows: there are n1 + Â· Â· Â· + np vertices partitioned into

p classes, where the ith class has ni vertices. Within a class no vertices are

adjacent, and every vertex in any class is adjacent to all vertices in the other

classes. Roberts [6] showed that the boxicity of Kn1 ,...,np is equal to the number

of ni that are larger than 1.

One result which helps somewhat in calculating the boxicity of a graph is

due to Gabai [2]. This theorem depends on the concept of independence of a

set of edges. Deï¬nition 9

in common. A set of edges in a graph is independent if they have no vertices Gabaiâ€™s theorem [2] is the following, stated without proof.

Theorem 3

Let G be a simple graph. If the maximum size of an independent

set of edges of G is k, then G has boxicity less than or equal to k. Also, if G

has a generated subgraph consisting of k independent edges then the boxicity

of G is greater than or equal to k. Chapter 13 Food Webs 233 Gabaiâ€™s theorem is useful in determining the boxicity of relatively small

graphs and for certain families. In any case it limits the amount of trial and

error needed.

In our study of competition we search for the representation of the competition graph of a food web as the intersection graph of a family of sets in

Euclidean n-space for some n. As a consequence of the theorem proved above,

this representation is always possible. Furthermore, we can use the boxicity

of the competition graph as an indicator of the minimum number of factors

essential for describing competition in the community. Cohen [1] has studied

more than 30 single-habitat food webs published in the ecological literature and

has found that the competition graphs of all of them are interval graphs. That

is, in all cases one dimension suï¬ƒces to represent competition by niche overlap.

It is not known whether this is a general law of ecology, but it does raise many

interesting questions. In some single-habitat communities a single dimension

for the niche space can be identiï¬ed. It may be some obviously linear factor

such as temperature, body length or depth in water. However, it may well be

that more than one single dimension will work. And, of course, we canâ€™t expect

the single-niche dimension to be the same from community to community.

Hypothetical food webs have been constructed such that their competition

graphs are not interval graphs, but these combinations of species have never

been observed in nature at the same time and place.

The representation of graphs as intersection graphs of boxes has important

applications in ecology, as we have seen. Applications to such diverse ï¬elds

as archaeology and automobile traï¬ƒc control have also been investigated (see

reference [6]). We conclude with an additional application of food webs. Trophic Status

In the study of social systems it is often useful to measure the status of an

individual in an organization. Harary [4] ï¬rst introduced the idea of measuring

the status of a species in a food web. In ecology this status is usually called the

trophic level and is helpful in assessing the complexity and diversity of a web.

The idea is that a web with many species at each trophic level has a high degree

of complexity. In ecology it is generally thought that more complex ecosystems

are more stable. In this section we study the question of how trophic status

can be deï¬ned in a food web.

If the food web is simply a directed path (a food chain) then it is easy to

deï¬ne trophic status; just follow the order of the species in the chain. Some

other structures also allow for an easy deï¬nition of trophic status. For example,

we might think of species with no outgoing edges as being at the bottom of the

web. Suppose that for every vertex, all directed paths to vertices at the bottom

have the same length. Examples of such webs are given in Figure 8. 234 Applications of Discrete Mathematics Figure 8. Graphs of two food webs. In this kind of web, the trophic status of a vertex can be deï¬ned as the

length of a directed path from the vertex to the bottom.

In general it is diï¬ƒcult to deï¬ne trophic status in complicated food webs.

Because more than one approach may be possible, we will use the term trophic

status in this context rather than the term trophic level which is well-known in

the context of food chains. Our goal is to investigate how trophic status could

be measured rather than to develop a unique possibility.

To start, we need some basic assumptions about food webs. In particular,

we assume that our food web is acyclic, i.e. that the directed graph has no

cycles. Thus, there are no species s1 , . . . , sn such that for i = 1, . . . , n âˆ’ 1, si

preys on si+1 and sn preys on s1 . In particular there are no two species such

that each preys on the other. Thus, the prey relationship is asymmetric.

We will take an axiomatic approach to deï¬ning measures of trophic status.

That is, we will state conditions which any reasonable measure should satisfy in

the form of axioms. A measure will then be acceptable if and only if it satisï¬es

the axioms. The axioms will deï¬ne an ideal model for the concept of measure

of trophic status. Our approach will follow that of Harary [4] and Kemeny

and Snell [5], who work with status in an organization, and the treatment in

Roberts [6], which is more detailed. Deï¬nition 10

In a food web a species v is a direct prey of a species u if

there is a directed edge from u to v. A species v is an indirect prey of u if there

is a directed path from u to v.

It could well happen that there are two species u and v neither of which is

an indirect prey of the other.

Deï¬nition 11

If v is a direct or indirect prey of u, then the level of v relative

to u is the length of the shortest directed path from u to v. Chapter 13 Food Webs 235 We can now state some reasonable axioms for measures of trophic status.

Let tW (u) be the measure of status in the food web W . The axioms are:

Axiom 1: If a species u has no prey then tW (u) = 0.

Axiom 2: If, without otherwise changing the food web, we add a

new vertex which is a direct prey of u to get a new web W , then

tW (u) > tW (u).

Axiom 3: Suppose the web W is changed by adding edges and/or

vertices in such a way that the level of some direct or indirect prey of

u is increased, and no direct or indirect prey of u has its level relative

to u decreased. If W is the new web, then tW (u) > tW (u).

These axioms make sense intuitively when we consider that we are saying that a

species with no prey is at the bottom level (Axiom 1), that if the number of prey

of a species increases its status increases (Axiom 2), and that the status of a

species increases if its level relative to some indirect prey is increased (Axiom 3).

There is a measure of status which satisï¬es the axioms. Harary [4] suggested the following deï¬nition.

Deï¬nition 12

k, then If a species u has nk species at level k relative to u for each hW (u) = knk .

k Theorem 4 The measure hW (u) satisï¬es Axioms 1-3. Proof: If u has no prey, then hW (u) = 0 because all the nk = 0.

If we add a direct prey for u, then n1 increases by 1, so the sum deï¬ning

hW (u) also increases.

Likewise, if some direct or indirect prey of u at level k relative to u is

moved to level k + n below u and no other direct or indirect prey of u has its

level decreased, the sum for h increases by at least kn, verifying Axiom 3.

Kemeny and Snell [5] also show that if tW is any other measure of trophic

status satisfying Axioms 1â€“3 and having all its values nonnegative, then for all

species u, tW (u) â‰¥ hW (u). Thus, h is in a sense a minimal measure of trophic

status.

While h satisï¬es our axioms it fails to have other desirable properties. For

example, it seems reasonable that if tW is a measure of trophic status and v is

a direct or indirect prey of u, then

tW (u) â‰¥ tW (v). 236 Applications of Discrete Mathematics The measure h does not have this property. Figure 9 shows an example of

an acyclic food web W with two vertices u and v for which v is a direct prey

of u but hW (v) > hW (u). Figure 9. An acyclic food web. In this example, hW (u) = 6 and hW (v) = 8.

The problem we have found can be avoided if we modify our deï¬nition of

level of one species relative to another: If v is a direct or indirect prey of u,

then the level of v relative to u is the length of the longest directed path from u

to v.

It is not hard to show that if h is deï¬ned by the same formula as before, but

using the new deï¬nition of level, then h satisï¬es Axioms 1â€“3 as well as having

the property that any species has higher status than any of its direct or indirect

prey (see reference [5]). The problem we encountered here demonstrates one of

the diï¬ƒculties with the axiomatic approach. Our problem lay in the deï¬nition

of level and this would not show up in any consideration of the reasonableness of

the axioms. Ideally, all of the terms used in specifying the axioms should either

be left undeï¬ned or else be checked for â€œreasonablenessâ€, just as the axioms

themselves are. In this light we would also have to examine the new deï¬nition

of level.

Without referring to the notion of relative level in a food web, perhaps the

only requirement we can state for a measure of trophic status is that if there is

a directed path from u to v, then tW (u) â‰¥ tW (v).

There are other ways to investigate complexity of food webs and relative

importance of species in food webs. General methods of measuring complexity

in graphs can be applied to competition graphs and food webs. For example,

such ideas as the number of edges divided by the number of vertices, and the

average out-degree and average in-degree might be useful. The importance, or

criticality, of a species in a food web could be studied by investigating what

happens to the web when the species is deleted from the web. For example, if

the web is disconnected when a species is removed that would indicated a high

level of importance. More information on these questions can be found in [6]. Chapter 13 Food Webs 237 Suggested Readings

1. J. Cohen, Food Webs and Niche Space, Princeton University Press, Princeton, N.J., 1978.

2. H. Gabai, â€œN -dimensional Interval Graphsâ€, mimeographed, York College,

C.U.N.Y., New York, 1974.

3. P. Gilmore and A. Hoï¬€man, â€œA Characterization of Comparability Graphs

and Interval Graphsâ€, Canadian J. Math., Vol. 16, 1964, pp. 539â€“548.

4. F. Harary, â€œStatus and Contrastatusâ€, Sociometry, Vol. 22, 1959, pp. 23â€“

43.

5. J. Kemeny and J. Snell, Mathematical Models in the Social Sciences, MIT

Press, Cambridge, MA, 1972.

6. F. Roberts, Discrete Mathematical Models with Applications to Social, Biological, and Environmental Problems, Prentice Hall, Upper Saddle River,

N.J., 1976. Exercises

1. Find the ecological niche in Euclidean space of the appropriate dimensions

in each case.

a) Temperature between 10o F and 90o F ; nitrate concentration in soil

between 1% and 5%.

b) Carbon monoxide in atmosphere between 0% and 1%; relative humidity between 20% and 100%; nitrogen gas content in atmosphere between

15% and 20%.

2. Find the competition graph for the given food webs in each case:

a)

b) 238 Applications of Discrete Mathematics 3. Find a representation for each graph as the intersection graph of a family

of rectangles in the plane.

a)

b) 4. Find a representation for each graph as the intersection graph of a family

of intervals on the line.

a) b) 5. Show that if a graph G is an interval graph then it satisï¬es the conditions of

the theorem of Gilmore and Hoï¬€man characterizing interval graphs. Hint:

For an interval representation let I(v) be the interval assigned to the vertex v. If u and v are adjacent in G, make the orientation (u, v) if and only

if I(u) lies entirely to the left of I(v).

6. Show that if Cn is the cycle of length n, then the boxicity of Cn is 1 for

n = 3 and 2 for n â‰¥ 4.

7. According to Robertsâ€™ result quoted in the text, the boxicity of the complete bipartite graph K(3, 3) is 2. Find a representation of K(3, 3) as the

intersection graph of a family of boxes in the plane.

8. Let Q3 be the graph formed by the edges and corners of a cube in Euclidean

three space. Is Q3 an interval graph? Why? Determine the boxicity of Q3 .

9. A food web for some species in the Strait of Georgia, B.C. ([1], page 165) is

given by the following table. The numbers atop columns indicate predator

(consuming) species and those at the left of rows indicate prey (consumed)

species. An entry 1 indicates that the predator in that column consumes

the prey for that row, an entry 0 that it does not. The key identiï¬es the

various species. Chapter 13 1

2

3

4

5

6

7 2 3 4 5 1

1

0

1

0

0 0

0

0

0

1

0 0

0

1

0

1

1 0

0

0

1

0

0 Food Webs 239 Key 0

0

0

0

1

1 1.

2.

3.

4.

5.

6.

7. Juvenile pink salmon

P. minutus

Calanus and Euphausiid furcilia

Euphausiid eggs

Euphausiids

Chaetoceros socialis and debilis

mu-ï¬‚agellates a) Construct a directed graph for this food web.

b) Construct the competition graph for this food web.

c) Find a set of intervals on the real line such that the graph of part b)

is the intersection graph of this family of intervals.

10. Repeat Exercise 9 for the following food web for a community of pine feeders

[1], p.148. 2 3

1

2

3

4

5

8

9

10 4 5 6 7...

**Solution details:**

Answered

QUALITY

Approved

ANSWER RATING

This question was answered on: * Sep 05, 2019 *

* * Solution~000200021908.zip (25.37 KB)

This attachment is locked

We have a ready expert answer for this paper which you can use for in-depth understanding, research editing or paraphrasing. You can buy it or order for a fresh, original and plagiarism-free solution (Deadline assured. Flexible pricing. TurnItIn Report provided)

Please Enter Your Payment Email Address To Receive Solution.

##### Pay using PayPal (No PayPal account Required) or your credit card . All your purchases are securely protected by .

#### About this Question

STATUSAnswered

QUALITYApproved

DATE ANSWEREDSep 05, 2019

EXPERTTutor

ANSWER RATING

#### GET INSTANT HELP/h4>

We have top-notch tutors who can do your essay/homework for you at a reasonable cost and then you can simply use that essay as a template to build your own arguments.

You can also use these solutions:

- As a reference for in-depth understanding of the subject.
- As a source of ideas / reasoning for your own research (if properly referenced)
- For editing and paraphrasing (check your institution's definition of plagiarism and recommended paraphrase).

#### NEW ASSIGNMENT HELP?

### Order New Solution. Quick Turnaround

Click on the button below in order to Order for a New, Original and High-Quality Essay Solutions.
New orders are original solutions *and precise to your writing instruction requirements. Place a New Order using the button below.*

WE GUARANTEE, THAT YOUR PAPER WILL BE WRITTEN FROM SCRATCH AND WITHIN YOUR SET DEADLINE.