Last modified: April 08, 1997

• Terminology
• Properties of Graphs
• Adjacency Matrix Implementation
• Adjacency List Implementation
• Special Kinds of Graphs
• A Problem
• Applications of Graphs
• Links
• References
• Web Page Creators

Terminology :

• V = Set of vertices (or nodes)
• |V| = # of vertices or cardinality of V     (in usual terminology |V| = n)
• E = Set of edges, where an edge is defined by two vertices
• |E| = # of edges or cardinality of E
• A Graph, G is a pair     G = (V, E)

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.

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.

• i) only one of (u, v) and (v, u) is present.
• ii) both (u, v) and (v, u) are present.

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.

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.

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.

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

A path from v to u is a collection u₁, u₂, . . . u_k, v such that all (u_i, u_i+1)  E. A simple path is a path in which each u_i 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.

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.

A free tree is a connected graph without a cycle.

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

A Directed Acyclic (no cycle) Graph.

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

  3) degrees : d₁, d₂, . . . , d_|V|

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

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

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

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.

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.

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.

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.

• Mazes (using stacks)
• Networks (computer, cities ....)
• Maps (any geographic databases )
• Graphics : Geometrical Objects
• Neighborhood graphs
• Voronoi diagrams

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.

	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.

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.

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.

References

Web Page Creators