Basic graph definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(72 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Basic definitions ==
# [[Sets and sequences]]
== Directed and undirected graphs ==
== Directed and undirected graphs ==


# A '''directed graph''' <math>G=(V,A)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets|multiset]] <math>A</math> of ordered pairs of nodes. The elements of <math>A</math> are the '''arcs''' of <math>G</math>.
# A '''directed graph''' <math>G=(V,A)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets|multiset]] <math>A</math> of [[Sets and sequences#Singleton, pair, triple, quadruple|ordered pairs]] of nodes. The elements of <math>A</math> are the '''arcs''' of <math>G</math>.
# An undirected graph <math>G=(V,E)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets|multiset]] <math>E</math> of ''un''ordered pairs of nodes, the '''edges''' of <math>G</math>.
# An undirected graph <math>G=(V,E)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets|multiset]] <math>E</math> of [[Sets and sequences#Singleton, pair, triple, quadruple|''un''ordered pairs]] of nodes, the '''edges''' of <math>G</math>.
# A directed or undirected graph is '''simple''', if:
# A directed or undirected graph is '''simple''', if:
## No node is paired with itself in <math>A</math> or <math>E</math>, respectively.
## No node is paired with itself in <math>A</math> or <math>E</math>, respectively.
Line 13: Line 17:
# A node and an arc/edge are called '''incident''' if the node belongs to the arc/edge.
# A node and an arc/edge are called '''incident''' if the node belongs to the arc/edge.
# Two arcs/edges are called '''incident''' if they share at least one node.
# Two arcs/edges are called '''incident''' if they share at least one node.
# For a node, the number of incident arcs/edges is the '''degree''' of this node.
# For a node, the number of incident arcs/edges is the '''degree''' of this node. A node with degree zero is '''isolated'''.
# Consider a directed graph <math>G=(V,A)</math>:
# Consider a directed graph <math>G=(V,A)</math>:
## For an arc <math>a=(v,w)\in A</math>, <math>v</math> is the '''tail''' of <math>a</math>, and <math>w</math> is the '''head''' of <math>a</math>.
## For an arc <math>a=(v,w)\in A</math>, <math>v</math> is the '''tail''' of <math>a</math>, and <math>w</math> is the '''head''' of <math>a</math>.
## An arc <math>(v,w)\in A</math> is an '''outgoing arc''' of <math>v</math>, and an '''incoming arc''' of <math>w</math>.
## An arc <math>(v,w)\in A</math> is an '''outgoing arc''' of <math>v</math>, and an '''incoming arc''' of <math>w</math>.
## The '''outdegree''' of a node <math>v\in V</math> is the number of its outgoing arcs, the '''indegree''' of <math>v</matH> is the number of its incoming arcs.
## The '''outdegree''' of a node <math>v\in V</math> is the number of its outgoing arcs, the '''indegree''' of <math>v</matH> is the number of its incoming arcs.
'''Statement:'''
If there are no [[#Adjacency, incidence, and degree|isolated nodes]], the number of edges/arcs dominates the number of nodes asymptotically.
'''Proof:'''
In this case, the number of edges/arcs is at least half the number of nodes.
'''Remark:'''
In many algorithmic problems on graphs, isolated nodes may be removed before the algorithm commences.


== Representations of graphs ==
== Representations of graphs ==


We focus on directed graphs <math>G=(V,A)</math> because an undirected graph is usually represented as a symmetric directed graph as introduced [[#Directed and undirected graphs|above]]. Let <math>n:=|V|</math> and <math>m:=|A|</math>. Without loss of generality, we assume <math>V=\{1,\ldots,n\}</math>, and we write <math>A=\{a_1,\ldots,a_m\}</math>..
We focus on directed graphs <math>G=(V,A)</math> because an undirected graph is usually represented as a symmetric directed graph as introduced [[#Directed and undirected graphs|above]]. Let <math>n:=|V|</math> and <math>m:=|A|</math>. Without loss of generality, we assume <math>V=\{1,\ldots,n\}</math>, and we write <math>A=\{a_1,\ldots,a_m\}</math>.
# '''Adjacency matrix:''' an <math>(n\times n)</math>-matrix <math>M</math> wit 0/1 entries such that, for all <math>i,j\in V</math>, <math>M[i,j]=1</math> if, and only if, <math>(i,j)\in A</math>.
# '''Adjacency matrix:''' an <math>(n\times n)</math>-matrix <math>M</math> with 0/1 entries such that, for all <math>i,j\in V</math>, <math>M[i,j]=1</math> if, and only if, <math>(i,j)\in A</math>.
# '''Incidence matrix:''' an <math>(n\times m)</math>-matrix <math>M</math> such that, for <math>i\in\{1,\ldots,n\}</math> and <math>j\in\{1,\ldots,m\}</math>, it is:
# '''Incidence matrix:''' an <math>(n\times m)</math>-matrix <math>M</math> such that, for <math>i\in\{1,\ldots,n\}</math> and <math>j\in\{1,\ldots,m\}</math>, it is:
## <math>M[i,j]=+1</math> if <math>i</math> is the head of <math>a_j</math>.
## <math>M[i,j]=+1</math> if <math>i</math> is the head of <math>a_j</math>.
## <math>M[i,j]=-1</math> if <math>i</math> is the tail of <math>a_j</math>.  
## <math>M[i,j]=-1</math> if <math>i</math> is the tail of <math>a_j</math>.  
## <math>M[i,j]=0</math>, otherwise.  
## <math>M[i,j]=0</math>, otherwise.  
# '''Incidence lists:'''  Each node has a list of its outgoing arcs (possibly, a list of its incoming arcs in addition). Each list is attached to its node. Alternatively, all lists are organized in a separate data structure, for example, an array or a [[Sets and sequences#Maps|map]] such that the list is easily accessible given the node. In each arc, the head and, possibly, the tail are stored as attributes.
# '''Incidence lists:'''  Each node has a list of its outgoing arcs (possibly, a list of its incoming arcs in addition). Each list is attached to its node or, alternatively, all lists are organized in a separate data structure, for example, an array or a [[Sets and sequences#Maps|map]] such that the list is easily accessible given the node. In each arc, the head and, possibly, the tail are stored as attributes.


== Transpose of a graph ==
== Transpose of a graph ==
Line 34: Line 47:


'''Remark:'''
'''Remark:'''
In many applications, the arcs have attributes such as lengths, capacities, cost factors, etc. These attributes are maintained when the arcs are turned.
In many applications, the arcs have attributes such as lengths, capacities, cost factors, etc. These attributes are maintained when the arcs are turned. In most cases, this means they are not changed at all. There are exceptions, for example, cost factors are to be negated in some contexts.


== Subgraphs ==
== Subgraphs ==


# Let <math>G_1=(V_1,E_1)</math> and <math>G_2=(V_2,E_2)</math> be two simple undirected graphs. Then <math>G_1</math> is a '''subgraph''' of <math>G_2</math> if there is <math>V'\subseteq V_2</math> and a bijection <math>\varphi:V_1\rightarrow V'</math> such that <math>\{v,w\}\in E_1</math> implies <math>\{\varphi(v),\varphi(w)\}\in E_2</math>. If <math>\{\varphi(v),\varphi(w)\}\in E_2</math> also implies <math>\{v,w\}\in E_1</math> for all <math>v,w\in V_1</math>, <math>G_1</math> is called the (unique) '''induced subgraph''' of <math>G_2</math> (we say, '''induced''' by <math>V'</math>).
# Let <math>G_1=(V_1,E_1)</math> and <math>G_2=(V_2,E_2)</math> be two simple undirected graphs. Then <math>G_1</math> is a '''subgraph''' of <math>G_2</math> if there is <math>V'\subseteq V_2</math> and a bijection <math>\varphi:V_1\rightarrow V'</math> such that <math>\{v,w\}\in E_1</math> implies <math>\{\varphi(v),\varphi(w)\}\in E_2</math>. If <math>\{\varphi(v),\varphi(w)\}\in E_2</math> also implies <math>\{v,w\}\in E_1</math> for all <math>v,w\in V_1</math>, <math>G_1</math> is called the (unique) '''induced subgraph''' of <math>G_2</math> (we say, '''induced''' by <math>V'</math>).
# Let <math>G_1=(V_1,A_1)</math> and <math>G_2=(V_2,A_2)</math> be two simple directed graphs. Then <math>G_1</math> is a '''subgraph''' of <math>G_2</math> if there is <math>V'\subseteq V_2</math> and a bijection <math>\varphi:V_1\rightarrow V'</math> such that <math>(v,w)\in A_1</math> implies <math>\{\varphi(v),\varphi(w)\}\in A_2</math>. If <math>\{\varphi(v),\varphi(w)\}\in A_2</math> also implies <math>\{v,w\}\in A_1</math> for all <math>v,w\in V'</math>, <math>G_1</math> is called the (unique) '''induced subgraph''' of <math>G_2</math> with respect to <math>V'</math> (we say, '''induced by''' <math>V'</math>).
# Let <math>G_1=(V_1,A_1)</math> and <math>G_2=(V_2,A_2)</math> be two simple directed graphs. Then <math>G_1</math> is a '''subgraph''' of <math>G_2</math> if there is <math>V'\subseteq V_2</math> and a bijection <math>\varphi:V_1\rightarrow V'</math> such that <math>(v,w)\in A_1</math> implies <math>(\varphi(v),\varphi(w))\in A_2</math>. If <math>(\varphi(v),\varphi(w))\in A_2</math> also implies <math>(v,w)\in A_1</math> for all <math>v,w\in V'</math>, <math>G_1</math> is called the (unique) '''induced subgraph''' of <math>G_2</math> with respect to <math>V'</math> (we say, '''induced by''' <math>V'</math>).
# A '''spanning subgraph''' of an undirected or directed graph <math>G</math> is a subgraph that contains all nodes of <math>G</math>.
# A '''spanning subgraph''' of an undirected or directed graph <math>G</math> is a subgraph that contains all nodes of <math>G</math>.


Line 47: Line 60:
# An (ordinary) '''path''' in a directed graph <math>G=(V,A)</math> is a finite  [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k))</math> of arcs.
# An (ordinary) '''path''' in a directed graph <math>G=(V,A)</math> is a finite  [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k))</math> of arcs.
# A '''generalized path''' (a.k.a. '''weak path''') in a directed graph <math>G=(V,A)</math> is a finite sequence <math>((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k))</math> such that turning  some of the arcs yields an ordinary path (possibly, no arc to turn, that is, ordinary paths are generalized paths).
# A '''generalized path''' (a.k.a. '''weak path''') in a directed graph <math>G=(V,A)</math> is a finite sequence <math>((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k))</math> such that turning  some of the arcs yields an ordinary path (possibly, no arc to turn, that is, ordinary paths are generalized paths).
# A path is '''simple''' if it does not meet any node more than most once.
# A node <math>t\in V</math> is '''reachable''' from <math>s\in V</math> if there is a path from <math>s</math> to <math>t</math> in the graph. Depending on the context, the path must be an undirected, an ordinary directed, or a generalized path. Each node is reachable from itself via the trivial path that contains this node only and no edges/arcs.
# The '''internal nodes''' of a path of any kind are all nodes on this path except for the start and the end node (if the start or end node appears more than once on the path, it is also an internal node).
# The '''internal nodes''' of a path of any kind are all nodes on this path except for the start and the end node (if the start or end node appears more than once on the path, it is also an internal node).
# Two paths are '''edge-disjoint''' (resp., '''arc-disjoint''') if they have no edge (arc) in common. They are called '''(internally) node-disjoint''' if they have no node in common that is internal on either path.
# Two paths are '''edge-disjoint''' (resp., '''arc-disjoint''') if they have no edge (arc) in common. They are called '''(internally) node-disjoint''' if they have no node in common that is internal on either path.
Line 55: Line 70:
== Cycles ==
== Cycles ==


# An (ordinary) '''cycle''' in an undirected graph is a finite [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>(\{v_1,v_2\},\{v_2,v_3\}\dots,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_1\})</math> of edges. In other words, a [[#Paths|path]] such that start node and end node are identical.
# An (ordinary) '''cycle''' in an undirected graph is a finite [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>(\{v_1,v_2\},\{v_2,v_3\}\dots,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_1\})</math> of edges; in other words, a [[#Paths|path]] such that start node and end node are identical.
# An (ordinary) '''cycle''' in a directed graph <math>G=(V,A)</math> is a finite [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_1))</math> of arcs. In other words, a [[#Paths|path]] such that start node and end node are identical.
# An (ordinary) '''cycle''' in a directed graph <math>G=(V,A)</math> is a finite [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_1))</math> of arcs; in other words, a [[#Paths|path]] such that start node and end node are identical.
# A '''generalized cycle''' (a..a. '''weak cycle''')in a directed graph <math>G=(V,A)</math> is a finite sequence <math>((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k))</math> such that turning  some of the arcs yields an ordinary cycle (possible, no arc to turn, that is, ordinary cycles are generalized cycles).
# A '''generalized cycle''' (a.k.a. '''weak cycle''')in a directed graph <math>G=(V,A)</math> is a finite sequence <math>((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k))</math> such that turning  some of the arcs yields an ordinary cycle (possibly, no arc to turn, that is, ordinary cycles are generalized cycles).
# An undirected or directed graph is '''acyclic''' (a.k.a. '''cycle-free''') if it contains no ordinary cycle. In the directed case, an acyclic graph is called a '''DAG''' (short for directed acyclic graph).
# A cycle is '''simple''' if no proper part is a cycle of its own.
# An undirected or directed graph is '''acyclic''' (a.k.a. '''cycle-free''') if it contains no ordinary cycle. In the directed case, an acyclic graph is usually called a '''DAG''' (short for directed acyclic graph).
# For <math>s,t\in V</math>, an '''<math>(s,t)</math>-graph''' <math>G=(V,A)</math> is a DAG such that <math>s</math> is the only node with indegree zero, and <math>t</math> is the only node with outdegree zero. It is easy to see that a DAG is an <math>(s,t)</math>-graph if, and only if, <math>G</math> is the union of (not necessarily internally node-disjoint or arc-disjoint) <math>(s,t)</math>-paths.
 
== Forests, trees, branchings, arborescences ==
 
# A '''forest''' is a [[#Cycles|cycle-free]] undirected graph. A '''tree''' is a connected forest.
# A '''branching''' is a [[#Cycles|cycle-free]] directed graph such that the indegree of each node is zero or one. An '''arborescence''' is a branching such that exactly one node has indegree zero (note that, for branchings, this condition is equivalent to weak connectedness). Arborescences are also known as '''rooted trees''', and the unique node with indegree zero is the '''root'''.
# A forest/tree/branching/arborescence '''in a graph''' <math>G</math> is a subgraph of <math>G</math> that is a forest/tree/branching/arborescence. A forest/tree/branching/arborescence is '''spanning''' if it contains all nodes of <math>G</math> (cf. [[#Subgraphs|here]]).
 
'''Statement:'''
For a forest, let <math>n</math> denote the number of nodes, <math>m</math> the number of edges, and <math>k</math> the number of trees in this forest. Then it is <math>m=n-k</math>. In particular, for a tree, it is <math>m=n-1</math>.
 
'''Proof:'''
Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. Then <math>p</math> is not extensible, so its two end nodes have degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.


== Connectedness ==
== Connectedness ==


'''Types of connectedness:'''
'''Types of connectedness:'''
# An undirected graph is said to be '''connected''' if, for each pair of nodes, there is a path connecting this pair. It is <math>k</math>-'''connected''' if each pair of nodes is connected by at least <math>k</math> internally node-disjoint paths. In particular, connected means 1-connected. For <math>k=2</math>, we speak of '''biconnected'''.
# An undirected graph is said to be '''connected''' if, for each pair of nodes, there is a [[#Paths|path]] connecting this pair. It is <math>k</math>-'''connected''' if each pair of nodes is connected by at least <math>k</math> [[#Paths|internally node-disjoint paths]]. In particular, connected means 1-connected. For <math>k=2</math>, we speak of '''biconnected'''.
# A directed graph is said to be '''weakly connected''' if, for each pair of nodes, there is a generalized path connecting this pair. It is even '''strongly connected''' if, for each ordered pair of nodes, there is a path from the first node to the second node.
# A directed graph is said to be '''weakly connected''' if, for each pair of nodes, there is a [[#Paths|generalized path]] connecting this pair. It is even '''strongly connected''' if, for each ordered pair of nodes, there is an [[#Paths|ordinary path]] from the first node to the second node.


'''Links:'''
'''Links:'''
Line 71: Line 100:


'''Connected components:'''
'''Connected components:'''
# The <math>k</math>-'''connected components''' of an undirected graph <math>G=(V,E)</math> are the maximal node sets <math>V'\subseteq V</math> such that the [[#Subgraphs|induced subgraph]] is <math>k</math>-connected. For <math>k=1</math> and <math>k=2</math>, we speak of the '''connected''' and '''biconnected components''', respectively.
# The <math>k</math>-'''connected components''' of an undirected graph <math>G=(V,E)</math> are the [[Sets and sequences#Maximal and minimal sets|inclusion-maximal]] node sets <math>V'\subseteq V</math> such that the subgraph of <math>G</math> [[#Subgraphs|induced by]] <math>V'</math> is <math>k</math>-connected. For <math>k=1</math> and <math>k=2</math>, we speak of the '''connected''' and '''biconnected components''' of <math>G</math>, respectively.
# The '''weak''' and '''strong components''' of a directed graph are the maximal node sets <math>V'\subseteq V</math> such that the [[#Subgraphs|induced subgraph]] is weakly and strongly connected, respectively.
# The '''weakly''' and '''strongly connected components''' ('''weak''' and '''strong components''', for short) of a directed graph <math>G=(V,A)</math> are the [[Sets and sequences#Maximal and minimal sets|inclusion-maximal]] node sets <math>V'\subseteq V</math> such that the subgraph of <math>G</math> [[#Subgraphs|induced by]] <math>V'</math> is weakly and strongly connected, respectively. The term strongly connected component is usually abbreviated by '''SCC'''.


'''Remark:'''
'''Remark:'''
Maximality of the components implies that the components form a partition of the node set in each case.
Inclusion-maximality of the connected components implies that, in each case, the connected components form a partition of the node set.
 
== Bipartite and k-partite graphs ==
 
Let <math>G=(V,E)</math> be an undirected graph.
# <math>G</math> is '''<math>k</math>-partite''' if there is a [[Sets and sequences#Partitions|<math>k</math>-partition]] <math>\{V_1,\ldots,V_k\}</math> of <math>V</math> such that <math>\{v,w\}\not\in E</math> for any pair <math>v,w\in V_i</math> for any <math>i\in\{1,\ldots,k\}</math>.
# For <math>k=2</math>, we say that <math>G</math> is '''bipartite'''.
 
'''Statement:'''
An undirected [[#Connectedness|connected]] graph is bipartite if, and only if, it contains no cycle of odd length.
 
'''Proof:'''
First suppose that <math>G=(V,E)</math> is bipartite with bipartition <math>V=V_1\dot\cup V_2</math>. Let <math>v_1-\cdots-v_k-v_1</math> be the nodes on some cycle in this order. Without loss of generality, let <math>v_1\in V_1</math>. A straightforward induction on <math>i\in\{1,\ldots,k\}</math> shows that <math>v_i\in V_1</math> for <math>i</math> odd and <math>v_i\in V_2</math> for <math>i</math> even. The assumption <math>v_1\in V_1</math> implies <math>v_k\in V_2</math>, so <math>k</math> must be even.
 
Now suppose there is no cycle of odd length in <math>G</math>. Start a  [[Breadth-first search|BFS]] from some start node <math>s\in V</math>. Create a bipartition of <math>V</math> as follows: Each node of even distance from <math>s</math> is in <math>V_1</math>, and all other nodes are in <math>V_2</math>. Suppose for a contradiction that there is an edge <math>\{v,w\}\in E</math> such that either <math>v,w\in V_1</math> or <math>v,w\in V_2</math>. Let <math>u</math> be the last node such that the paths from <math>s</math> to <math>v</math> and <math>w</math> in the arborescence are identical up to <math>u</math> (possibly, <math>u=s</math>). Let <math>p_1</math> and <math>p_2</math> denote the paths from <math>u</math> to <math>v</math> and <math>w</math> in the arborescence. Then the concatenation <math>p_1+p_2+\{v,w\}</math> is a cycle of odd length.
 
== Complete graphs ==
 
# For a positive integral number <math>n</math>, the '''complete graph''' <math>K_n=(V,E)</math> is the unique undirected graph such that <math>|V|=n</math> and all (unordered) pairs of nodes are in <math>E</math>.
# For positive integral numbers <math>m</math> and <math>n</math>, the '''complete bipartite graph''' <math>K_{m,n}=(V_1\dot\cup V_2,E)</math> is the unique undirected graph such that <math>|V_1|=m</math> and <math>|V_2|=n</math>, and each (unordered) pair <math>\{v,w\}</math> with <math>v\in V_1</math> and <math>w\in V_2</math> is in <math>E</math>.

Latest revision as of 14:47, 16 May 2015

Basic definitions

  1. Sets and sequences

Directed and undirected graphs

  1. A directed graph [math]\displaystyle{ G=(V,A) }[/math] consists of a finite set [math]\displaystyle{ V }[/math] of nodes (a.k.a. vertices) and a multiset [math]\displaystyle{ A }[/math] of ordered pairs of nodes. The elements of [math]\displaystyle{ A }[/math] are the arcs of [math]\displaystyle{ G }[/math].
  2. An undirected graph [math]\displaystyle{ G=(V,E) }[/math] consists of a finite set [math]\displaystyle{ V }[/math] of nodes (a.k.a. vertices) and a multiset [math]\displaystyle{ E }[/math] of unordered pairs of nodes, the edges of [math]\displaystyle{ G }[/math].
  3. A directed or undirected graph is simple, if:
    1. No node is paired with itself in [math]\displaystyle{ A }[/math] or [math]\displaystyle{ E }[/math], respectively.
    2. The multisets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ E }[/math], respectively, are sets.
  4. A directed graph [math]\displaystyle{ G=(V,A) }[/math] is symmetric if [math]\displaystyle{ (v,w)\in A }[/math] implies [math]\displaystyle{ (w,v)\in A }[/math], and anti-symmetric if [math]\displaystyle{ (v,w)\in A }[/math] implies [math]\displaystyle{ (w,v)\not\in A }[/math].

Adjacency, incidence, and degree

  1. Two nodes of a directed or undirected graph are called adjacent if they share at least one arc/edge.
  2. A node and an arc/edge are called incident if the node belongs to the arc/edge.
  3. Two arcs/edges are called incident if they share at least one node.
  4. For a node, the number of incident arcs/edges is the degree of this node. A node with degree zero is isolated.
  5. Consider a directed graph [math]\displaystyle{ G=(V,A) }[/math]:
    1. For an arc [math]\displaystyle{ a=(v,w)\in A }[/math], [math]\displaystyle{ v }[/math] is the tail of [math]\displaystyle{ a }[/math], and [math]\displaystyle{ w }[/math] is the head of [math]\displaystyle{ a }[/math].
    2. An arc [math]\displaystyle{ (v,w)\in A }[/math] is an outgoing arc of [math]\displaystyle{ v }[/math], and an incoming arc of [math]\displaystyle{ w }[/math].
    3. The outdegree of a node [math]\displaystyle{ v\in V }[/math] is the number of its outgoing arcs, the indegree of [math]\displaystyle{ v }[/math] is the number of its incoming arcs.

Statement: If there are no isolated nodes, the number of edges/arcs dominates the number of nodes asymptotically.

Proof: In this case, the number of edges/arcs is at least half the number of nodes.

Remark: In many algorithmic problems on graphs, isolated nodes may be removed before the algorithm commences.

Representations of graphs

We focus on directed graphs [math]\displaystyle{ G=(V,A) }[/math] because an undirected graph is usually represented as a symmetric directed graph as introduced above. Let [math]\displaystyle{ n:=|V| }[/math] and [math]\displaystyle{ m:=|A| }[/math]. Without loss of generality, we assume [math]\displaystyle{ V=\{1,\ldots,n\} }[/math], and we write [math]\displaystyle{ A=\{a_1,\ldots,a_m\} }[/math].

  1. Adjacency matrix: an [math]\displaystyle{ (n\times n) }[/math]-matrix [math]\displaystyle{ M }[/math] with 0/1 entries such that, for all [math]\displaystyle{ i,j\in V }[/math], [math]\displaystyle{ M[i,j]=1 }[/math] if, and only if, [math]\displaystyle{ (i,j)\in A }[/math].
  2. Incidence matrix: an [math]\displaystyle{ (n\times m) }[/math]-matrix [math]\displaystyle{ M }[/math] such that, for [math]\displaystyle{ i\in\{1,\ldots,n\} }[/math] and [math]\displaystyle{ j\in\{1,\ldots,m\} }[/math], it is:
    1. [math]\displaystyle{ M[i,j]=+1 }[/math] if [math]\displaystyle{ i }[/math] is the head of [math]\displaystyle{ a_j }[/math].
    2. [math]\displaystyle{ M[i,j]=-1 }[/math] if [math]\displaystyle{ i }[/math] is the tail of [math]\displaystyle{ a_j }[/math].
    3. [math]\displaystyle{ M[i,j]=0 }[/math], otherwise.
  3. Incidence lists: Each node has a list of its outgoing arcs (possibly, a list of its incoming arcs in addition). Each list is attached to its node or, alternatively, all lists are organized in a separate data structure, for example, an array or a map such that the list is easily accessible given the node. In each arc, the head and, possibly, the tail are stored as attributes.

Transpose of a graph

For a directed graph [math]\displaystyle{ G=(V,A) }[/math], the transpose of [math]\displaystyle{ G }[/math] results from [math]\displaystyle{ G }[/math] by turning all arcs.

Remark: In many applications, the arcs have attributes such as lengths, capacities, cost factors, etc. These attributes are maintained when the arcs are turned. In most cases, this means they are not changed at all. There are exceptions, for example, cost factors are to be negated in some contexts.

Subgraphs

  1. Let [math]\displaystyle{ G_1=(V_1,E_1) }[/math] and [math]\displaystyle{ G_2=(V_2,E_2) }[/math] be two simple undirected graphs. Then [math]\displaystyle{ G_1 }[/math] is a subgraph of [math]\displaystyle{ G_2 }[/math] if there is [math]\displaystyle{ V'\subseteq V_2 }[/math] and a bijection [math]\displaystyle{ \varphi:V_1\rightarrow V' }[/math] such that [math]\displaystyle{ \{v,w\}\in E_1 }[/math] implies [math]\displaystyle{ \{\varphi(v),\varphi(w)\}\in E_2 }[/math]. If [math]\displaystyle{ \{\varphi(v),\varphi(w)\}\in E_2 }[/math] also implies [math]\displaystyle{ \{v,w\}\in E_1 }[/math] for all [math]\displaystyle{ v,w\in V_1 }[/math], [math]\displaystyle{ G_1 }[/math] is called the (unique) induced subgraph of [math]\displaystyle{ G_2 }[/math] (we say, induced by [math]\displaystyle{ V' }[/math]).
  2. Let [math]\displaystyle{ G_1=(V_1,A_1) }[/math] and [math]\displaystyle{ G_2=(V_2,A_2) }[/math] be two simple directed graphs. Then [math]\displaystyle{ G_1 }[/math] is a subgraph of [math]\displaystyle{ G_2 }[/math] if there is [math]\displaystyle{ V'\subseteq V_2 }[/math] and a bijection [math]\displaystyle{ \varphi:V_1\rightarrow V' }[/math] such that [math]\displaystyle{ (v,w)\in A_1 }[/math] implies [math]\displaystyle{ (\varphi(v),\varphi(w))\in A_2 }[/math]. If [math]\displaystyle{ (\varphi(v),\varphi(w))\in A_2 }[/math] also implies [math]\displaystyle{ (v,w)\in A_1 }[/math] for all [math]\displaystyle{ v,w\in V' }[/math], [math]\displaystyle{ G_1 }[/math] is called the (unique) induced subgraph of [math]\displaystyle{ G_2 }[/math] with respect to [math]\displaystyle{ V' }[/math] (we say, induced by [math]\displaystyle{ V' }[/math]).
  3. A spanning subgraph of an undirected or directed graph [math]\displaystyle{ G }[/math] is a subgraph that contains all nodes of [math]\displaystyle{ G }[/math].

Paths

  1. An (ordinary) path in an undirected graph is a finite ordered sequence [math]\displaystyle{ (\{v_1,v_2\},\{v_2,v_3\}\dots,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_k\}) }[/math] of edges.
  2. An (ordinary) path in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite ordered sequence [math]\displaystyle{ ((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k)) }[/math] of arcs.
  3. A generalized path (a.k.a. weak path) in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite sequence [math]\displaystyle{ ((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k)) }[/math] such that turning some of the arcs yields an ordinary path (possibly, no arc to turn, that is, ordinary paths are generalized paths).
  4. A path is simple if it does not meet any node more than most once.
  5. A node [math]\displaystyle{ t\in V }[/math] is reachable from [math]\displaystyle{ s\in V }[/math] if there is a path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] in the graph. Depending on the context, the path must be an undirected, an ordinary directed, or a generalized path. Each node is reachable from itself via the trivial path that contains this node only and no edges/arcs.
  6. The internal nodes of a path of any kind are all nodes on this path except for the start and the end node (if the start or end node appears more than once on the path, it is also an internal node).
  7. Two paths are edge-disjoint (resp., arc-disjoint) if they have no edge (arc) in common. They are called (internally) node-disjoint if they have no node in common that is internal on either path.

Remark:

  1. Frequently, a path is viewed as an alternating sequence of the arcs/edges and the nodes on that path.
  2. In simple graphs, a path is often identified with the sequence of nodes on this path.

Cycles

  1. An (ordinary) cycle in an undirected graph is a finite ordered sequence [math]\displaystyle{ (\{v_1,v_2\},\{v_2,v_3\}\dots,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_1\}) }[/math] of edges; in other words, a path such that start node and end node are identical.
  2. An (ordinary) cycle in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite ordered sequence [math]\displaystyle{ ((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_1)) }[/math] of arcs; in other words, a path such that start node and end node are identical.
  3. A generalized cycle (a.k.a. weak cycle)in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite sequence [math]\displaystyle{ ((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k)) }[/math] such that turning some of the arcs yields an ordinary cycle (possibly, no arc to turn, that is, ordinary cycles are generalized cycles).
  4. A cycle is simple if no proper part is a cycle of its own.
  5. An undirected or directed graph is acyclic (a.k.a. cycle-free) if it contains no ordinary cycle. In the directed case, an acyclic graph is usually called a DAG (short for directed acyclic graph).
  6. For [math]\displaystyle{ s,t\in V }[/math], an [math]\displaystyle{ (s,t) }[/math]-graph [math]\displaystyle{ G=(V,A) }[/math] is a DAG such that [math]\displaystyle{ s }[/math] is the only node with indegree zero, and [math]\displaystyle{ t }[/math] is the only node with outdegree zero. It is easy to see that a DAG is an [math]\displaystyle{ (s,t) }[/math]-graph if, and only if, [math]\displaystyle{ G }[/math] is the union of (not necessarily internally node-disjoint or arc-disjoint) [math]\displaystyle{ (s,t) }[/math]-paths.

Forests, trees, branchings, arborescences

  1. A forest is a cycle-free undirected graph. A tree is a connected forest.
  2. A branching is a cycle-free directed graph such that the indegree of each node is zero or one. An arborescence is a branching such that exactly one node has indegree zero (note that, for branchings, this condition is equivalent to weak connectedness). Arborescences are also known as rooted trees, and the unique node with indegree zero is the root.
  3. A forest/tree/branching/arborescence in a graph [math]\displaystyle{ G }[/math] is a subgraph of [math]\displaystyle{ G }[/math] that is a forest/tree/branching/arborescence. A forest/tree/branching/arborescence is spanning if it contains all nodes of [math]\displaystyle{ G }[/math] (cf. here).

Statement: For a forest, let [math]\displaystyle{ n }[/math] denote the number of nodes, [math]\displaystyle{ m }[/math] the number of edges, and [math]\displaystyle{ k }[/math] the number of trees in this forest. Then it is [math]\displaystyle{ m=n-k }[/math]. In particular, for a tree, it is [math]\displaystyle{ m=n-1 }[/math].

Proof: Obviously, it suffices to prove [math]\displaystyle{ m=n-1 }[/math] for trees. This is proved by an induction on the number [math]\displaystyle{ n\geq 1 }[/math] of nodes. For [math]\displaystyle{ n=1 }[/math], it is [math]\displaystyle{ m=0 }[/math], so consider the case [math]\displaystyle{ n\gt 1 }[/math]. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path [math]\displaystyle{ p }[/math] in terms of the number of edges. Then [math]\displaystyle{ p }[/math] is not extensible, so its two end nodes have degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.

Connectedness

Types of connectedness:

  1. An undirected graph is said to be connected if, for each pair of nodes, there is a path connecting this pair. It is [math]\displaystyle{ k }[/math]-connected if each pair of nodes is connected by at least [math]\displaystyle{ k }[/math] internally node-disjoint paths. In particular, connected means 1-connected. For [math]\displaystyle{ k=2 }[/math], we speak of biconnected.
  2. A directed graph is said to be weakly connected if, for each pair of nodes, there is a generalized path connecting this pair. It is even strongly connected if, for each ordered pair of nodes, there is an ordinary path from the first node to the second node.

Links:

  1. An articulation node in a connected undirected graph is a node such that the graph becomes disconnected when this node and its incident arcs are removed.
  2. A bridge in a connected undirected graph is an edge such that the graph becomes disconnected when this edge is removed.

Connected components:

  1. The [math]\displaystyle{ k }[/math]-connected components of an undirected graph [math]\displaystyle{ G=(V,E) }[/math] are the inclusion-maximal node sets [math]\displaystyle{ V'\subseteq V }[/math] such that the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ V' }[/math] is [math]\displaystyle{ k }[/math]-connected. For [math]\displaystyle{ k=1 }[/math] and [math]\displaystyle{ k=2 }[/math], we speak of the connected and biconnected components of [math]\displaystyle{ G }[/math], respectively.
  2. The weakly and strongly connected components (weak and strong components, for short) of a directed graph [math]\displaystyle{ G=(V,A) }[/math] are the inclusion-maximal node sets [math]\displaystyle{ V'\subseteq V }[/math] such that the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ V' }[/math] is weakly and strongly connected, respectively. The term strongly connected component is usually abbreviated by SCC.

Remark: Inclusion-maximality of the connected components implies that, in each case, the connected components form a partition of the node set.

Bipartite and k-partite graphs

Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph.

  1. [math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-partite if there is a [math]\displaystyle{ k }[/math]-partition [math]\displaystyle{ \{V_1,\ldots,V_k\} }[/math] of [math]\displaystyle{ V }[/math] such that [math]\displaystyle{ \{v,w\}\not\in E }[/math] for any pair [math]\displaystyle{ v,w\in V_i }[/math] for any [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math].
  2. For [math]\displaystyle{ k=2 }[/math], we say that [math]\displaystyle{ G }[/math] is bipartite.

Statement: An undirected connected graph is bipartite if, and only if, it contains no cycle of odd length.

Proof: First suppose that [math]\displaystyle{ G=(V,E) }[/math] is bipartite with bipartition [math]\displaystyle{ V=V_1\dot\cup V_2 }[/math]. Let [math]\displaystyle{ v_1-\cdots-v_k-v_1 }[/math] be the nodes on some cycle in this order. Without loss of generality, let [math]\displaystyle{ v_1\in V_1 }[/math]. A straightforward induction on [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math] shows that [math]\displaystyle{ v_i\in V_1 }[/math] for [math]\displaystyle{ i }[/math] odd and [math]\displaystyle{ v_i\in V_2 }[/math] for [math]\displaystyle{ i }[/math] even. The assumption [math]\displaystyle{ v_1\in V_1 }[/math] implies [math]\displaystyle{ v_k\in V_2 }[/math], so [math]\displaystyle{ k }[/math] must be even.

Now suppose there is no cycle of odd length in [math]\displaystyle{ G }[/math]. Start a BFS from some start node [math]\displaystyle{ s\in V }[/math]. Create a bipartition of [math]\displaystyle{ V }[/math] as follows: Each node of even distance from [math]\displaystyle{ s }[/math] is in [math]\displaystyle{ V_1 }[/math], and all other nodes are in [math]\displaystyle{ V_2 }[/math]. Suppose for a contradiction that there is an edge [math]\displaystyle{ \{v,w\}\in E }[/math] such that either [math]\displaystyle{ v,w\in V_1 }[/math] or [math]\displaystyle{ v,w\in V_2 }[/math]. Let [math]\displaystyle{ u }[/math] be the last node such that the paths from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] in the arborescence are identical up to [math]\displaystyle{ u }[/math] (possibly, [math]\displaystyle{ u=s }[/math]). Let [math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p_2 }[/math] denote the paths from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] in the arborescence. Then the concatenation [math]\displaystyle{ p_1+p_2+\{v,w\} }[/math] is a cycle of odd length.

Complete graphs

  1. For a positive integral number [math]\displaystyle{ n }[/math], the complete graph [math]\displaystyle{ K_n=(V,E) }[/math] is the unique undirected graph such that [math]\displaystyle{ |V|=n }[/math] and all (unordered) pairs of nodes are in [math]\displaystyle{ E }[/math].
  2. For positive integral numbers [math]\displaystyle{ m }[/math] and [math]\displaystyle{ n }[/math], the complete bipartite graph [math]\displaystyle{ K_{m,n}=(V_1\dot\cup V_2,E) }[/math] is the unique undirected graph such that [math]\displaystyle{ |V_1|=m }[/math] and [math]\displaystyle{ |V_2|=n }[/math], and each (unordered) pair [math]\displaystyle{ \{v,w\} }[/math] with [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math] is in [math]\displaystyle{ E }[/math].