13
Food Webs
GRAPH THEORY
Author:    Robert A. McGuigan, Department of Mathematics, Westfield State
Prerequisites: The prerequisites for this chapter are basic concepts of graph I In nry. See, for example, Sections 7.1 and 7.2 of Discrete Mathematics and Its Applications, Second Edition, by Kenneth H. Rosen.
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. I < tr 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 defined by the availability of resources. The resources might be denned in terms
225
:>."6
Application;: ot l)i;.i into M.xthom.ttii
of factors such as temperature, moisture, degrei of nudity, i.....units of nut rieut.h,
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 defines 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 ti and t2 degrees, the amount of nutrients between ni and ri2 and the pH between ai and 02. Then the ecological niche these define occupies the region of 3-dimensional Euclidean space shown in Figure 1.
nutrients
t, t2 temperature
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 defining 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 1002 — t1. 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 defined by these constraints is not a rectangle.
i ii.ipini 1.1 1 ()o</ Wii/i.'. 227
Our disciiNHK.....I rci 1I1 inn »1 • <it 11111111111     and related concepts such as
pedes, food webs, and mini., hi.....      will he somewhat oversimplified in order
I., make a brief presentation possible. Interested readers should consult refer-
...... 111 for an in-depth treatment of these topics. Our mathematical treatment
I'nllows that of reference [6].
Food Webs
It may be difficult to know all the factors which determine an ecological niche, hi.I some factors may be relatively unimportant. Hence it is useful to start with 1 In concept of competition and try to find the minimum number of dimensions 11. . rssary for a phase space in which competition can be represented by niche . iverlap.
One approach to this question is to consider the notion of the food web of mi ecological community.
Definition 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.
Robin
Raccoon
Grasshopper
Figure 2.
Fox
t Toad
A simple food web.
We can define 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
IK'ti Applications ol 1ioU> M.ilhoin.ili, ■.
Chapter 13 Food Wöbs 229
fox compete (since robin is a common prey), milkmiaki nti.l raccoon coinpel.e,
while salamander and robin do not compete. We uw Uiím <•.....petition relat.....
to define a graph called the competition graph.
Definition 3      A Kr»|>h ih an iidcrsvclion graph for a family of sets if each i i i,x in assigned a set in kiic.1i a way that two vertices are joined by an edge if Mid only if the corresponding sets have non-empty intersection. □
Definition 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      Find the competition graph for the food web of Figure 2. Solution:    The competition graph for this food web is shown in Figure 3. □
• Robin
Raccoon
Salamander
Grasshopper
Toad
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.
Robin
Grasshopper
Raccoon
Salamander
Milksnake
Fox
Toad
Figure 4.   Interval representation of a competition graph.
We can now state a general mathematical problem, but first we need to develop some terminology.
Definition 4 A graph is called an interval graph if it is the intersection Itrnph for a family of closed intervals. □
Our goal is the representation of competition graphs of families of sets in Kuclidean n-space. Clearly the simplest case would be that of competition naphs 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], £» = [4,5].
Solution: We use the definition of intersection graph to obtain the graph of Figure 5. Q
Figure 5.   An intersection graph.
Example 3 Prove that the 4-cycle graph C4 of Figure 6 is not an interval graph.
Solution: The proof depends on the order properties of the real numbers. Let the interval corresponding to vertex n be [n(, nr]. Since the intervals for vertices 1 and 2 overlap, we must have either 1; < 2; < lr < 2r or 2/ < 1; < 2r < lr, Assume for specificity that 1, < 2, < lr < 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 1, < 2, < lr < 3, < 2r. Now the interval for vertex 4 must meet those for both vertices 1 and 3, so we have to have If < 4* < lr and 3; < 4r < 3r since interval 1 lies entirely to the left of interval 3. However, since 2, < lr < 3; < 2r, the intervals for vertices 2 and 4 overlap, which is forbidden.
:kio
Application;, ol Dint into M.ilhuni n„
Figure 6.   A graph that is not an interval graph.
The 4-cycle can, however, be represented as the intersection grapli of n 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 Hoffman [3] without proof. Before the characterization can be stated, we need some definitions.
I Ik- cliiinicl.-ri/jilK.n <lm In < iilnmi.....I II• <tl■ 11<......givi-n l>y Un- following
I Ik i ilTin.
Theorem 1      A graph 0 in an interval graph if and only if it satisfies the
following two conditions:
(i) The four-cycle C4 is not a generated subgraph of G,
(li) The complement of G is transitively orientable. ■
Our goal in our study of ecological competition is the representation of nil lies 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 ns "boxes", or Cartesian products of intervals. This leads us to the next part ■ if this discussion, namely, when can we represent a graph as the intersection graph of a family of boxes in n-space.
Figure 7.    A box representation.
Definition 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. □
Definition 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. □
Definition 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. ^
Boxicity
Definition 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 difficulty.
Theorem 2 Every graph G with n vertices is the intersection graph of a family of boxes in Euclidean n-space.
Proof: Let Wi,W2i"-»"n be the vertices of G. A box in Euclidean n-dimen-sional space is the set of all n-tuples of real numbers (xi,!?,... ,xn) such that each Xi is in some closed interval Now, for each k = I... ,n and each vertex Vi, define closed intervals as follows.
' [0,1]   if i = k Ik(vi) = < [1,2]   if i ^ k and {«,-, vt} is an edge in G
[2,3]   if i ^ k and {vi, t^} is not an edge in G. For each vertex u; define a box B(v{) in Euclidean n-space by B(vi) = {(xi,x2,...,xn) \xj € Ij(vi) for j =s l,...,n}.
232       Applications ol Discrolo Mathematics
Thus, the box B(v,) corresponding to v, is the Cartesian product of the intervalu Ij{vi) for j= l,...,n.
Now we show that t;,- and Vj are adjacent in G if and only if B(ví)C\B(vj) -jt ill. Thus the graph G is the intersection graph of the family of boxes B(ví). Firil suppose that there is an edge joining i/; and vm. U k is different from both / and m, then according to the definition, h(vi) l~l h{vm) is [1,2] D [1,2], [1,2] fl [2, 3], or [2,3] fl [2,3]. In any case we have h(vi) n h(vm) # 0- If k=l or k=m then h(vi) fl h(vm) = [1,2] fl [0,1] ^ 0. So, if there is an edge joining ve and r,„ then for all fc, n J*(t;m) ^ 0. Hence £(<;,) D B(vm) ^ 0.
Now suppose that B(vt)r\B(vm) ^ 0. Then for each k from 1 to n, 0 /ib(vm) ^ 0- Set    = / then = [0,1] and It{vm) must be [1,2] for thl
intersection to be nonempty. By definition of Ii(vm), vi and vm are adjaceni Thus G is the intersection graph of the family of boxes B(ví). ■
This theorem shows that boxicity is well-defined. Unfortunately, there \» no efficient algorithm known for determining the boxicity of a general graph There is no characterization known for graphs of any specific 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 C„ is 2 for n = 1 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 A'n,,n3,...,np defined as follows: there are n\ + ■ ■ ■ + np vertices partitioned into p classes, where the ith class has n,- 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 Kni.....„p is equal to the number
of rii 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.
Chapt&r 13 Food Wöbs
Definition 9 A set of edges in a graph is independent if they h in common.
Gabai's theorem [2] is the following, stated without proof.
ave no vertices □
Theorem 3 Let G be a simple graph. If the maximum size of an independent set of edges of G is *, then G has boxicity less than or equal to *. Also f
of G^freTlt r11?^8 °f * indePendent edges then the boxicity
ot G is greater than or equal to k. JL
(Juliai's theorem in iim«-I'iiI in determining the boxicity of relatively small i i ipliH and for certain families. In any case it limits the amount of trial and
.....i needed.
In our study of competition we search for the representation of the com-pi hi ion graph of a food web as the intersection graph of a family of sets in
I uclidean 7i-space for some n. As a consequence of the theorem proved above, i In, representation is always possible. Furthermore, we can use the boxicity Of the competition graph as an indicator of the minimum number of factors
ii ntial for describing competition in the community. Cohen [1] has studied
......e than 30 single-habitat food webs published in the ecological literature and
lie. found that the competition graphs of all of them are interval graphs. That i . in all cases one dimension suffices to represent competition by niche overlap.
II ia 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 l"i the niche space can be identified. It may be some obviously linear factor
in Ii 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 i lie 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 fields as archaeology and automobile traffic 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] first 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 defined in a food web.
If the food web is simply a directed path (a food chain) then it is easy to define trophic status; just follow the order of the species in the chain. Some other structures also allow for an easy definition 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 arc given m lij'.urr H.
(Uuploi M   / (>(>(< Wii/w
235
Figure 8.   Graphs of two food webs.
In this kind of web, the trophic status of a vertex can be defined as the length of a directed path from the vertex to the bottom.
In general it is difficult to define 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 si,..., sn such that for i = 1,..., n — 1, Bi preys on s;+i and sn preys on «i. 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 defining 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 satisfies the axioms. The axioms will define 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.
Definition 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.
Definition 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.
We can now state noiih reasonable axioms for measures of trophic status. I ■ i /iv (i«) !>'• the measure of status in the food web W. The axioms are: \ x ii mi 1: If a species u has no prey then (iv(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 t\v>(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 ii is increased, and no direct or indirect prey of u has its level relative Id u decreased. If W is the new web, then <w(u) > <w(u). I lii-se axioms make sense intuitively when we consider that we are saying that a ics with no prey is at the bottom level (Axiom 1), that if the number of prey ■ i a species increases its status increases (Axiom 2), and that the status of a ipecies increases if its level relative to some indirect prey is increased (Axiom 3).
There is a measure of status which satisfies the axioms. Harary [4] suggested the following definition.
Definition 12 If a species u has species at level k relative to u for each *, then
hw(u) = ^2 krik- □
Theorem 4      The measure h\y(u) satisfies Axioms 1-3.
Proof:  If u has no prey, then hw(u) — 0 because all the     = 0.
If we add a direct prey for u, then n\ increases by 1, so the sum defining liw(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, <w(u) > hw(u). Thus, h is in a sense a minimal measure of trophic status.
While h satisfies 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).
V/i>/. .Mom. ol Hi:, iiilo
Chapter 13 Food W»b$ 237
The measure /; docs not have this proper!.} I ir.nn I) ilrnvvs an example ol an acyclic food web W with two vertices 11. and v l"i wlin li n is a direct prt»y 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 definition of level of one species relative to another: If v is a direct or indirect prey of u, then the 7eve7 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 defined by the same formula as before, but using the new definition of level, then h satisfies 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 difficulties with the axiomatic approach. Our problem lay in the definition 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 undefined or else be checked for "reasonableness", just as the axioms themselves are. In this light we would also have to examine the new definition 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].
Suggested Readings
I. J, Cohen, Food Webs and Niche Space, Princeton University Press, 1978. '   II (iabai, 'W-dimensional Interval Graphs", mimeographed, York College, C.U.N.Y., New York, 1974.
3. P. Gilmore and A. Hoffman, "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.
C. F. Roberts, Discrete Mathematical Models, Prentice-Hall, 1976.
Exercises
1. Find the ecological niche in Euclidean space of the appropriate dimensions in each case.
a) Temperature between 10"f and 90°.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)
. \ M        Application* ot Dincmta i
3. Find a representation for each gr;iph ii.m Ih< nil' r..-< turn graph of n I'anil of rectangles in the plane.
a) b) a_ b
Id
4. Find a representation for each graph as the intersection graph of a family of intervals on the line.
a)
5. Show that if a graph G is an interval graph then it satisfies the conditions of the theorem of Gilmore and Hoffman 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,t>) 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 A'(3,3) is 2. Find a representation of A'(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 identifies the various species.
:>39
12   3 4
Key
2
3
4
5 G 7
1 1
0
1 0 0
0
0
1
0
1 1
0 1. Juvenile pink salmon
0 2. P. minutus
0 3. Calanus and Euphausiid furcilia
0 4. Euphausiid eggs
1 5. Euphausiids 1 6. Chaetoceros socialis and debilis
7. mu-flagellates a) Construct a directed graph for this food web. I)) 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.
Repeat Exercise 9 for the following food web for a community of pine feeders [I], P-148.
Key
1. Pine
2. Caterpillars, moths
3. Aphids, secretion
4. Digger wasps
5. Ichneumons
6. Bugs
7. Ants
8. Syrphids
9. Ladybugs 10. Spiders
11. Give an example of a food web which has two species, neither of which is a direct or indirect prey of the other.
12. In the section on trophic status two different definitions of relative level were given and two corresponding versions of the measure of trophic status h\y were also given. Calculate the trophic status of each vertex in each of the following food webs using both versions of h.
	2	3	4	5	6	7	8	9	10
1	1	1	0	0	0	0	0	0	0
2	0	0	1	1	0	0	0	0	0
3	0	0	1	0	1	1	1	1	1
4	0	0	0	0	0	0	0	0	1
5	0	0	0	0	0	0	0	0	1
8	0	0	0	0	0	0	0	0	1
9	0	0	0	0	0	0	0	0	1
10	0	0	1	0	0	0	0	0	0
240
Applications ol UikciiiIii M.illunn.iti, ■.
14
Applications of Subgraph Enumeration
13. If the only requirement we make for a measure of trophic status tw is that if there is a directed path from u to v then tw(u) > tw(v), show that every acyclic food web has such a measure of trophic status.
14. (Roberts [6]) If relative level is measured using the length of the shortest directed path (our first definition), a plausible measure of trophic status is
15
tw(u)
w
where the sum is taken over all vertices v for which there is a directed path from u to v. Show that this possible measure has the property that if there is a directed path from u to v, then tw(u) > tw(v). Which of the Axioms 1-3 does this measure satisfy?
In our discussion of trophic status we assumed that the food web was acyclic. How restrictive is this assumption? Can you think of two species each of which could have the other as prey?
Computer Projects
1. Write a program to calculate trophic status in acyclic food webs.
2. Write a program to calculate the adjacency matrix for the intersection graph of a family of intervals given as pairs (a, b) of their endpoints.
Author:    Fred J. Rispoli, Department of Mathematics, Dowling College.
Prerequisites: The prerequisites for this chapter are counting, probability, graphs, and trees. See, for example, Sections 4.1-4.4, 7.1-7.6, 8.1, and 8.5 of Discrete Mathematics and Its Applications, Second Edition, by Kenneth H. Rosen.
Introduction
Many applications of graph theory involve enumerating subgraphs to determine the number of subgraphs satisfying various properties, or to find a subgraph satisfying various properties. Some interesting examples are:
Example 1 How many distinct paths are there joining locations vi to vs in the transportation network represented by the graph in Figure 1? Given the length, /, and cost, c, of each edge, as displayed in Figure 1, does there exist a path joining v± to v3 with total length 15 or less, and total cost $40 or less? □
Example 2 How many different isomers are there of the saturated hydrocarbons C5H12? □
241