Commencing with the solution to the
Seven Bridges of Königsberg problem
by Leonhard Euler, the graph, which is
a mathematical object as simple as the
composition of vertices and edges,
begins to draw the attention of
mathematicians when they study in
their own fields. Nevertheless, many
real world problems show the trace of
a graph behind them, so it's useful to
study the reasoning of graphs as
a dedicated topic.
In this text, we will introduce and
establish some really fundamental and
common concepts, notations and
conventions about graph theory, so that
they are applicable in the later topics.
Graph Notations
The Seven Bridges of Königsberg problem
asks whether one can pass through the
7 bridges for exactly once. The map of
Königsberg is shown in the figure on the
left, with bridges highlighted in red.
We can extract the sides and islands
into nodes, with bridges being linkages
between nodes, so that we obtain the
figure on the right. We may start at
any node, and at any time we must
select a linkage connected to the
current node we are in, remove it
as we may only walk through it
exactly once, and go to the opposite
node connected by this linkage. The
problem is to ask whether there's a
way to use up all linkages.
In this problem, every bridge is
a two-way passage, so the order
of nodes it links does not matter.
While in the example below, which
is the relationship between factors
of , defined by their reachability
by dividing a prime, the order of
nodes in a linkage matters.
These give rise to the definition of
graphs and digraphs:
Definition (Graphs and Digraphs)
In graph theory, we care about
finite sets associated with
the linkages on elements in .
The element is called a
vertex, and the linkage
between is
called an edge, while the
vertices that links are
called the endpoints
of the edge. The edge is also said to
be incident to and to .
The endpoints of an edge need not to
be distinct, and if they are the same,
such an edge is called a
(self) loop.
For every edge in , if the order
of endpoints does not matter, the
mathematical structure
is called an (undirected) graph;
otherwise if the order of endpoints
matters, the mathematical structure
is called a digraph
or directed graph.
For convenience, if which graph
or digraph is referred is clear
and unambigious, we may refer to the
set directly. Otherwise we
may use the notations
such that and
such that
to point out which
vertex set or edge set we are accessing.
Warning
In graph theory, all edges must be
directed or undirected at
the same time.
If you find yourself trapped in
dealing with the case that only
some of them are directed, it's very
likely to be convertible to the case
of directed graph, with those
undirected edges incident to
converted into two clones of
directed edges, one from to
and the other from to .
The requirement for to be finite
is mandatory. In fact, many conclusions
of graph theory rely on the
finiteness of . On the other hand,
we do study the infinite set and the
linkages on it, but it is treated as a
distinct object from graph and digraph.
It might be alluring to define as
subset of , while it's not
the case. In the example of the Seven
Bridge of Königsberg problem, if we
define it as the subset of ,
then we will be unable to distinguish
from , which are both
, as well as distinguishing
from , which are both
. This is why we should
handle identity of edge and the
endpoints of the edge separately.
However, it's inconvenient if we
forbid referring to the edges by their
endpoints completely, thus we specify
conventions instead of forbiddance:
Convention (Referring to Edges by Endpoints)
In graph ,
is the set of edges in whose
endpoints are . We write
,
and otherwise.
Similarly in digraph ,
is the set of edges in that are
from to . We write
and otherwise.
For convenience, in graph ,
when we take edge out of a set
of edges , and
the endpoints of are ,
then we may write
to make the endpoints of
also clear. Noted that and
means exactly the same thing.
The same thing does for
in digraph .
If there're multiple graphs to
distinguish, we may write
and
to
specify that we are taking edges
out of graph . So does
and
for digraph .
For example, in the graph of the
Seven Bridges of Königsberg, we write
,
,
and .
In graph theory, it's very common
for some propositions to be
applicable to both directed and
undirected edges, as long as they
are incident to specific endpoints.
Thus, for convenience, we may let:
Convention (Unification of Adjacency Relation and Edge Reference)
It's possible to unify
in graph
and in digraph
into a monolithic
adjacency relation
,
such that
in graph and
.
In this way, handling
suffices to deal with
in graph
and in digraph
at the same time.
The only special thing is
is symmetric for graph while it is
not for digraph. Thus by defining
for relationship , the
unified notation matches our previous
definition and is perfect to go.
For convenience, we may extend
such unification to handling edge
sets, that if a proposition is
applicable to both undirected
edges from
and directed edges from
, we may begin
with "in graph or digraph" to
clarify its viability to both
graph and digraph, and then refer
to uniformly. That
the set equals
in graph and
in digraph .
Consequently, the edge
refers to the undirected edge
and the directed edge
.
We may also introduce the
multiplicity of edges:
Definition (Multiple Edges)
If in graph or digraph, the set
contains more than
one edge, then the edges in the
set are said to be
multiple edges.
And if in graph or digraph, by
somehow we managed to guarantee
there's only one element in
, we may refer to
or directly.
For example, in the graph of the
Seven Bridges of Königsberg,
are
multiple edges.
In some circumstance, we may make
propositions that are applicable
only to graph or digraph without
loops and even multiple edges,
and we'd better name them:
Definition (Loopless Graphs and Simple Graphs)
For a graph or digraph, if it has
no loop, then it is said to be
loopless, if it has no loop
or multiple edge, then it is said
to be simple.
Neighbors and Degree
In graph theory, standing on the
point of vertex, we care about
what edges are incident to it,
and what vertices can be reached
through an incident edge:
Definition (Neighbors)
In graph , the vertices reachable
through an incident edge to
are called the neighbors of
, it's denoted as
.
In digraph , since the direction
of edge matters, we have the
in-neighbors of as
,
as well as the out-neighbors of as
.
For convenience, we also allow taking
neighbors of a vertex subset
:
If it's required to distinguish what
graph or digraph we are talking about,
we will write
.
Please notice by our definition,
if then ,
and if then
,
which means vertex can be neighbor
of itself if there's loop.
Convention (Referring Incident Edges to Vertex)
Just like we may specify edges
incident to at the same time
by and
, we may also want to
specify the edges incident to
one at a time by:
For consistence, we allow writing
and
,
if only one endpoint of the edge
needs to be made clear.
Definition (Degree)
In graph , the degree
of a vertex is
the number of edges incident to ,
specially the loop are counted twice.
Which means:
Where all edges in
have been
counted once in the summand
.
In digraph , the in-degree
of vertex is
the number of incoming edges to ,
and the out-degree
is the number of departing edges
from . Which means:
We may also write
to distinguish the context.
The handshaking lemma, which is usually
considered as the first theorem of
graph theory, describes the numberic
relationship between degrees and the
number of edges:
Lemma (Handshaking Lemma of Digraph)
Proof. We may partition
by their starting endpoint,
so that every edge
goes to .
Obviously those sets in the form
of are disjoint
for each , thus we have
.
By the analogous argument, we have
.
Definition (Orientation of Graph and the Underlying Graph)
An orientation of graph is
a digraph with direction assigned to
every edges, that ,
and each edge
is exclusively oriented into either
or
.
Conversely, the underlying graph
of digraph is a graph with
direction erased from every edges,
that and each edge
is
one-to-one mapped / undirected into
.
Obviously every digraph is an orientation
of its underlying graph.
Example
Imagine if many tourists go to
Königsberg for a mathematical
vacation and the local goverment
decides to set up traffic control,
so that every bridge is now a
one-way passage. It becomes an
orientation of the
original graph now:
Lemma (Handshaking Lemma of Graph)
Proof. Let be any orientation
of , for any vertex ,
consider every edge
incident to , it's assigned to
either
or ,
in the former case it contribute
to , while in the latter
case it contribute to .
Specially when is loop it contribute
to both and
at the same time. And we
can see there's
.
Obviously there's ,
since just assigning direction to
edges in does not affect its
amount. And since:
We are done with the proof.
This also brings us to the parity
of vertices in a graph:
Collary
In graph , a vertex is
said to be odd when
is odd, and even otherwise.
The number of odd vertices is even.
Proof. Let the number of odd
vertices be , take modulo- to
the handshaking lemma we have
,
thus and
.
We also characterize a graph by the
maximum and minimum value
of its degrees:
Definition
In graph , we define:
Similarly in digraph , we define:
Graph is said to be
-regular if
.
Collary
A -regular graph of vertices
has edges, and if
is odd, must be even.
Proof. Clearly this is a
direct consequence of the
handshaking lemma.
Adjacency Matrix and Incidence Matrix
In graph theory, we may sometimes
refer to the adjacency matrix and
incidence matrix:
Definition (Adjacency Matrix and Incidence Matrix)
In a loopless graph or digraph,
since both are finite,
let and fix
.
In graph or digraph , the
adjacency matrix is
a -matrix such that
.
Clearly the adjacency matrix
of must be symmetric, while
it is not neccesarily the case
for digraph .
In graph , the incidence matrix
is a -matrix
such that if
is an endpoint of . In digraph,
, then
and other cells of the -th column
are set to .
Or more explicitly:
We may simply write
if what graph or digraph we are
talking about is clear, and we
may also explicitly write
to clarify the context.
Example
The adjacency matrix and incidence
matrix of the graph of Seven Bridges
of Königsberg are:
We may also not have incidence matrix
for graph or digraph with loop. Just
think of what should we fill into the
column corresponding to
,
should we let
or
? And
of course, for
,
we cannot fill in
simultenously, while filling in
will
render the whole -th column as .
The adjacency matrix of graph and
the incidence matrix of any of its
orientation has a strong connection:
Theorem
Let be a loopless graph, be any
orientation of , be the
adjacency matrix of , and
be the incidence matrix of . Then we have:
The matrix
is also called the Laplacian matrix
of graph .
Proof. Just consider what
values are in
.
When , in order for
not to be , either
or
must
hold, and either case will render
and require
.
Therefore we have
.
When , in order for
not to be , either
or
must
be held, and either case will render
and require
.
Therefore we have
.
In this way, clearly
and we are done with the proof.
When we think of the relationship
between the adjacency matrix of a graph
and the incidence matrix of matrix of
its orientation, we will find being
loopless is required in order for the
graph to have a orientation with
well-defined incidence matrix.
Specially, the Laplacian matrix and the
incidence matrix have the same rank:
Theorem (Rank of Laplacian and Incidence Matrix)
Let be Laplacian matrix of
graph and be incidence
matrix of any orientation of ,
then we have:
The rank relationship holds when
are over
any characteristic field.
Proof. Noted that both
and are
linear transformations on .
By rank-nullity theorem, that
,
it suffices to prove
.
In fact, we will prove
.
Consider any ,
clearly we have:
This will require
,
and therefore we have
.
On the other hand, it's obvious that:
Therefore we have
,
and thus
.
The rank implies the number of
independent row and column vectors
after gaussian elimination. For
characteristic fields, they have
prime field embedded into
them, and the gaussian elimination can
be carried out over by
the elements in the matrices. Thus the
rank relationship holds when viewing
the matrices as over any
characteristic field.
The adjacency matrix, incidence
matrix and Laplacian matrix
build us a bridge between graph
theory and linear algebra. We will
see in detail in later topics.
Algorithmic Representations of Graphs
It's also common to let computer to
process and solve graph theory problems,
and there must be way to represent a
graph so that the algorithm can fetch
and run over it.
As algorithm inputs, the vertices are
usually identified by an integer less
than the number of vertices, which is
usually also an input. Otherwise one
can also quickly process them into a
list / vector, and use the index as
integer identifier, and the container
length as the identifier range.
So the algorithmic representation of
a graph or digraph mainly focus on
the representation of edge. There're
two aspects, one is to fetch the
incident edges of a vertex, two is
to store extra information like
weight and costs on that edge.
The adjacency matrix is also one of
a common algorithmic representation
of graph and digraph. However, in
this way we must treat the edges
equivalently (as only
is stored in the
matrix cell). Many graph theory
problem takes simple graph as input,
or can be preprocessed into simple
graph by utilizing some properties
of the problem. And if the graph is
a simple graph, we can store the
extra information into the matrix
cell instead of . But we
should choose some special value
to identify the case that
then, e.g. we
may choose in the case
of weight or cost.
It's fast to check whether
, however it's slow
to fetch
which must be done by completely
scanning the row or column. It's
believed that such a scan must be
done in for each vertex,
and if all edges must be visited,
the whole traversal must be
done in .
The adjacency matrix is okay when the
average degree is approximate to
(in which case the graph is said to be
dense), but in most problem the
vertices are not so connected, and the
average degree is far less than
(in which case the graph is said to
be sparse). We will generally
use the adjacency list instead.
The adjacency list is a graph
representation by aggregating edges
onto each vertices. There're
containers for these edges, and each
edge is represented by the
(out)-neighbor. The containers might
be linked lists or vectors, depending
on whether the graph should be mutable
in the problem. Extra information
related to the problem can also be
stored in the node or cell
of each edge.
Example
Here are the graph of Seven Bridges of
Königsberg and its adjacency list:
Example
Here are one instance of the orientation of
the Seven Bridges of Königsberg alongside
with its adjacency list:
When adjacency matrix and adjacency list
are put together to compare their
performance, we usually consider the
case when all edges in the graph must
be iterated, in which we have:
Lemma
The edge iteration is done within time
complexity when
adjacency matrix is chosen as the
algorithmic representation, while the
time complexity is when
adjacency list is chosen instead.
Proof. When adjacency matrix is
used, every cell in the matrix must be
checked for the presence, and there're
exactly cells in total.
When adjacency list is used, every
linked list nodes must be visited, and
the time complexity depends on the
number of cells chained in each nodes.
In a digraph, every linked list
corresponding to vertex has
exactly nodes. By
handshaking lemma, exactly
nodes must be visited.
In a graph, every linked list
corresponding to vertex has
to nodes,
where the lower bound is taken when
all edges are loops and upper bound is
taken when there's no loop. By
handshaking lemma, to
nodes must be visited.
When the graph is dense, by handshaking
lemma it won't be hard to know there're
approximately edges
in the graph, thus time complexity of
adjacency list drops the same level as
adjacency matrix when it is dense. One
must be wondering why don't we use
adjacency list indefinitely?
Well, the matrix guarantees the address
coherence, while the linked list does
not, and even the vector can not
guarantee. The memory usage is also a
consideration. We will have to store
the identifier of vertex in adjacency
list, even when no extra information
besides adjacency needs to be stored,
in which only a bitmap needs to be
maintained in adjacency matrix.
Determining whether fast
is also a consideration, in adjacency
matrix it's just an lookup,
and in adjacency list, either an
linear search or an
bisect in ordered list
must be done.
Thus the choice of whether to use
adjacency matrix or adjacency list
depends on the actual problem to
solve, while most graph theory
algorithm will abstractly ask to
iterate the edges, which is
implemented by the actual
algorithmic representation.
Walk and Path Notations
It's quite intuitive and convincible
to allow us "walk" along "paths" in
a graph or digraph:
Definition (Walks, Trails and Paths)
In graph or digraph , a
-walk of length
, is an alternating sequence of
length , with vertices
and edges between them, that:
(Noted that unification of edge
reference is used.)
Both vertices and edges are
not necessarily distinct.
Or we may simply write it as:
The vertices
are said to be the endpoints
of the walk, and the vertices
are said
to be the internal vertices.
The length of is retrieved by
, noted that the length
always counts the number of
edges in the sequence. The
sets of vertices and edges of
are retrieved by
.
When all edges appears in are
unique, the walk is said to be
a -trail, and when all
edges and vertices appear in
are unique, the walk is said
to be a -path. We may
use to indicate it is a path.
If the endpoints of the
-walk are the same, then
the walk is said to be a
closed walk passing .
When all edges in a closed walk
are unique, it's said to be a
closed trail or a
circuit; and when all edges
and vertices in the walk are
unique, it's said to be a
cycle. We may use to
indicate it as a cycle.
Convention (Parity of Walks)
For convenience, if a walk
/ path / cycle has odd length,
then it's said to be an odd
walk / path / cycle; otherwise
it's said to be an even
walk /path / cycle.
Convention (Usage of Path versus Cycle)
When referring to walk or trail,
it might be closed or not closed.
But to avoid obfuscation, when
referring to path of positive
length, their endpoints
must be different (there's no
closed path), otherwise we
will call it a cycle.
Specially, there's -walk
containing a single vertex
and of zero length. To avoid
obfuscation, such walk is
considered a closed walk and a
path, however not a cycle.
Therefore a cycle must be
of positive length.
In short, a path of positive
length has distinct endpoints,
a cycle always has positive
length and the same endpoints,
and zero length walk is a path.
Example
Let's have a tournament in Königsberg, we
walk through the bridges except in
the order as is specified in the graph
to the left.
Assume the is removed from the
edge set of the graph, then the walk
is a -trail, however
it's not a path as
are repeated. The walk contains some
segments, where is indeed a
-path, and
are cycles.
Many authors, due to historical
issue and especially in computer
science, abuse the term "path" and
don't distinguish walk from path,
which is very unfortunate and really,
really bad. Such abuse has caused
many confusion and hindered the
communitation. Given that there're
sufficient lessons we can learn
from the predecessors, we have to
strive for making things clear
from now on.
Segment Notations
It's also intuitive to define
concatenation between two walks:
Definition (Concatenation of Walks)
For a -walk
and a -walk
,
Their concatenation
is defined as:
Given that edge can be easily
converted into single hop walk,
for convenience, we accept edge
as operand for concatenation
directly. For example:
It won't be hard to find the
concatenation is an
associative operation, and
under any circumstance.
As we can see, it's generally
verbose and hard to read if we
have to write all vertices and
edges over and over again. We
may also want to refer to a
segment of a walk conveniently.
Thus we will introduce the
segment notations:
Definition (Segment Notations)
In graph and digraph, just like
how we abbreviate edge
incident to , we introduce
a similar notation for a
-walk , that
.
For consecutive walks
,
we may write
.
Hybrid usage of walk segments and
edges is undoubtedly allowed, that
,
.
Example
A main usage of segment
notation is for pattern
matching. For example:
Writing so matches the last
incident edge to
alongside with another endpoint
of , and the walk
segment obtainable by
removing last edge, and makes
them available for reference
in current context.
Of course, it would be noisy
to haul everything into current
context, and it's completely
okay to ellide unnecesary
elements in the matching:
Writing so hauls only the last
edge into the context.
The well-formedness of segment
notation is guaranteed by its
user, which is the art of making
things clear. For example:
Writing so does not perform
a well-formed pattern matching,
since might have multiple
occurence in . Further
elaboration on the occurence
on is required, e.g.
matches the first occurence of .
We may also want to introduce
relation and set
related to it, just like how we
introduce adjacency relation
and the set
related to it. But we'd like
to show a related theorem to
justify our decision first:
Theorem
There's a -walk iff there's a -path.
Proof. For sufficiency,
clearly a -path is a
-walk sufficiently.
For necessity, we show a way
of fixing arbitrary -walk
into a -path.
If , then and
it's already a -path.
If and all vertices
in are distinct, then all
edge in will also be
distinct since they are
incident to different endpoint
pairs, and thus -path.
If and contains
repeated vertex, we fix
into a strictly shorter
-walk: let be one
of the repeated vertex and
,
such that is the first
occurence and is the
last occurence of in .
Noted that ,
otherwise will occur for
exactly once and is not
repeated. Then we fix
into -walk
such that
,
which will be fixed next.
The fixture of will not
last indefinitely, since the
descending chain of length
of is finite, it will halt
at , or at some point
that is a -path.
Warning
A closed walk passing cannot
be necessarily fixed into a
cycle passing .
Proof. Just consider the walk
() in graph passing
twice, clearly it cannot be fixed
into a cycle passing .
However, when the walk is of
length , it's in the
form of ,
which is a loop and thus cycle.
And the walk is in the form of
,
of length such that
: if
or then keeping
or suffices;
otherwise we may fix
into -path , and then
is a cycle passing .
In this way, we can see it's
equivalent to justify the
existence of -walk as
the existence of -path.
However, the latter case is
far much easier to handle,
given that it is always
finite, while the former one
isn't in general. Thus it earns
its dedicated notation:
Definition
In graph or digraph ,
we denote the set of all
-paths as
, writing
and otherwise.
The relation
is called the
connection relation,
that is read
is connected to .
Similar to the case of edges,
we can define:
And and to be
all paths in or , that
.
Clearly, all of
are finite sets.
It's natural to define distance
between vertices with paths:
Lemma
The shortest -walk in
length is a -path.
Proof. Let be the
shortest -walk, we may run
the process of fixing into
-path , such that
. However if
, it's a
contradiction to is the
shortest. Thus , no
segment needs to be removed
from , and is path.
Definition (Distance between Vertices)
The distance from
to , denoted as
, is the length of
the shortest -walk,
which clearly can be
evaluated by
if . Specially,
we will let
when
.
Subscript can be added in
order to distinguish the
context of graph or digraph.
Clearly
in graph , since by simply
inverse the underlying
sequence of a -path
we obtain a -path
and vice versa. However
it's generally not the
case in digraph.
Actually, it's very likely for
a walk-related problem to be
reducible to considering only
paths in graph theory. We can
see more of them in
the later topics.
Maximal Path
A path is said to be maximal
in set of paths, if there's no
longer path in containing it as
a proper walk segment. The existence
of maximality is accompanied by the
finiteness of or ,
making it fruitful for thinking
graph theory.
Let's see an easy example first:
Lemma
In graph , if ,
then there must be a cycle.
Proof. Consider maximal path
such that
we have
.
However, there must be
,
otherwise for any
,
concatenating
to forms a path
,
which is longer than in
and contains as
proper walk segment.
Corollary
In digraph , if
or
,
then there must be a cycle.
Proof. The argument is just
identical: inspect the neighbors
of the endpoints of maximal path
in , and argue the
neighbors are in the path by
attempting to extend it into
a longer path.
The process can also be interpreted
easily in natural language.
Consider the scenario of prolonging
the path
in graph such that
, must contain
other neighbor than due to
. If ,
it contains a cycle passing ,
otherwise we can prolong even
longer, however such process cannot
last forever since the set
is dwindling during the
process of prolonging.
In contrast, thinking of an
"infinite graph" of vertices being
and edges being
, with other concepts
defined in similar way. Clearly
for every
, thus the
minimal degree is . However
such graph does not contain a
maximal path, since for every
path with ,
we can prolong it even longer
by adding to it. And
clearly there's no cycle in
such "infinite graph" either.
In this way, we can clearly see
maximal path is an exploitation
of finiteness of .
Connectivity in Graph
With the connection relation, we
are able to define the
connectivity in graph.
Example
For example, consider the
following graph :
From the plot on the left, we can
quickly identify the two
"isolated islands"
of . Whether they are on the same
"island" can be easily defined by
connection relation, that we
can see
and so does . Meantime,
and vice versa.
Please notice the graph contains
no placement information, so
due to the way we plot the graph,
it can be easier or harder to
recognize "islands" in graph. Like
the plot on the right, just by
swapping the placement of
and , it should be not so
intuitive to identify these two
"islands" as the one on the left.
The stuff can be even more
entangled as the graph grows
complexer, so the connectivity
defined by path should be the
only standard.
Definition (Connected Components)
In graph , if there's a vertex
subset such that
while
,
then the vertex subset is
said to be a
connected component of ,
or simply a component.
It's quite obvious that the
connection relation defines
equivalence relation on :
- For every vertex
, by definition .
- Since
in graph, by inverting the
underlying sequence of
we obtain another sequence
,
which is also a valid path.
- The paths
can be concatenated into the
-walk
,
and thus .
Therefore, the vertex set of a
graph can always be partitioned
into disjoint connected
components by connection
relation. If a graph composes
of only a single connected
component, then it's said to be
(singly) connected.
For convenience, a vertex that
is connected component on its
own are said to be a
isolated vertex, and
the connected component it forms
is said to be trivial.
Although the connectivity is
quite independent of how we
plot the graph on a plane, if
there's a plot of isolated
islands, we should believe the
graph has at least
connected components; and
conversely, if we have known
the graph can be partitioned
into connected components,
we can separate the plane into
regions and allocate these
components to be ploted in
these regions separately.
So the problem concentrates
at finding out the connected
components of a graph. In fact,
the task suffices to do a
single pass scan of the edge
set. To see, we need to
consider how connected
components change as we
add an edge to a graph:
Lemma
After adding an edge to a graph,
the connected components remain
still, or two of them merge into
a component.
Proof. Let the graph
be of connected components
, the graph
obtained by adding
to
is , where
.
If , then are
already in the same connected
component, so adding to
does not affect the components.
If , then in graph ,
,
there's an -walk
,
and vice versa. Thus and
merge into a single component
in now.
This can lead to this quite
simple algorithm:
Algorithm (Incremental Connectivity)
The input is the graph
with
,
the output is the set
of
connected components in
:
- Initialize each vertex to be the
connected component on its own, that
.
- Iterate for each edge
,
such that
:
- if then do update
.
Proof. Let
that ,
for . The algorithm starts
with , in which
is the connected components in , and
the -th iteration of step 2
yields the connected components
of from .
After iterations the
algorithm terminates and yields
the connected components of
, in which
.
Theorem
The incremental connectivity algorithm
runs in time complexity
and space
complexity , where
is the inverse Ackermann function.
Proof. This is due to the
connected components are disjoint
sets and their union operations
can be tracked by disjoint-sets
data structure. The disjoint-set
data structure supports update in
and search in ,
occupying space , where
is the number of elements to
partition into disjoint sets.
The algorithm requires a search
and potential update for each
iteration, which requires time
,
and there're iterations,
thus the total time complexity
is and total
space complexity is .
The inverse Ackermann function
is a slow growth function and
nearly output no more than
in every scale of problem that
is solvable by a computer
physically, thus we usually treat
it as constant, and the time
complexity of the incremental
connectivity algorithm is
approximate to , which
is quite efficient.
The incremental connectivity
algorithm is also a part of
other graph algorithms, such as
the Kruskal's algorithm, which
will be discussed in a later topic.
The discussion of adding edge also
lead to such corollary quite easily:
Corollary
If has no cycle / is acyclic,
then there're connected
components in .
Proof. Again, consider
adding edges in in any order,
we claim that every edge added
connects two distinct components.
Otherwise, let
to be the edge that connect two
vertices in the same
connected component , before
adding this edge there's a
-path
,
and after adding this edge
is a cycle, and such cycle can
also be found in , which is
contradiction to has no
cycle / is acyclic.
Initially, there're trivial
components, after adding edges
there're components, and
there're additions to go,
thus there're components.
Corollary
A graph is acyclic iff it has
connected components.
Proof. The necessity has
been proved above, and to prove
the sufficiency, we think of
the contrapositive.
Again, think of the process of
adding edges incrementally. If a
graph has cycle, then the last
edge closing the cycle when
added will not merge two
components. Thus after adding
edges, there are more
than components.
This leads to the alias of
(undirected) acyclic graph:
Definition (Trees and Forests)
A connected (undirected)
acyclic graph is said to be a
tree.
From the lemmas above we know
a tree has vertices and
edges, and an acyclic
graph of vertices and
edges is a tree. And
since there's a cycle when
, a tree must
fulfill . And
in order to be connected, there
must be
,
therefore
.
In a tree, the vertex
such that is said
to be a leaf. In the tree
formed by an isolated vertex
there is no leaf. In the tree
such that , there must
be at least one leaf, since
and the leaf is the vertex
fulfilling the minimality.
An (undirected) acyclic graph is
said to be a forest, since
every connected component of it
is a tree.
We may have come across the
concept of trees (and forests)
in computer science, not limited
to the balanced binary search
trees (e.g. AVL trees, red-black
trees, B-trees) in data structure,
and the decision tree models in
machine learning. These trees
share the common point that
they are organized in a
hierarchy with single root (at the
base level), for a non-root node
at every level, there's a unique
referer from its previous level.
Every node must be reachable from
the root, and will be visited (in
balanced search trees) when the
search key falls into the range
represented by the node, or
(in decision trees) when the input
vector passes all predicates guarded
by its ancestor decision nodes.
When we abstract one of these trees
from computer science by converting
nodes into vertices, and the unique
reference from previous level as
undirected edges (thus helper
reference we built for accelerating
traversals must be excluded by such
specification, which may be found in
threaded trees, B+-trees, and so on),
we will soon obtain the graph structure
of the tree. Such a graph is obviously
connected, acyclic and thus a tree in
graph theory by definition. So the
theorems we drawn in graph theory are
immediately applicable to these trees,
in fact, they have already been
utilized to analyze the complexity
of operations in balanced binary
search trees and so on.
The only specialty of these
trees from computer science is to
have a root, or they may be said
to be rooted, while the
trees we study in graph theory
are generally unrooted,
although when studying graph
theoretic algorithms, we might
ocassionally discuss properties
of rooted trees. When the tree
is rooted, the order of
childrens usually matters, e.g.
left and right subtrees of a
binary search tree.
The graph structure of the rooted
tree is an unrooted tree, and it
won't be hard to see multiple
rooted trees might correspond to
the same unrooted trees. For
example, by swapping the order of
children when order matters; or
by rotating the tree via selecting
a direct children of (old) root as
new root, with the old root
excluding the subtree of new root
now becoming the children of it.
Conversely, for any unrooted tree,
by performing a depth-first search
or breadth-first search starting
at vertex , we obtain a
search tree rooted at with
graph structure identical to
the input unrooted tree. We have
details in performing such a
search in the
later topic of search in graph theory.
Besides adding edge, its also
useful to consider removing
vertex or edge from graph.
Consider a communication
network with relays and their
linkage, what if removing a
relay or linkage segregates
some relays from others?
With relays abstracted as
vertices and linkages
abstracted as edges, we are
able to study the design of
communication network with
graph theory, and establish a
good trade-off between cost
and robustness:
Definition (Cut Edges and Cut Vertices)
In a graph, a cut edge
or a bridge is an edge
such that removing it increases
the number of components.
Similarly, a cut vertex
or an articulation point
is a vertex such that removing
it (alongside with the edges
incident to it) increases the
number of components.
When we think of the consequence
of removing edge, we can see:
Theorem
An edge is a cut edge iff
it's inside no cycle.
Proof. If
is inside no cycle, after removing
, there's no -path.
Otherwise
forms a cycle and is contradiction.
If is
inside cycle
,
any -path
passing can be fixed
into -walk
after is removed, and thus
the connectivity of no pair of
vertices is affected by the
removal of .
Corollary
A graph is a forest iff every
edge is a cut edge.
Corollary
If a -path contains a cut
edge, then every -path
must contain that cut edge.
Proof. Assume the contrary,
that there's a -path
such that is
a cut edge, and there's
another -path
such that and
.
Clearly
is the cycle containing ,
which is contradiction to
is a cut edge.
Corollary
Every -path in a forest is
the only path connecting .
Proof. Consider a -path
, assume there's another
-path . Since every
edge in is a cut edge,
.
And every edge in is
also a cut edge, thus
, and
therefore .
Consider reconstructing the
path from the edge set:
starting from and ending
with , we connect edges
consecutively. The path
reconstructed from
must be identical to the
one from , since
the inputs are the same,
which is a contradiction to
is a path different
from .
Noted that a loop itself forms
a cycle, is not a cut edge, and
its removal does not affect the
analysis of remaining cut edges
and cut vertices at all. So the
following notation will comes
in handy when discussing or
solving connectivity
related problems:
Convention
For any edge set , let
be the edge subset with
all loops removed from , and
or
.
By similar argument applied
to vertices, we can see:
Lemma
A cut vertex must separate at
least of its neighbors into
distinct components after
its removal.
Proof. Let be a cut
vertex that separates
into distinct components,
must be on every -path.
Let one of them be
,
after is removed, its
neighbor must be on
distinct component, otherwise for
found after is removed,
can be fixed into a -path
without passing , which is
contradiction to is on
every -path.
Theorem
A vertex is cut vertex iff
it and its neighbors are
not inside the same cycle.
Proof. For vertex
and its two neighbors
such that no cycle passes
at the same time,
removing will disconnect
from , otherwise for
found after is removed,
will be the cycle passing
.
Conversely, if removing
separates its two
neighbours into two
components, and there's cycle
passing at the same
time, removing will leave
found after is removed,
which is contradiction.
Corollary
Every vertex of degree or
more in a forest is cut vertex.
Warning
We may not draw the conclusion of
a graph is a forest when every
vertex of degree or more is
cut vertex. An easy example is
, where vertices
are of degree , are cut vertices,
but the graph is not forest.
An intuition is removing a vertex
is more destructible than removing
an edge, since it takes away
incident edges alongside with it.
We will revisit such intuition in the
later topic of -connectivity.
Algorithmically, it's possible to
find the cut vertices and cut edges
through the depth-first search
based Tarjan algorithms, which will
be discussed in the later topic of
search algorithims in graph theory.
Connectivity in Digraphs
When it comes to the connectivity
in digraphs, the connection
relation is no longer equivalence
relation since
does not imply ,
in most cases.
We are also familiar with the
partial order, which is the
relation that is reflexive,
antisymmetric and transitive.
However, the connection relation
is reflexive and transitive,
but neither necessarily
symmetric (like equivalence
relations), nor necessarily
antisymmetric (like partial
orders), it's seemingly an
interpolation of them generally.
So, is their any specialty
about connectivity in digraphs?
A directed acyclic graph (DAG)
is the digraph that has no cycle,
and is the extremal case
we can reach:
Lemma
The connection relation of
is partial order iff
is DAG.
Proof. If
is DAG, but is not
antisymmetric, then for any evidence
,
forms
a cycle and is contradiction.
If is antisymmetric,
but has cycle
, then
,
which is a contradiction.
Actually, we may convert the
partial order with
finite into digraph
by letting
,
and then find out
is a DAG with
.
What about a more general case?
Well, for those symmetric pairs
,
we can easily find that
and
.
This inspire us to treat the
symmetric part in digraph as a whole:
Definition (Strongly Connected Components)
In digraph , if
,
then and are said to
be strongly connected.
For convenience, we may let
.
The strong connection relation
we define is symmetric, and by
combining with the intrinsic
reflexive and transitive property
of the underlying connection
relation, we create an equivalence
relation. That is:
- (Reflexive)
- (Symmetric)
- (Transitive)
A strongly connected
component (SCC) in digraph
is the vertex subset such that
.
Clearly the vertex set of
digraph is partitioned into
strongly connected components
by . For convenience,
we may let
.
With strongly connected components
defined, we are now able to define
the condensation of digraphs:
Definition (Condensation of Digraph)
The condensation
of digraph , is a digraph
such that the underlying graph is
simple graph on vertex set
, and:
Example
A digraph and its condensation can
be shown as below:
As you might have noticed, that
after condensation, we obtain a
DAG over SCCs, and this is
indeed what happens to digraphs:
Proof. When
in , we have:
Each edge
is realized by
.
In each strongly connected
component , there's
. In the
end, we have:
Where
and
.
Therefore in when
in .
Conversely, when we have:
Let ,
such path can be mapped into:
Where either
and is empty walk, or
and
with being realized
by . Therefore
in
, I mean
in .
Theorem
The condensation
of any digraph is DAG.
Proof. Assume the contrary,
there's cycle
in . For any
, we have:
Therefore
, but
is expected since ,
which is a contradiction.
Algorithmically, it's possible
to partition the vertex set
into strongly connected
component through either depth
first search based Tarjan's
algorithm, or topological sort
(which may also be implemented
by depth first search) based
Kosaraju's algorithm, both
run within . We
will discuss them in the later
topic of search algorithms
in graph theory.
Graph Operations
Generally speaking, once we have
clarified the operands and the
result, by definition or
algorithm, and assigned a
notation for it, we have defined
an operation. In this way,
obtaining the underlying graph
from a digraph, obtaining a
-walk from a -path,
evaluating the connected
components of a graph, obtaining
the condensation of digraph,
are all operations.
It's good to introduce operations
under dedicated context, and we
can define a new operation on
demand. But there're some neutral
and commonly used operations in
graph theory, that will look
scattered everywhere if we always
define them on first time usage.
So we write this section for
gathering and introducing them.
Subgraphs
It's quite common to define
substructures for mathematical
objects. And in graph theory,
we define the subgraph of
graph or digraph as:
Definition (Subgraphs)
A subgraph
of graph or
digraph , is a graph
or digraph such that
.
We denote such relationship as
or .
Noted that we may not denote
subgraph of digraph as ,
otherwise it will coincide with
the notation of edge set.
Such definition seems too general
and nothing special, and indeed it
is. We seldom refer to such kind
of general subgraph, but instead
we often refer to two specific
kinds of subgraph, the spanning
subgraph and induced subgraph:
Definition (Spanning Subgraphs)
A spanning subgraph of
graph or digraph
is a graph or digraph
is a subgraph such that
and . It is
obtained by keeping all vertices
while taking a subset of
edges from or .
Definition (Induced Subgraphs)
An induced subgraph
of graph ,
or
of digraph ,
parametered with vertex subset
, is a subgraph
of or such that
.
It's obtained by using a vertex
subset as vertex set, while
preserving incidence relationship
between these vertices in the
original graph or digraph .
Example
From the graph of the Seven Bridges
of Königsberg, the spanning subgraph
obtained by keeping edges with odd
ordinal, and the induced sugraph
obtained by removing , is
shown as below:
We may ocassionally remove certain
edges and vertices from graph or
digraph (e.g. remove cut edges and
cur vertices), and discuss the
property of the graph or digraph
after removal. For convenience, we
may define the subtraction operation:
Convention (Subtraction Operation for Graphs and Digraphs)
Given edge subset ,
we may define spanning subgraph
for graph or
for digraph
. When there's
only one edge to
remove, we may let
or
.
Given vertex subset ,
we may define induced subgraph
for graph
, or
for digraph
. When there's
only one vertex to
remove, we may let
or
.
Example
In this way, we may define
is cut edge if
contains more
components than , and
is cut vertex if
contains more
components than .
When there is subtraction, there
may also be addition. When the
operands are graph / digraph
and edge(s), we may trivially let:
Convention (Adding Edges to Graphs or Digraphs)
For graph or
digraph , and edge
that
, we simply let
or
.
This is also applicable to
edge subset incident to ,
that or
,
although used less frequently.
When the operands are
graph / digraph and vertice(s),
the answer is not so obvious.
Should we define as
adding edges
to or what? Therefore many
textbooks avoid messing up with
such notation, and we will also
avoid such operation, and choose
more explicit notation for
different purposes.
Set Operations
As graphs and digraphs are just
tuples of vertex set and edge
set, for convenience, many
textbook defines monolithic set
operations to certain extent.
However, the notation used by
different authors varies, and
we seek for common place so
that it's compatible with the
most common and influential
textbooks, while considering
the friendliness and usefulness.
For graphs and digraphs, when
there's a common ground set
between their vertex sets and
edge sets (e.g. when they are
subgraph of the same graph or
digraph, but not limited to
this scenario), it will be
useful to do union and
intersection between them:
Convention (Union and Intersection Operations)
For graphs , or
digraphs , we
may simply define their
union and intersection
operations to take on their
underlying vertex and edge
sets, that:
The union
may also be written as
or
when the underlying sets
are disjoint. However, we
will use the later one
since the symbol
has already been used to
denote disjoint union
between set, and thus
prevails in being explcit.
Example
For any graph
with components
,
it's always true that
.
The complement
of set
is usually defined as
when the universal set
is present. This is usually
considered in the boolean
algebra over such universal
set. Defining a universal set
is impossible for general
graph, however it's possible
when restrained to simple
graph on the same vertex set:
(Warn: If you have not learnt
lattices and boolean algebras,
you may just memorize how we
define the operations and
ignore the rationale.)
Definition (Boolean Algebra Operation on Simple Graphs)
The complete graph
on vertex set is
the simple graph such that
.
Let the set of simple graphs
on vertex set be
, clearly
is a lattice with order
. The lattice
with order is
a boolean algebra, and
there's a boolean algebra
isomorphism
between
and .
In this way, for simple graphs
on vertex set ,
we may define boolean algebra
operations as:
For the symmetric difference
operation ,
many books may denote it as
, however
has already been
defined as symmetric difference
in boolean algebra and set,
therefore we adopt
it for our text.
While it's nonsense to define
complement without a universal
set, it's quite common to
do subtraction and boolean
algebra between sets even if
it's not under universal set
context. And we will also
enlarge the application of
these operations to digraph
and graph without common
vertex set:
Convention (Subtraction and Symmetric Difference on General Graphs)
For graph and
digraph we would
like to define their
subtraction and symmetric
difference as:
Clearly defining in such way
is compatible with the boolean
algebra operations of simple
graphs on the same vertex set.
For the case we want to
do subtraction and symmetric
difference for the vertex sets
and edge sets of two graphs,
we may write
and
directly, although I've
never seen any occurence
of such scenario.
Transpositions of Digraphs
It's sometimes needed to
invert the direction of every
edge in digraph, and for
convenience, we define the
transpositions of digraphs:
Definition (Transpositions of Digraphs)
For any set of directed edges
, we define the
transposition map
as to invert the direction of
every edge in while keeping
their identity, that
.
The range of
with respect to is denoted
as .
Clearly
defines a bijection between
and with
inverse being itself, that
and therefore
.
For digraph ,
the transposition
of digraph is
obtained by applying the
transposition map to the
edge set, resulting in a
digraph that every edge
is inverted.
When SCCs of digraph are
considered alongside with
transposition, it's easy
to see that:
Lemma
For any sets of directed edges
, we have
.
Proof. We can easily get
by seeing as a subset
of preimage under map
. Then apply
this again and we get
.
Proof. For any
in implemented by:
There's a corresponding
cycle in :
Therefore
in .
And noted that
,
if
in but
in
, since the
latter one will imply
in
,
we have a contradiction.
Proof. For any
implemented by
,
the edge becomes
,
after transposition, therefore
,
and
.
Let take the
place of and we have
,
this will imply
,
and therefore
.
Proof.
Such relationship between
transposition and SCCs is
utilized by the Kosaraju's
algorithm in search of the
SCC themselves. We will see
in detail in the later topic.
Line Graphs and the "Prime" Notations
In graph theory, the concept
of line graph is defined as:
Definition (Line Graphs)
For graph or
digraph , the
line graph is a
simple graph
or
simple digraph
such that:
Which means we use the edges
in the original graph or
digraph as vertices. And in
, there's a directed
edge from to when
the target endpoint of
is the source endpoint of
; in , since
,
is adjacent to
when they are incident to
a common vertex.
Example
The line graph of the graph
of the Seven Bridges of
Königsberg is like:
As you might have noticed, it's the
union graph of complete graphs of
.
Proof. Mark that
.
From left to right, we every
implemented by
falls into the union
compound ;
from right to left, the
fact that
implies ,
and therefore every edge
in
is in .
Example
The line graph of a digraph is like:
As we can see, when it comes
to line graph, vertices
become edges connecting every
pair of edges from
and (Tips:
try ).
It's quite often the case that
when we ask a problem about
vertices in graph, we may ask
a similar problem about edges:
Definition (Internally Disjoint Paths and Edge Disjoint Paths)
In graph or digraph
, for two distinct
vertices ,
two -paths are
said to be internally disjoint
if their internal vertices are
disjoint, that is,
;
they are said to be
edge disjoint if their
edge sets are disjoint, that is,
.
Example
We may ask a question about
vertex, that what's the maximum
size of the set of internally
disjoint -paths; meantime,
we may ask a problem about edges,
that what's the maximum size of the
set of edge disjoint -paths.
And with line graph, we may
hopefully unify such
pair of problems:
Example
Consider the graph or
digraph constructed in
such way: with or
as foundation, we
add make two pseudo vertices
, and make edges
and
.
It won't be hard to find that
every -path in or
has a corresponding
-path in or ,
and vice versa:
And the special thing is, if
two -path are edge
disjoint, then their
corresponding -paths
in or will
be internally disjoint.
In this way, we unify the
internally disjoint paths and
edge disjoint paths with the
help of line graph. Every
conclusion we've drawn on
internally disjoint paths will
now be applied to edge disjoint
paths by using or
as proxy.
In graph theory, we may define
a lot of graph metrics,
which is numberic answer to
a graph theoretic question in
a specific graph or digraph.
E.g. /
provides the numberic answer
to the question of
minimum / maximum degree of
vertices in a graph, so it's
a graph metric.
And since when we ask a problem
about vertices, we may also
ask a similar problem about
edges. To improve the efficiency
of utilizing symbols, we will
define the convention of the
"prime" notations:
Convention (The "Prime" Notations)
Principally speaking, if
is a graph metric associated
with vertices, then is
the graph metric associated with
edges for the very question.
That is, the metrics without
prime symbol () are associated
with vertices, and the metrics
with prime symbol are associated
with edges.
By default, without extra
elaboration, for graph metric
retrieved in graph or
graph , is the graph
metric retrieved in graph
or .
Let's go over some examples to
see what it means:
Definition (Independent Sets)
An independent set
is a vertex
subset in graph
such that
,
that is, a set of pairwisely
non-adjacent vertices.
The independence number
of graph is the maximum
size of independent set we are
able to construct in graph .
We will denote such graph metric
as since it's
associated with vertices.
Definition (Matchings)
A matching
is an edge subset in graph
such that
,
that is, no pair of edge shares
the same endpoint.
If we take a matching in
to the line graph , we will
immediately find is an
independent set in . Thus
the matching number, which
is the metric of maximum size of
matching we are able to construct
in graph , should be denoted
as , according to
the "prime" notation.
The duality of independence number
and matching number belongs to the
lucky case that line graph can
handle by default. However,
there're still many cases that
cannot be handled without
extra elaborations:
Example
The maximum size of the set of
internally disjoint -paths
is denoted as
or , and the
maximum size of the set of
edge disjoint -paths is
denoted as ,
or , since
it's a pair of dual question
that one is for vertex and the
other is for edge.
As we can see, or
cannot handle it by default.
However, by tweaking the line
graph into or , via
adding pseudo vertex ,
we can see there's
or
.
Definition (Vertex Covers and Edge Covers)
In graph , a
vertex cover
is a vertex subset such that
,
that is, every edge is
incident to at least one
vertex in ; an
edge cover
is an edge subset such that
,
that is, every vertex
is incident to at least
one edge in .
The edge cover may not
exist when the graph has
isolated vertices, so we
require contains no
isolated vertices.
The set is trivially a
vertex cover, and is
trivially an edge cover
in a graph without isolated
vertex, so the problem is
to consider the minimum size
of vertex cover or edge cover.
The vertex covering number,
which is the metric of minimum
size of vertex cover in ,
is denoted as ; and
the edge covering number,
which is the metric of minimum
size of edge cover in ,
is denoted as .
Example
An edge cover in is
generally not a vertex
cover in : consider
the subgraph induced by
in , it's a complete
graph and require at least
vertices to cover when
;
however it suffices to take
one edge from
to cover . And clearly there's
.
Although being used as examples for
usage of the "prime" notations, the
independence number, matching number,
vertex / edge covering numbers are
all important concepts in graph
theory, and have intrinsically
connections. We will revisit them in
detail in the later topic of
matchings in bipartite graphs.
The maximum size of the set of
internally disjoint and edge
disjoint paths are also critical
to the -connectivity of graphs
and digraphs, due to the Menger's
theorem. We will revisit them
dedicatedly in the later topic
of -connectivity.
Graph Isomorphisms
Consider the two graphs:
When I say "two graphs", I mean
they are not the same graph.
Yes, I mean , since
,
,
and
.
But one might argue that the
graph has the same structure,
and it's nothing more than an
issue of labeling, that by
changing the label with
,
graph soon becomes .
If you have learnt algebra,
you may have already known that
,
since their multiplication
tables can be shown as below:
(We've arrange the
multiplication table of
so that one can easily see
how the elements are mapped.)
The connecting
and
means there's a bijection
(in our case, it's
)
such that
,
in which the group structures
are preserved when elements
are mapped. Such a bijection
is said to be a group
isomorphism, and the existence
of group isomorphism reveals
the fact that the two groups
has the same group structure.
The concept of isomorphism has
been leveraged by mathematicians
to handle the scenarios that
different mathematical objects
have the same structure in some
way. In the case of groups,
the isomorphism should preserve
the group structure; and
similarly in the case of graphs,
the structure of graph should
be preserved, which is given by
the way vertices are connected,
and can be seen from the edge set:
Definition (Graph Isomorphisms)
For graphs
and ,
or digraphs
and ,
a graph isomorphism
or
is a bijection
defined on vertex sets and edge
sets simultaneously, so that
are both bijections, and:
In short, if is an
edge connecting ,
then is
also an edge connecting
.
For convenience, we may refer
to directly instead of
if the type
of function argument is clear
(so the expression above can
be shortened into
).
If there's a graph isomorphish
or ,
we may say and to be
isomorphic, or and to
be isomorphic, and denote it
as or .
In the case of and
we've come up with previously,
since we may define a
graph isomorphism
such that
and
,
we have but
, and there's
no controversy.
Isomorphism classes
Let's first introduce the
concept of isomorphism class:
Definition (Isomorphism Classes)
The relation of between
graphs / digraphs is equivalence
relation, since:
- (Reflexive) by identity map ;
- (Symmetric) If due to , then due to ;
- (Transitive) If due to and , we have due to .
In this way, the equivalence
class of graphs /digraphs
under is said to be
the isomorphism class
of graphs / digraphs.
In order to define an
isomorphism class, it suffices
to take any graph from the
class. The graph chosen to
represent the isomorphism class
is called the representitive
of the class.
It's common to assign names
to isomorphism classes, such
as
(which will be introduced later).
We may use it to classify graphs,
like we may say is
when belongs to the
isomorphism class of .
The merit of classifying graphs
is clear, when we have studied
some graph theoretic properties
of the representitive of the
isomorphism class, by inspecting
how graph isomorphism may
preserve such property while
mapping graphs, we may migrate
the property to all graphs in
the isomorphism class. For
example, if a representitive
of fulfils
/ is -regular, since graph
isomorphism preserves the
degree of each vertex, every
graphs in should
be -regular.
One may ocassionally come
across the terms "labeled
graphs" and "unlabeled graphs"
used by many authors. They're
sometimes consider informal
terms, but they do affects
the naming and definition
of many graph theory concepts
and problems, e.g. the
Caylay's formula for labeled
tree counting. So we will
attempt to give them a
relatively deterministic
definition so that we can
use them in later topics:
Convention (Labeled Graphs and Unlabeled Graphs)
Since all graphs / digraphs
has finite vertex set, we
can first enumerate the
vertex set as
and then map then to a graph on
by
. This helps
us unify the graph defined
on different vertex set to be
defined on , and narrow
down the scope of the problem
we will be taling about. So we
would say a graph whose vertex
set is
to be a labeled graph.
The unlabeled graphs,
one the other hand, means
the isomorphism classes we
may obtain from labeled
graphs. Consider isomorphic
graphs on ,
the graph isomorphism on
should be a
bijection on vertex set
in the first place. All
bijections on forms
symmetric group , and
if how the bijection should
map the edge is omitted /
done in any way, any
permutation
can be sufficiently made
into a graph isomorphism.
To apply , we may
first erase the vertex
identities / labels
, and then
reassign the labels according
to to obtain the
graph isomorphic to the
previous one. The
intermediate "graph" with
labeled erased is prepared
to be labeled into any
graphs in this isomorphism
class, and thus it gets
its name "unlabeled graph".
While someone might argue
that the vertex set of labeled
graph need not to be ,
any vertex set suffices to
provide vertex identification.
However, as we have shown
we can indefinitely convert
it to due to the
finiteness of vertex set,
and allowing arbitrary vertex
set will unnecessarily
complicate the discussion,
we will force the labeled
graphs to be on
in our texts.
To plot an isomorphism
class, we will plot its
representitive with vertex
labels removed. One can
see it's proper when
reflecting on the argument
of isomorphisms of
unlabeled graph we've just
discussed above.
For convenience, we also
allow operations between
isomorphism classes and graphs:
Convention (Graph Operations on Isomorphism Classes)
For a graph and isomorphism
class , we say
contains a copy of
when there's a subgraph
such that
. For two isomorphism
classes , we say
contains a copy of when
the representive of
contains .
For a isomorphism class
whose representitive is
a simple graph, we will let
be the
isomorphism class
of .
Seemingly affected by the
unlabeled graphs, many authors
treat isomorphism classes as
if it where a graph, and writes
something like and
, for graph and
isomorphism classes ,
to mean and .
Both of them are valid since
there's no ambiguity, but we
adopt the latter way in our text.
Here are some most common
isomorphism classes we will
use in graph theory:
Definition (Unlabeled Complete Graphs)
Consider complete graphs
on vertex set
such that . Since
is finite, we may label
elements in as
.
Consider the complete graph
on vertex set
,
since there's a graph isomorphism
defined by and
,
we have
.
In this way, we define the
unlabeled complete graph
with vertices
to be the isomorphism class that
is in. Clearly all
complete graphs on
vertex set are in the
isomorphism class of .
Specially, when a graph
contains a vertex
subset such that
and therefore
, then
is said to be a clique.
Clique is the opposite
concept of independent set
we have introduced earlier,
where an independent set can
also be described in a similar
way that such
.
When is simple graph, then
for clique
and
for independent set . We
almost never talk about clique
in graph that is not simple.
The maximum size of clique to
be found in is called the
clique number, which is
denoted as , in the
opposite of for
independent sets.
Definition (Unlabeled Paths and Cycles)
The unlabeled path
with vertices
captures the structure of a
path of length ; similarly
the unlabeled cycle
with vertices
captures the structure of a
cycle of length . Say,
consider simple graph :
The is the isomorphism
class of , and
the isomorphism class of
.
Please notice if would
like to be a simple graph,
it's furtherly required that
, since must
contain a loop and must
contain multiple edges.
Therefore if
would
like to exist.
It won't be hard to see there's
.
And interestingly, one will soon
find there's
and .
The graph isomorphic to its
complement is said to be
self-completemtary. In
fact, is the only
self-complementary unlabeled
cycle, since it's the only
that each vertex in
has degree
, which is required when
would like
to be an unlabeled cycle. A
similar argument can be
carried out to to show
to be the only
self-complementary
unlabeled path.
Bipartite Graphs
Let's introduce the concept
of bipartite graphs:
Definition (Bipartite Graphs)
A bipartite graph
or bigraph is
a graph such that
, and
.
Which means are
independent sets called
partite sets or
partitions, and
all edges must connect
one vertex in and
another in . For
convenience, we say such
graph is an
-bigraph to
provide its partite sets
to the context.
For a -bigraph,
either or is
allowed to be empty.
Let
and
,
the complete bipartite graph
or biclique
is the isomorphism class of
simple graph such that:
Clearly is the
isomorphism class of maximum
simple bipartite graph,
however a bipartite graph
need not be simple when
it contains multiple edges.
For convenience, an
-bigraph that
is said to be an
-biclique, to
provide the bipartite sets
to the context.
The bipartite graph may be one of
the most important class of graph,
it's not only due to the special
duality it shown in the maximum
matching problem, by the
König-Egerváry theorem, which
will be discussed in the later
topic, but also due to its being
unbelievably common. Say, it's
quite easy for a graph
to be bipartite:
Assertion
A graph is bipartite iff
it contains no odd cycle.
The neccesity part is quite simple:
Lemma
A graph is bipartite only if
it contains no odd cycle.
Proof. We prove its
contrapositive. If there's
an odd cycle
in -bigraph , then
we must be able to partition
into independent sets
just by doing
.
However, for edge
in , if goes to
then must go to ,
and vice versa. When we walk
along the cycle , we end up
with partitioning and
into the same set due to
the parity of , but there's
an edge connecting them.
Thus it's impossible to partition
into two independent sets,
and therefore will never be
bipartite if there's odd cycle.
So the odd cycle itself forbids
the graph from being bipartite.
For the sufficiency part, there's
an algorithm to partition the
vertex sets of any graph without
odd cycle into its partite sets:
Algorithm
The input is a graph
without odd cycle, the output is
partite sets
such that
is
-bigraph:
- Initialize .
- Loop until :
- Pick up any ,
let , and initialize
counter .
- Loop until :
- If ,
do update ;
otherwise do .
- Update ,
increment .
- Halt with partite sets .
It's recommended to try running
the algorithm above on some
graphs without odd cycle manually,
to see how it works:
Let's prove the correctness of
the algorithm, and thereby
the sufficiency:
Lemma
In graph , for any pair
of -path and
-path sharing the
common endpoint , we may
"zip" them into the form of
and
,
such that they have a
common prefix , and
the internal vertices of
and are disjoint,
that is,
.
Proof. To do so, first
we will let
since
they share the common endpoint
, and be the
original -path
and -path found.
We iteratively check whether
,
if so then we are done,
otherwise we select any
such that
and
,
and "zip" them by updating
and
.
The process will halt after
finite step, since both
are finite
and decreasing per iteration.
The portions
are always paths since they
are portions of the original
-path and -path.
Theorem
The algorithm yields the partite set
of graph without odd cycle.
Proof. First, due to the
nature of algorithm to run until
in
the iteration of step 2, when the
algorithm halt, there's
. Then since the
number of elements in is
finite, each iteration of step 2
will bring at least vertex
into , the algorithm will
definitely halt eventually. And
each update of in step 2.2.2
will exclude vertices already in
, thus every vertex
will be added to or
exclusively in step 2.2.1, and
. So
the last thing to confirm is,
whether are independent
sets when the algorithm halts.
It won't be hard to find when
on step 2.2 is
hit, we have visited all vertices
in the component seeded by
chosen on step
2.2.1. The algorithm adopts the
idea of breadth-first search, which
will be discussed in a
later topic,
and the knowledge we've discussed
so far has been sufficient for it
(perhaps the definition of the
vertex colorings is also required,
but that one is quite simple).
So you may go over the related
theorems there and then back to
the topic, or just add what we've
claimed in this paragraph as
a precondition to the theorem,
and resolve it when you go over
the later topic.
If graph contains multiple
components, the algorithm will
go over multiple iterations of
step 2. While there's no edge
between vertices from different
components, and the behaviour
of algorithm to run in each
component is identical to
the algorithm running on ,
with ignored since
they will not affect
on step 2.2.2.
Without loss of generality, we
assume is connected with
the scan seeded at .
Let's break down the increment
of by iteration counter
, say
with being the
increment of or at
the iteration of step 2.2,
starting at .
For every
, it's
inside for some
, and is
inside for some
. Therefore
by doing such traceback,
for every ,
there's a -path of
length . For the same
reason, for every
there's a -path of
length .
Assume is not an
independent set for
.
There's a -path
and -path, and
after the "zipping" process
described by the lemma,
they becomes
and
,
such that they have a common
prefix and the internal
vertices of and
are disjoint. Let
or (and whether
is in or in
does not affect the outcome),
and let
:
There's a cycle
passing to
be found in .
Noted that
,
it's an odd cycle, which
is a contradiction to
does not contain odd cycle.
Similar argument can be
carried out to edges
between vertices in ,
to show is independent.
So must be
independent set if
does not contain odd cycle.
Corollary
A graph is bipartite iff
it contains no odd cycle.
Proof. Since the odd cycle
prevents the graph from being
bipartite, and there's an
algorithm to extract partite
sets for a graph without odd
cycle to be bipartite.
Clearly all acyclic graphs
/ forests are bipartite. But
but the range of bipartite
graphs is much wider range
than the one of acyclic
graphs, since it allows those
with even cycles, like
unlabeled cycles with
even vertices.
On the other hand, the bipartite
graph is associated with the
graph coloring problem:
Definition (Graph Coloring and Chromatic Number)
In graph , a vertex coloring
is a mapping
from the vertex set of to
finite set of colors. A
proper vertex coloring
is a vertex
coloring such that
.
Similarly, an edge coloring
is a mapping
from the edge set of to
finite set of colors. A
proper edge coloring
is an edge
coloring such that
.
Clearly a proper edge coloring
is equivalent to a proper
vertex coloring in the line
graph of .
We are interested in the
minimum size of that is
ever possible for a proper
vertex coloring or proper
edge coloring. As we can
see, if there's a proper
vertex coloring
, then any
larger set
can be used as the image of
, since leaving colors in
unused suffices.
However, the converse is not
true, consider the graph
of single edge, the
two vertices must be colored
differently, and there's
no feasible set of colors
of size for a proper
vertex coloring.
A proper vertex coloring
such that
is called a
-coloring.
The analogous concept for
proper edge coloring is
-edge-coloring. For
, a -(edge)-coloring
is also a -(edge)-coloring.
The graph is said to be
-colorable if there
exists a -coloring, and
-edge-colorable if
there exists a -edge-coloring.
For , a -colorable
graph is -colorable.
The chromatic number
is the minimum
size of the set of colors
ever possible for a proper
vertex coloring, and
. For
, the graph
is -colorable; for
, the graph
is -edge-colorable.
The graph coloring problem
may be one of the most famous
problem in graph theory, due
to the four-color theorem of
loopless planar graphs, which
is unbelievably hard and
verbose, and is proven with
the aid of computer, verifying
hundreds of different cases,
owing to Kenneth Appel and
Wolfgang Haken.
And we introduce a strongly
associated concept of
-partite graph:
Definition (k-Partite Graphs)
A -partite graph
is a graph such that
and
.
The sets
are called the partite sets,
and allowed to be empty.
For , a -partite
graph is also -partite, by
leaving some partite sets empty.
Clearly -partite graph is
just an extension of bipartite
graph to more than sets,
with being exactly
the case of bipartite graph.
Theorem
A graph is -partite iff
it's -colorable.
Proof. For a -partite
graph with
,
there's a
-coloring
defined by
.
For a -colorable graph
with -coloring
, we partition
into
such that
.
Clearly each is an
independent set due to
the contrapositive
of
,
and
.
In this way, being -partite
and being -colorable are
completely equivalent. When it
falls to the case of bipartite,
it becomes that a graph is
bipartite iff it's
-colorable. However, verifying
whether a graph is -colorable
is algorithmically special.
Noted that the coloring of each
components of a graph does not
affect the other. So without loss
of geneality, we study the coloring
of a connected graph, which can
be converted to the case of
coloring in each components later.
And we have:
Thereom
The -coloring of a
-colorable connected graph /
connected bipartite graph is
unique up to permutation of
the colors.
Proof. The term "unique
up to permutation of the colors"
means we treat the -colorings
and
such that
equivalently. In fact, one can
see this comes quite naturally
due to the fact that any
-bigraph is also a
-bigraph. In the
remaining text of this proof,
"unique" is "up to permutation
of the colors".
To prove, for -coloring
partitioning
into , assume
there's another unique
-coloring
partitoning into
. Noted that
,
and there should not be
,
otherwise and will
not be unique.
Since
,
and is connected,
by labeling every vertices
according to whether it's
in , it's
quite easy to identify an edge
in the form of
.
However, since
,
while
is required, it's impossible
for both and to be
valid -colorings at the
same time, which is a
contradiction to there're two
unique valid -colorings.
This guarantees us that any
-coloring we found for each
component of a -colorable
graph is the only solution (up
to permutation of the colors).
In the case of testing
-colorability for ,
when we are to determine the
color of through edge
,
we may have to check which
partite set that is not
in can we place in,
through a depth first search
with fallback manner. And in
the case of testing
-colorability of graph, if
a vertex is colored ,
then any vertex adjacent to it
must colored , and vice versa.
This guarantees us an ultra fast
algorithm to check -colorability.
Algorithm
The input is graph
,
the output is whether
is
-colorable, and the solution
of
-coloring
if
is
-colorable:
- Initialize empty mapping .
- Loop while there's uncolored vertex in :
- Select any uncolored vertex ,
set , initialze empty queue
, and enqueue into .
- Loop while queue is not empty:
- Pop front from .
- For each neighbor :
- If is not colored, set
if ,
otherwise set when
; enqueue into .
- If is colored, check whether
, if so halt with
is not -colorable.
- Halt with is -colorable
and the -coloring defined by .
Theorem
The algorithm yields the correct result.
Proof. This algorithm adopts the
idea of breadth-first search, so all
vertices and edges are checked, and
if the algorithm terminates with
is -colorable with corresponding
-coloring, the graph is sufficiently
-colorable. So the only problem to
suspect is, if is -colorable
while the algorithm fails to find it.
Assume is -colorable with
-coloring which the algorithm
fails to find. Let be loopless
since a graph with loop is not
-colorable. Since the algorithm
adopts the idea of breadth-first
search, each iteration of step 2
scans a component of , and if
is -colorable then the
component is -colorable. Let
component is being scanned,
is popped from and
is being checked, when the algorithm
halts with is not -colorable.
Let be the set of
vertices in that has been
colored by when the algorithm
halts. When is popped, has
been colored, and is reached
from some . So on the
timeline of vertices being scanned,
is pushed and popped from
after , therefore
is connected
graph, and -colorable by the
assumption. The portion of and
on are unique
up to permutation of the colors, and
let them be the same. So there's
,
such coloring of will cause
conflict on later, which is
a contradiction to is
valid -coloring.
Theorem
The algorithm runs in time complexity
.
Proof. Since all vertices
and edges are scanned exactly once.
So it suffices to do a breadth
first search to detect the
-colorability of a graph
while yielding the solution.
And when putting the algorithm
above together with the previous
algorithm for extracting partite
sets of bipartite graphs, we will
find we are just extending the
previous one with the capability
of detecting -colorability,
while they are the same in the
essence of partitioning vertices.
Eulerian Trails
Let's get back to the Seven
Bridges of Königsberg problem,
so is there a way to pass the
7 bridges for exactly once?
First, let's introduce the
concept of Eulerian circuits
and Eulerian trails:
Definition (Eulerian Trails and Eulerian Circuits)
In graph , a trail that
contains all edges in
is said to be an
Eulerian trail. When
Eulerian trail is closed / is
a circuit, it's said to be
an Eulerian circuit.
So the Seven Bridges of
Königsberg problem can be
formalized as, does its
underlying graph contain
a Eulerian trail? The answer
is no, and this section is
to give a proof of it, as
well as charactering all
graphs that has Eulerian
trail / circuit.
It's quite easy to derive
the essential condition of
the existence of Eulerian
trail / circuit:
Lemma
A graph has an Eulerian
trail only if it has at
most one non-trivial component
and or odd vertices
(with all remaining vertices
being even).
Proof. It's safe for a
graph to contain as many
trivial components as it like,
since adding or removing them
does not affect the edges we
have to consider. However, if
there're two or more trivial
components in the graph, the
Eulerian trail itself shows
the components to be connected,
which is a contradiction.
Let the Eulerian trail be
.
Since the contains all
edges, the degree of every
vertices can be deduced from
walking . For each
internal vertices
of , each occurence of
is accompanied by an
entering edge and
leaving edge ,
contributing to the
degree of ; the
endpoint has
leaving edge and
has entering edge
, contributing to
their degrees. So when
, there're
odd vertices, and
when ( is
Eulerian circuit), there's
odd vertex.
The underlying graph of
the Seven Bridges of
Königsberg problem has
odd vertices, so it's
impossible for it to have
an Eulerian trail. The
Seven Bridges of
Königsberg problem has
been setteled, however we
have set our goal to
characterizing all graphs
that has Eulerian trail
/ circuit, so let's move on.
In fact, the problem of
Eulerian circuits can be
furtherly reduced:
Lemma
A graph with exactly
odd vertices
has an Eulerian trail
iff the graph
for pseudo edge
created has an
Eulerian circuit.
Proof. By the previous
lemma, if would like to
have an Eulerian trail, then
it must not be closed, due to
the odd vertices ; and
if would like to have
an Eulerian circuit, then it
must be closed since all
vertices in is even.
If
is an Eulerian trail in ,
then
is an Eulerian circuit in
; and conversely if
is an Eulerian circuit in
, then
is an Eulerian trail in .
So there's conversion
between Eulerian trail in
and Eulerian circuit
in .
So it suffices to characterize
all graphs that has Eulerian
circuits and then migrate it
to the case of Eulerian trails,
according to the lemma above.
By the neccesary condition, if
a graph would like to contain
an Eulerian trail, it must
contain at most one non-trivial
component with all vertices
being even. And this neccesary
condition also turns out
to be sufficient:
Assertion (Euler-Hierholzer)
A graph has Eulerian circuit
iff it contains at most
one non-trivial component
with all vertices being even.
To see, let's first show the
property of such kind of graph:
Convention (Even Graphs)
For convenience, a graph is
said to be even if all
vertices inside are even.
Lemma
An even graph decomposes
into cycles, that is, there's
a series of cycles
such that
.
Proof. If all components
of are trivial, then we
are done; otherwise consider
one of the non-trivial component
, clearly ,
thus contains a
cycle by the argument
of maximal path. Noted that
is also an even
graph, with
.
Since is finite, by
recursively applying this
argument on , we
will eventually result in
that all components are trivial.
In this way, decomposes
into cycles, such that
.
And if we are able to
combine these cycles into
a single Eulerian circuit,
then we are done. So let's
draft an algorithm:
Algorithm
The input is an even graph
with at most one
non-trivial component, the
output is Eulerian circuit
of
:
- Decompose into
cycles .
- Let , and
.
- Loop until :
- Select
such that .
- For
such that
,
update
,
and .
- Halt with being the
Eulerian circuit of .
Theorem
The algorithm yields the
Eulerian circuit correctly.
Proof. It won't be hard
to see when all cycles in
are exhausted,
the output must be an Eulerian
circuit since it's a circuit
containing all edges of .
The only problematic part is,
the step 3.1
claims there's a
such that
unconditionally, but how comes it?
Assume the contrary that at
certain iteration of step 3,
.
Let
,
so .
Noted that all edges in
are partitioned into cycles
, and now a cycle
is either merged into , or
remains in
exclusively. Those edges
partitioned into cycle merged
into are edges on ,
and those edges partitioned
into cycles remained in
are edges on .
Vertices in and are
not isolated vertex, and for any
, they
can be found to be on distinct
non-trivial components, since
there's no edge for constructing
-path connecting them.
In this way, contains two
or more non-trivial components,
which is a contradiction to the
precondition that has at
most one non-trivial component.
In this way, we have characterized
all graphs with Eulerian circuit
inside them:
Corollary (Euler-Hierholzer)
A graph has an Eulerian circuit
iff it's even, with
at most one non-trivial component.
Proof. The necessity is given
by the lemma of necessary condition
of existence of Eulerian trail /
circuit, the sufficiency is given by
the algorithm above.
Corollary (Euler-Hierholzer)
A graph has an Eulerian trail iff
it has or odd vertices with
at most one non-trivial component.
Proof. Due to the lemma of
equivalence between Eulerian
trail in with odd vertices
and with pseudo edge
between the odd vertices.
This shall conclude the
characterization of all graphs
that has Eulerian trail / circuit.
