Class notes CS251B -- Winter 1997

McGill University:
School of Computer Science
Winter 1997 Class Notes for 308-251b

Topic #25 : Graphs: introduction

Last modified: April 08, 1997


Contents



Graphs

Terminology :

Labeled Graphs:

We may give edges and vertices labels. In our diagram all vertices have been labeled and two of the edges have been labeled. Graphing applications often require the labeling of vertices and for some applications, such as in organic chemistry , the labeling of edges is also common, (to represent different types of bonds). Edges might also be numerically labeled. For instance if the vertices represent cities, the edges might be labeled to represent distances.

Directed Graphs:

A directed graph is one in which every edge (u, v) has a direction, so that (u, v) is different from (v, u). In an undirected graph, there is no distinction between (u, v) and (v, u). There are two possible situations that can arise in a directed graph between vertices u and v.

    A Directed Graph
Subgraphs:

A subgraph of (V, E) is a pair (V', E'), where V' is a subset of V, and E' consists of all edges (u, v) of E between two nodes of V'. For example, in the figure above, the subgraph for F, G, and H has three edges. The subgraph for D, E, F, G, H, and I is circled and contains 9 edges.

Connected Components:

A connected component containing the node u is the subgraph consisting of all nodes v that may be reached from u by traversing zero or more edges. A graph may consist of one or more connected components. The above graph consists of two connected components. A connected graph has only one connected component.

Neighbors:

The neighbors of v V are all u V such that u v, and (u, v) E. In this case we can also say that u and v are adjacent. In our graph, the neighbors of F are E, H and G.

Degree:

The degree of v V is equal to its number of neighbors.

Path :

A path from v to u is a collection u1, u2, . . . uk, v such that all (ui, ui+1)  E. A simple path is a path in which each ui is distinct. I-H-G is a simple path in our graph. I-G-E-D-I-H-G is a path in our graph.

Cycle:

A cycle is a path that begins and ends at the same place. In other words its a path from u to u. The Subpath not including the terminal node is simple.

Free Tree:

A free tree is a connected graph without a cycle.

A Free Tree

Q: How many edges are there in a free tree?
Ans: |E| = |V| -1

Dag:

A Directed Acyclic (no cycle) Graph.

[Top]

Properties of Graphs


  2) # of graphs with |V| vertices : 2 [|V| ( |V|-1 )]/2

  3) degrees : d1, d2, . . . , d|V|

Note: This shows that the number of nodes with an odd degree must be even.
[Top]

Adjacency Matrix Implementation

A |V| × |V| matrix of 0's and 1's. A 1 represents a connection or an edge. Storage = |V|²       (this is huge!!)

Adjacency Matrix

For a non-directed graph there will always be symmetry along the top left to bottom right diagonal. This diagonal will always be filled with zero's. These facts simplify coding.

Coding a Graph

Coding is concerned with storing the graph in an effecient manner. One might grab all the bits from the adjacency matrix and concatenate them to form a binary string. One could say that the numerical value of the binary string (consider as the positive integer) is the number of the graph. Different graphs have different numbers. Clearly, |V|² bits would suffice.

One may improve on this scheme in two ways: the initial string obtained from the adjacency matrix may be compressed by standars compression methods . Also, for undirected graphs, it suffices to concatenate the bits of the upper right triangle of the adjacency matrix as is done in the figure below.

This is the graph number 46.
Graph number zero is a graph with no edges.

          Coding Graphs

Problem : How would one go about implementing the following operations effeciently?

MakeGraph (n, g), where n is the number of vertices and g is the graph number.

Insert/Delete (g, i, j) where (i, j) E (these operations will change the graph number).

[Top]

Adjacency List Implementation

The Adjacency list implementation typically uses less space than the adjacency matrix implementation. It is exactly like hashing with chaining where we have a list (array) of vertices , each of which stores a linked list of all of its neighbors.

Adjacency List Implementation

This method is very good for problems that involve traversing a graph. Storage = |V| header cells + 2|E| linked list cells (since each edge in an undirected graph is counted by both vertices that it connects). In a directed graph the 2|E| is replaced by |E|. The overhead in this method is quite excessive, however consider the graph number (1000001100000000000000000000100)2. This is an example of sparse graph. Sparse graphs are defined as graphs with few edges, (typically . For a graph like this we are much better off using the adjacency list implementation with the storage (|V| + 2|E|) versus storage of |V|² for the adjacency matrix implementation.

[Top]

Special Kinds of Graphs


Certain graphs have special configuration which eliminates the need to use any of the implementations introduced so far.
Grid:

The neighbours of (i, j) are (i ±1, j) and (i, j ± 1), therefore it suffices to store the pair (i, j). This is analogous to what we did for heaps, where the heapsize was essential. As no pointers are needed, the resulting data structures are called implicit data structures.

Complete Graph:

A complete graph Knis a graph in which all possible edges are present. The matrix for this graph would contain all 1's therefore there would be no point in storing it.

Complete Bipartite Graph:

A complete bipartite graph Km, n is a graph that has its set of vertices positioned into two subsets, one of size m and the other of size n. All possible edges from one subset to the other are present, but there are no edges between the vertices of the same subset.

Cycle:

The cycle Cn consists of n vertices v1, v2, ..., vn which are connected by the edges (v1, v2), (v2, v3), ....., (vn-1, vn), (vn, v1).

Wheel :

The wheel Wn is constructed from the Cycle Cn by adding a new vertex to the graph and connecting it to each of each of the already existing vertices.

Mobius Wheel:

The mobius wheel Mn (where n is even) is constructed from the cycle Cn by adding additional edges between vertices which are directly across from each other.

[Top]

A Problem

Consider a directed graph stored in adjacency matrix form. The edge (u, v) is an ingoing edge with espect to v, and an outgoing edge with respect to u.

A sink is a node with |V|-1 ingoing edges and no outgoing edges.

Write an O(|V|) algorithm to determine if a graph (given in a |V| × |V|) has a sink.

[Top]

Applications of Graphs

Some of the applications of graphs are :

Graphics :

Many geometrical objects such as cubes, polyhedra, and wire frame car models, may be thought of as graphs. These graphs are more than just nodes and edges. Their geometrical structure must also be taken into account. For example consider the cube:

This structure contains three kinds of objects
  • vertices
  • edges
  • faces
Edges are crucial since, in a three dimensional object, an edge will always belong to only two faces and two nodes. For this reason it makes sense to number the edges. Faces become linked list of edges, and each edge lives in only two faces.
List of Edges Face1 Face2 . . .
1
2
-
2
3
-
3
4
5
4
1
-
5
-
6
6
-
7
7
.
3
.
.
.
.
.
.
.
.
.
.
.
.

Faces become linked list of edges, and each edge lives in only two faces

Neighborhood Graphs

These are graphs for collection of points in d-dimensional space. Such point sets may be visualized by connecting close points. There are many possible definitions of closeness. For example, one might draw a circle with two data points at diametrically opposite sides. If the circle contains no other data points then the two points may be considered "close" and an edge may be added between them.

Voronoi Diagrams

In computational geometry the voronoi diagram is the main tool for storing clouds of points and for manipulating points in the Euclidean space. To create a voronoi diagram we must partition the graphical space into regions. This is done by seperating every pair of data points which are nearest neighbors by a line which is centered between the points and perpendicular to an imaginary edge between them.

[Top]

Java Applet

Simple Graphing Demonstration


This Java Applet demonstrates Simple Undirected Graphing. The user creates points, then places edges between some or all of them. As this is done, the user is shown how 2 representations of the Graph, the Edge Matrix and the Adjacency List, are changed by the addition of a Node and of an Edge. Nodes and Edges are the 2 basic components of any Graph. The Edge Matrix indicates which Nodes have an Edge between them by making the value of box (Node1, Node2) = 1. For an Undirected Graph, this Matrix is symmetrical about its diagonal axis form (0,0) to (n, n). The Adjacency List shows, for each node, a list of the other nodes to which it is connected. Its size for an Undirected Graph is (# of Nodes + 2(# of Edges)). The user is also shown how an Undirected Graph can be encoded from the (sometimes sparse) Matrix of edges. This encoding assigns to each Graph a unique decimal number from which all information concerning the edges may be determined given the number of nodes. If all possible edges are drawn between the nodes, a Graph is said to be "Complete". Try drawing a Complete Graph and see what happens.




view the source of the applet

Links

Sugihara's lecture notes on Graphs Representation of Graphs
Mark Toleman & Prof Tony Roberts, Dept Maths & Computing, University of southern Queensland Introduction to Graphs
Dept of Computer Science, Oberlin College Introduction to Graphs and Graphs Terminologies
ICS: Design and Analysis of Algorithms, Dept of Information and Computer Science, UCI Intoduction to Graphs, their representation, and examples of Graphs
Nikos Drakos, Computer Based Learning Unit, Uiniversity of Leeds Elementary Definitions, Representations, and Examples of Graphs
Downloadable Postscript Files
On Graphs Department of Computer Science, University Of Iowa
Data Structures for Graphs Dept. of Computer Science, SUNY, the State University of New York
[Top]

References

  • CORMEN, Thomas H. and LEISERSON, Charles E. and RIVEST, RONALD L., Introduction to Algorithms, The Massachusetts Institute of Technology, Cambridge, Massachusetts, 1990. Section 23.1
  • WEISS, Mark Allen., Data Structures and Algorithm Analysis in C The Benjamin/ Cummings Publishing Company , Inc., 1992. Section 9.1
  • SEDGEWICK, Robert., Algorithms in C Addison-Wesley Publishing Company, Reading, Massachusetts, 1990. Section 29.
  • AHO, Alfred V., HOPCROFT, John E., ULLMAN, Jeffery D., Data Structures and Algorithms , Addison-Wesley Publishing Company, Reading, Massachusetts, 1983. Section 6.1, 6.2, 7.1.
  • BOGART, Kenneth P., Discrete Mathematics, D.C. Heath and Company, Lexington, Massachusetts, 1988. Section 9.1.
  • GERSTING, Judith L., Mathematical Structures for Computer Science, Computer Science Press, New York, 1993. Section 5.1, 5.2, 5.3.
  • MANBER, Udi., Introduction to Algorithms, Addison-Wesley Publishing Company, Reading, Massachusetts, 1989. Section 7.1.

  • [Top]

    Web Page Creators

  • Rachel Potvin
  • (rachelp@cs.mcgill.ca) (Notes Compilation, Text Preparation)
  • Rebecca Ann Michaels
  • (rupert@cs.mcgill.ca) (Java Applet)
  • Chiu Hang Patrick Fung
  • (pfung@cs.mcgill.ca) (Graphics using Xpaint)
  • Razi Abbas Bokhari
  • (bokhari@cs.mcgill.ca) (Links, HTML)


    [Top]
    Last Updated April 08, 1997, at 16:15 by Razi Abbas Bokhari

    Copyright © 1997, Rachel Potvin, Rebecca Ann Michaels, Chiu Hang Patrick Fung, Razi Abbas Bokhari. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy. Disclaimer: this collection of notes is experimental, and does not serve as-is as a substitute for attendance in the actual class.