Basic graph definitions: Difference between revisions
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
- 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].
- 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].
- A directed or undirected graph is simple, if:
- No node is paired with itself in [math]\displaystyle{ A }[/math] and [math]\displaystyle{ E }[/math], respectively.
- The multisets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ E }[/math], respectively, are sets.
- 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
- 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.
- 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.
- Consider a directed graph [math]\displaystyle{ G=(V,A) }[/math] and a node [math]\displaystyle{ v\in V }[/math]:
- 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].
- 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]..
- 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].
- 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:
- [math]\displaystyle{ M[i,j]=+1 }[/math] if [math]\displaystyle{ i }[/math] is the head of [math]\displaystyle{ a_j }[/math].
- [math]\displaystyle{ M[i,j]=-1 }[/math] if [math]\displaystyle{ i }[/math] is the tail of [math]\displaystyle{ a_j }[/math].
- [math]\displaystyle{ 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 map.
Paths
- A path in an undirected graph is a sequence <math>
Connectedness
- An undirected graph is said to be connected if, for each pair of nodes, there is a path connecting this pair.
- A directed graph is said to be weakly connected if, for each pair of nodes, there is a generalized path connecting this pair.
- 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.