Basic graph definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 12: Line 12:
# Two nodes of a directed or undirected graph are called '''adjacent''' if they share at least one arc/edge.
# Two nodes of a directed or undirected graph are called '''adjacent''' if they share at least one arc/edge.
# 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.
# 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.
# Consider a directed graph <math>G=(V,A)</math> and a node <math>v\in V</math>:
# Consider a directed graph <math>G=(V,A)</math> and a node <math>v\in V</math>:
Line 26: Line 27:
## <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, or all lists are organized in a separate data structure, for example, an array or a [[Sets and sequences#Maps|map]].
# '''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 all lists are organized in a separate data structure, for example, an array or a [[Sets and sequences#Maps|map]].
== Paths ==
# A '''path''' in an undirected graph is a sequence <math>


== Connectedness ==
== Connectedness ==

Revision as of 12:23, 20 October 2014

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] and [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.
  5. Consider a directed graph [math]\displaystyle{ G=(V,A) }[/math] and a node [math]\displaystyle{ v\in V }[/math]:
    1. An arc [math]\displaystyle{ (v,w)\in A }[/math] is an outgoing arc of [math]\displaystyle{ v }[/math], and an arc [math]\displaystyle{ (w,v)\in A }[/math] is an incoming arc of [math]\displaystyle{ v }[/math].
    2. The outdegree of [math]\displaystyle{ v }[/math] is the number of its outgoing arcs, the indegree of [math]\displaystyle{ v }[/math] is the number of its incoming arcs.

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] wit 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 all lists are organized in a separate data structure, for example, an array or a map.

Paths

  1. A path in an undirected graph is a sequence <math>

Connectedness

  1. An undirected graph is said to be connected if, for each pair of nodes, there is a path connecting this pair.
  2. A directed graph is said to be weakly connected if, for each pair of nodes, there is a generalized path connecting this pair.
  3. A directed graph is said to be strongly connected if, for each ordered pair of nodes, there is a path fro the first node to the second one.