1 Introduction to Graphs

1.1 Graphs

A Graph \(G\) consists of two sets

  • \(V\), a set of vertices (also called nodes)
  • \(E\), a set of edges (each edge is associated with two1 vertices)

In modeling situations, the edges are used to express some sort of relationship between vertices.

1.1.1 Graph flavors

There are several flavors of graphs depending on how edges are associated with pairs of vertices and what constraints are placed on the edge set.

graph type edges multi-edges allowed? self-loops allowed? cycles allowed?
simple graph set no no yes
directed graph tuple no yes yes
multigraph set yes no yes
directed multigraph tuple yes yes yes
pseudo-graph set yes yes yes
tree set no no no
directed acyclic graph (DAG) tuple no no no

Directed graphs are sometimes called digraphs.

(Small) graphs are often depicted using dots for vertices and line segments or arcs for edges. For directed graphs, an arrow is used to indicate the direction.

  1. For each type of graph, draw a picture of an example graph with 5 vertices.

1.1.2 Labeled Graphs

In many situations it is useful to add additional information to either the vertices or the edges. These are sometimes called “labeled” graphs and the extra information referred to as labels.

1.1.3 Graph Models

Many things can be models with graphs of various types. In each situation below,

  • identify the vertices
  • identify what edges represent
  • determine which flavor of graph would be used
  • determine what, if any, information might be useful as labels (on vertices or on edges or on both)
  • if the graph has any special properties, note them
  • if your group disagrees about some of the answers, identify whether it is because you are making different assumptions about the situation being modeled
Model Vertices Edges Type of Graph Labels/Properties?
2
3
4
5
6
7
8
9
10
11

  1. Niche Overlap. Some species of animals compete with other species in an ecosystem.

  2. Acquaintanceship. Some pairs of people are acquainted with each other, some are not.

  3. Precedence and Concurrent Processing. Computer programs can be executed more rapidly by executing some statements concurrently But it is important not to execute a statement that depends on the results of statements that have not yet been executed. What is the precedence graph for this simple program?

          a = 0
          b = 1
          c = a + 1
          d = b + a
          e = d + 1
          e = c + d

  1. Influence. In studies of group behavior it is observed that certain people can influence the thinking of other people.

  2. Hollywood. Some actors have been in movies together, others have not.

  3. Round-Robin Tournament. In a round robin tournament, each team plays each other team once. (The graph should keep track of who wins and loses each game.)

  4. General Sports Schedule. The schedule for most leagues is not a round-robin tournament. How does that change the graph? If the games haven’t been played yet, what information might the graph keep track of? How?

  5. Telephone calls.

  6. World Wide Web.

  7. Road maps.

1.2 Bonus Problem

From 1961 through 1977 the NFL (National Football League) had a 14-game season. Until 1976, when two new teams were added, there were 13 teams in each of 2 conferences. The NFL wanted a schedule were each team would play 11 games against other teams in their conference and 3 games against teams from the other conference.

Devise such a schedule or explain why it is not possible. For simplicity, let’s name the teams in the American Football Conference (AFC) \(A_1, A_2, \dots, A_{13}\) and the teams in the National Football Conference (NFC) \(N_1, N_2, \dots, N_{13}\).

  1. In some types of graphs, the two vertices may be the same, so there is really only one vertex. This is called a self-loop.↩