Graphs 

A graph G=<V,E> consists of a set of vertices (also known as nodes) V and a set of edges (also known as arcs) E. An edge connects two vertices u and v; v is said to be adjacent to u. In a directed graph, each edge has a sense of direction from u to v and is written as an ordered pair <u,v> or u>v. In an undirected graph, an edge has no sense of direction and is written as an unordered pair {u,v} or u<>v. An undirected graph can be represented by a directed graph if every undirected edge {u,v} is represented by two directed edges <u,v> and <v,u>. A path in G is a sequence of vertices <v_{0}, v_{1}, v_{2}, ..., v_{n}> such that <v_{i},v_{i+1}> (or {v_{i},v_{i+1}}), for each i from 0 to n1, is an edge in G. The path is simple if no two vertices are identical. The path is a cycle if v_{0}=v_{n}. The path is a simple cycle if v_{0}=v_{n} and no other two vertices are identical. Graphs are useful for representing networks and maps of roads, railways, airline routes, pipe systems, telephone lines, electrical connections, prerequisites amongst courses, dependencies amongst tasks in a manufacturing system and a host of other data. There are a large number of important results and structures that are computed from graphs. Note that a rooted tree is a special kind of directed graph and that an unrooted tree is a special kind of undirected graph. Graphs by Adjacency Matrices.A graph G=
If G is undirected, A_{ij}=A_{ji}=true if {v_{i},v_{j}} is in E and A_{ij}=A_{ji}=false otherwise. In this case there are at most V*(V+1)/2 edges in E, A is symmetric and space can be saved by storing only the upper triangular part A_{ij} for i>=j.
An adjacency matrix is easily implemented as an array. Both directed and undirected graphs may be weighted. A weight is attached to each edge. This may be used to represent the distance between two cities, the flight time, the cost of the fare, the electrical capacity of a cable or some other quantity associated with the edge. The weight is sometimes called the length of the edge, particularly when the graph represents a map of some kind. The weight or length of a path or a cycle is the sum of the weights or lengths of its component edges. Algorithms to find shortest paths in a graph are given later. The adjacency matrix of a weighted graph can be used to store the weights of the edges. If an edge is missing a special value, perhaps a negative value, zero or a large value to represent "infinity", indicates this fact.
It is often the case that if the weights represent distances then the natural distance from v_{i} to itself is zero and the diagonal elements of the matrix are given this value. A weighted adjacency matrix is easily defined in any imperative programming language. A graph is complete if all possible edges are present. It is dense if most of the possible edges are present. It is sparse if most of them are absent, E<<V^{2}. Adjacency matrices are space efficient for dense graphs but inefficient for sparse graphs when most of the entries represent missing edges. Adjacency lists use less space for sparse graphs. Graphs by Adjacency Lists.In a sparse directed graph, E<<V^{2}. In a sparse undirected graph E<<V*(V1)/2. Most of the possible edges are missing and space can be saved by storing only those edges that are present, using linked [lists]. Consider the weighted directed case. An edge <v_{i},v_{j}> is placed in a list associated with v_{i}. The edge is represented by the destination v_{j} and the weight.
Consider now the undirected case:
As before, half the space can be saved by only storing {v_{i},v_{j}} for i>=j:
Adjacency lists can be defined using records (structs) and pointers. Note that some questions, such as "are v_{i} and v_{j} adjacent in G", take more time to answer using adjacency lists than using an adjacency matrix as the latter gives random access to all possible edges. Path Problems in Directed GraphsThe weight of an edge in a directed graph is often thought of as its length. The length of a path <v_{0}, v_{1}, ..., v_{n}> is the sum of the lengths of all component edges <v_{i},v_{i+1}>. Finding the shortest paths between vertices in a graph is an important class of problem. See the [directed graph page]. Directed Acyclic GraphsA directed acyclic graph (DAG!) is a directed graph that contains no cycles. A rooted tree is a special kind of DAG and a DAG is a special kind of directed graph. See the [directed acyclic graph page]. The Minimum Spanning Tree of an Undirected GraphA minimum spanning tree, T, of an undirected graph, G=<V,E>, is a tree such that:
See the [undirected graph page]. Exercises


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Friday, 01Mar2024 05:29:20 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 