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.

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.

Undirected Graph

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).

Directed Graph

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.

Mixed Graph

Graph Terminologies

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.

Flight Network

Check your understanding

Refer to the graph in the figure above.

Exercise: The graph is _______

Answer: directed

Exercise: Vertex ORD is adjacent to vertex _____.

Answer: LAX

Exercise: Vertex DFW has _____ incident edges.

Answer: five

Exercise: What vertex has the minimum degree?

Answer: SFO

Check your understanding

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

Directed Graph
Exercise: Is B reachable from G?

Answer: Yes. Path G -> F -> C -> B goes from G to B.

Exercise: Is G reachable from B?

Answer: No. When starting at B, only F and C are reachable.

Exercise: _____ is a directed cycle.

Answer: F -> C -> B -> F. This cycle is a strongly connected component, as each of B, C, and F can reach the other two.

Exercise: The longest simple path contains _____ vertices.

Answer: 6. A path exists from A → D → G → F → C → B.

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).

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

The graph ADT

Function Description
is_directed() Returns true if this is a directed graph and false if this is an undirected graph
num_vertices() Returns the number of vertices of the graph
vertices() Returns a list of all vertices of the graph
num_edges() Returns the number of edges of the graph
edges() Returns a list of all edges of the graph
has_edge(u,v) Returns true if there exists an edge from u to v and false otherwise. For an undirected graph, there is no difference between has_edge(u, v) and has_edge(v, u).
get_edge(u,v) Returns the edge from vertex u to vertex v; undefined behavior if no such edge exists. For an undirected graph, there is no difference between get_edge(u, v) and get_edge(v, u).
endpoints(e) Returns the pair of vertices (origin, destination) for edge e.
opposite(e,v) For edge e incident to vertex v, returns the other vertex of the edge
degree(v, out=true) For an undirected graph, return the number of edges incident to vertex v. For a directed graph, return the number of outgoing edges incident to vertex v by default; report the number of incoming edges incident to vertex v if the optional parameter is set to false.
neighbors(v, out=true) Return a list of all vertices adjacent to vertex v. In the case of a directed graph, report neighbors via outgoing edge by default; report neighbors via incoming edge if the optional parameter is set to false.
incident_edges(v, out=true) Return a list of all edges incident to vertex v. In the case of a directed graph, report outgoing edges by default; report incoming edges if the optional parameter is set to false.
insert_vertex(x) Creates and returns a new Vertex storing element x
insert_edge(u, v, w, x) Creates and returns a new Edge from vertex u to vertex v, having weight w (1 by default), and storing element x; if an edge from u to v already exists, updates w and x for that edge
erase(v) Removes vertex v and all its incident edges from the graph
erase(e) Removes edge e from the graph