|
[____]
A simple graph is a graph in which each edge joins two
distinct vertices and two distinct vertices are joined by at
most one edge.
A simple digraph, whose edges are directed,
is defined in an analogous manner.
Thus, loops and multiple edges are not permitted in simple graphs
and simple digraphs.
A graph (digraph) with loops and/or
multiple edges joining a fixed pair of
vertices is called a multigraph (resp. multidigraph).
A multidigraph whose edges are assigned a capacity is more commonly
called a network.
In this chapter the term "graph" is used when referring to a
simple undirected graph, while the term "digraph" is used when
referring to a simple directed graph.
Sometimes the term "graph" is used as the generic term for the
incidence structure on vertices and edges.
Such uses should be clear from the context in which they occur.
There are five Magma graph objects: the undirected simple graph
of type GrphUnd, the directed simple graph of type GrphDir, the undirected multigraph of type GrphMultUnd,
the directed multigraph of type GrphMultDir,
and the network of type GrphNet.
The simple graphs are all of type Grph, while the multigraphs
(including the network) are of type GrphMult.
There is a caveat here with respect to simple digraphs and loops:
for historical reasons, Magma allows loops in digraphs.
Simple graphs and digraphs are covered in this chapter, while
multigraphs, multidigraphs
are covered in Chapter MULTIGRAPHS and networks in Chapter NETWORKS.
All types of graphs may have vertex
labellings and/or edge labellings.
In addition, assigning weights and/or capacities to graph edges
is also possible, thus allowing to run shortest-paths and
flow-based algorithms over the graphs.
Importantly, from the present version (V2.11) onwards,
all the standard graph construction functions
(see Subsections Subgraphs and Quotient Graphs and Incremental Construction of Graphs)
respect the graph's
support set and vertex and edge decorations.
That is, the resulting graph will have a support set and
vertex and edge decorations compatible with the original
graph and the operation performed on that graph.
Magma employs two distinct data structures for representing
graphs.
A graph may be represented in the
form of an adjacency matrix (the dense representation) or in
the form of an adjacency list (the sparse representation).
The latter is better suited for sparse graphs and for
algorithms which have been designed with the adjacency list representation
in mind.
An advantage of the sparse representation is the
possibility of creating much larger (sparse) graphs than
would be possible using the dense representation, since
memory requirements for the adjacency list representation is
linear in the number of edges, while memory requirements for
the adjacency matrix representation is quadratic in the number
of vertices (order) of the graph.
This is covered in detail in Section Bounds on the Graph Order.
Further, multigraphs and multidigraphs (and networks) may only be
represented by an adjacency list since they may contain multiple
edges.
Users have control over the choice of representation when
creating simple graphs or digraphs.
If no indication is given, simple graphs and digraphs
are always created with the dense representation.
At the time of the present release (V2.11),
a significant part of Magma functions
are able to work directly with either of the representations.
However, wherever necessary, a graph will be converted internally
to whichever representation is required by a given function.
We emphasize that this process is completely transparent to users
and requires no intervention on their part.
For a concise and comprehensive overview on graph theory and algorithms,
the reader is referred to [Eve79]; in [TCR90]
they'll find a clear exposure of some graph algorithms,
and [AMO93] is the recommended reference for flow problems in graphs.
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|