Basic graph definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 27: 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]].
== Transpose of a graph ==
For a directed graph <math>G=(V,A)</math>, the '''transpose''' of <math>G</math> results from <math>G</math> by turning all arcs.


== Paths ==
== Paths ==


# A '''path''' in an undirected graph is a finite sequence <math>(e_1,\dots,e_k)</math> of edges such that, for <math>i\in\{1,\ldots,k-1\}</math>, <math>e_i</math> and <math>e_{i+1}</math> are incident.
# A '''path''' in an undirected graph is a finite sequence <math>(\{v_1,v_2\},\{v_2,v_3\}\dots,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_k\})</math> of edges such that, for <math>i\in\{1,\ldots,k-1\}</math>, <math>e_i</math> and <math>e_{i+1}</math> are incident.
# An (ordinary) '''path''' in a directed graph <math>G=(V,A)</math> is a finite sequence <math>((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k))</math>.
# An (ordinary) '''path''' in a directed graph <math>G=(V,A)</math> is a finite sequence <math>((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k))</math>.
# A '''generalized 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 (possible, no arc to turn, that is, ordinary paths are generalized paths).
# A '''generalized 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 (possible, no arc to turn, that is, ordinary paths are generalized paths).
Line 44: Line 48:
# A directed graph is said to be '''strongly connected''' if, for each ordered pair of nodes, there is a path from the first node to the second one.
# A directed graph is said to be '''strongly connected''' if, for each ordered pair of nodes, there is a path from the first node to the second one.


== Transpose of a graph ==
== Cycles ==


For a directed graph <math>G=(V,A)</math>, the '''transpose''' of <math>G</math> results from <math>G</math> by turning all arcs.
# A '''cycle''' in an undirected

Revision as of 12:45, 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.

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.

Paths

  1. A path in an undirected graph is a finite 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 such that, for [math]\displaystyle{ i\in\{1,\ldots,k-1\} }[/math], [math]\displaystyle{ e_i }[/math] and [math]\displaystyle{ e_{i+1} }[/math] are incident.
  2. An (ordinary) path in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite sequence [math]\displaystyle{ ((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k)) }[/math].
  3. A generalized 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 (possible, no arc to turn, that is, ordinary paths are generalized paths).

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.

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 from the first node to the second one.

Cycles

  1. A cycle in an undirected