Last modified: April 08, 1997
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 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.
Q: How many edges are there in a free tree?
Ans: |E| = |V| -1
A Directed Acyclic (no cycle) Graph.[Top]
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).[Top]
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.[Top]
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.
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
|List of Edges||Face1||Face2||.||.||.|
|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.
|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|