Introduction to Graphs

A graph is a way of representing relationships that exist between pairs of objects. That is, a graph is a set of objects, called vertices, together with a collection of pairwise connections between them, called edges. Graphs have applications in modeling many domains, including mapping, transportation, computer networks, and social networks.

Viewed abstractly, a graph G is a set of V vertices and a collection E of pairs of vertices from V, called edges.

Edges can be either directed or undirected.

• An edge (u, v) is directed from u to v if the pair (u, v) is ordered, with u preceding v.
• An edge (u, v) is undirected if the pair (u, v) is unordered.

Undirected graphs

If all the edges in a graph are undirected, then we say the graph is an undirected graph.

Example: graph of coauthorship among some authors.

Edges are undirected because coauthorship is a symmetric relation.

Directed graphs

If all the edges in a graph are directed, then we say the graph is a directed graph (digraph).

Example: class hierarchy diagram for an object-oriented program.

Edges are directed because the inheritance relation only goes in one direction (asymmetric).

Mixed graphs

A graph that has both directed and undirected edges is called a mixed graph

Example: A city map can be modeled as a graph whose vertices are intersections or dead ends, and whose edges are stretches of streets without intersections. This graph has both undirected edges, which correspond to stretches of two-way streets, and directed edges, which correspond to stretches of one-way streets. Thus, in this way, a graph modeling a city map is a mixed graph.

Graph Terminologies

• The two vertices joined by an edge are called the end vertices (or endpoints) of the edge.
• If an edge is directed, its first endpoint is its origin and the other is the destination of the edge.
• Two vertices u and v are said to be adjacent if there is an edge whose end vertices are u and v.
• An edge is said to be incident to a vertex if the vertex is one of the edge's endpoints.
• The outgoing edges of a vertex are the directed edges whose origin is that vertex.
• The incoming edges of a vertex are the directed edges whose destination is that vertex.
• The degree of a vertex v, denoted as deg(v), is the number of incident edges of v.
• The in-degree and out-degree of a vertex are the number of the incoming and outgoing edges of v, and are denoted as indeg(v) and outdeg(v), respectively.

Example of a directed graph representing a flight network.

We can study air transportation by constructing a graph, called a flight network, whose vertices are associated with airports, and whose edges are associated with flights. In graph G, the edges are directed because a given flight has a specific travel direction. The endpoints of an edge in G correspond respectively to the origin and destination of the flight corresponding to that edge. Two airports are adjacent in G if there is a flight that flies between them, and an edge is incident to a vertex in G if the flight for that edge flies to or from the airport for that vertex. The outgoing edges of a vertex correspond to the outbound flights from that vertex's airport, and the incoming edges correspond to the inbound flights to that vertex's airport. Finally, the in-degree of a vertex of G corresponds to the number of inbound flights to that vertex's airport, and the out-degree of a vertex in G corresponds to the number of outbound flights.

The endpoints of edge UA 120 are origin LAX and destination ORD; hence, LAX and ORD are adjacent. The in-degree of DFW is 3, and the out-degree of DFW is 2.

Check your understanding

Refer to the graph in the figure above.

• The definition of a graph refers to the group of edges as a collection, not a set, thus allowing two undirected edges to have the same end vertices, and for two directed edges to have the same origin and the same destination. Such edges are called parallel edges or multiple edges.
• A flight network can contain parallel edges such that multiple edges between the same pair of vertices could indicate different flights operating on the same route at different times of the day.
• Another special type of edge is one that connects a vertex to itself. Namely, we say that an edge (undirected or directed) is a self-loop if its two endpoints coincide. A self-loop may occur in a graph associated with a city map, corresponding to a "circle" (a curving street that returns to its starting point).
• Here is a graph with parallel edges and a self-loop:

• A simple graph is one without parallel edges or self-loops; we assume that a graph is simple unless otherwise specified. In this case, we can say that the edges are a set of vertex pairs (and not just a collection).
• A path is a sequence of alternating vertices and edges that starts at a vertex and ends at a vertex such that each edge is incident to its predecessor and successor vertex, and a simple path is a path whose vertices are distinct.
• A cycle is a path that starts and ends at the same vertex, and that includes at least one edge, and a simple cycle is a cycle in which the only repeated vertex is the first and last one.
• A directed path is a path such that all edges are directed and are traversed along their direction. A directed cycle is similarly defined.
• For example, in the flight network graph, (BOS, NW 35, JFK, AA 1387, DFW) is a directed simple path, and (LAX, UA 120, ORD, UA 877, DFW, AA 49, LAX) is a directed simple cycle.
• Note that a directed graph may have a cycle consisting of two edges with opposite direction between the same pair of vertices, for example (ORD, UA 877, DFW, DL 335, ORD).
• A directed graph is acyclic if it has no directed cycles. For example, if we were to remove the edge UA 877 from the flight network graph, the remaining graph is acyclic.
• If a graph is simple, we may omit the edges when describing path P or cycle C, as these are well defined, in which case P is a list of adjacent vertices and C is a cycle of adjacent vertices.
• Example: Given a graph G representing a city map, we can model a couple driving to dinner at a restaurant as traversing a path through G.
  • If they know the way, and do not accidentally go through the same intersection twice, then they traverse a simple path in G
  • If they go home from the restaurant in a completely different way than how they went, not even going through the same intersection twice, then their entire round trip is a simple cycle
  • If they travel along one-way streets for their entire trip, we can model their night out as a directed cycle.
• Given vertices u and v of a directed graph G, we say that u reaches v, and that v is reachable from u, if G has a directed path from u to v.
• In an undirected graph, reachability is symmetric.
• In a directed graph, it is possible that u reaches v but v does not reach u.
• A graph is connected if, for any two vertices, there is a path between them
• A graph is strongly connected if for any two vertices u and v of G, u reaches v and v reaches u.
• A subgraph of a graph G is a graph H whose vertices and edges are subsets of the vertices and edges of G.
• A spanning subgraph of G is a subgraph of G that contains all the vertices of the graph G.
• If a graph G is not connected, its maximal connected subgraphs are called the connected components of G.
• A forest is a graph without cycles.
• A tree is a connected forest.
• A spanning tree of a graph G is a spanning subgraph that is a tree containing all the vertices of G.
• Examples:

• a directed path from BOS to LAX:

  

• a directed cycle (ORD, MIA, DFW, LAX, ORD): its vertices induce a strongly connected subgraph

  

• the subgraph of the vertices and edges reachable from ORD:

  

• the removal of the dashed edges results in a directed acyclic graph:

  

Check your understanding

Consider the following directed graph with 6 vertices and 9 edges.

Important properties of graphs

If a graph G with m edges and vertex set V, then the total degree of G is 2m.

If G is a directed graph with m edges and vertex set V, then the total in-degree of G is the same as the total out-degree of G, which is equal to m.

Let G be a simple graph with n vertices and m edges. If G is undirected, then m <= n(n-1)/2. If G is directed, then m <= n(n-1).

• Suppose that G is undirected. Since no two edge can have the same endpoints and there are no self-loops, the max degree of a vertex in G is n-1. Thus, 2m <= n(n-1).
• Now suppose that G is directed. Since no two edges can have the same origin and destination, and no self-loops, the max in-degree of a vertex is n-1. Thus, m <= n(n-1).

Let G be an undirected graph with n vertices and m edges:

• If G is connected, then m >= n-1
• If G is a tree, then m = n-1
• If G is a forest, then m <= n-1

The graph ADT