Graph

From NovaOrdis Knowledge Base
Jump to: navigation, search

Internal

Concepts

A graph G is a pair (V, E), where V is a finite set of vertices, called the vertex set of G, and E is a binary relation on G, called the edge set of G.

An elements of the vertex set V is called vertex (plural vertices). An alternate term for vertex, used sometimes in the graph theory literature, is node. We prefer to use the term "node" when we refer to the vertices of rooted trees. We use "vertex" as a more generic term that refers to graphs in general. Another alternate name is entity.

The element of the edge set E are called edges (also known as relationships or arcs). By convention, we use (u, v) notation for an edge, where u and v represent vertices in V. The order in which vertices are specified for an edge may be relevant. If the order in which the vertices are specified matters, then the graph is a directed graph. If the order in which the vertices are specified does not matter, then the graph is an undirected graph.

Graph Directionality

Directed Graph

A directed graph is a (V, E) pair where the edge set E contains directed edges: the order in which the vertices are specified when the edge is defined matters. For a directed graph, (u, v) and (v, u) are distinct edges. That is why we sometimes write the edge as u → v and v → u.

Graph Directed.png

A characteristic of a directed graph is that self-loops, edges from a vertex to itself, are allowed. A self-loop is a cycle of length 1.

A directed graph with no self-loops is simple.

If (u, v) is an edge in a directed graph G = (V, E), we say that (u, v) is:

  • incident from, or leaves vertex u. Another formulation is that u is the tail vertex.
  • incident to, or enters, vertex v. v is the head vertex.

In the example above, edges (2, 2), (2, 4) and (2, 5) leave vertex 2, and (2, 2) and (1, 2) enter vertex 2.

Undirected Graph

An undirected graph is a (V, E) pair where the edge set E contains undirected edges: the order in which the vertices are specified when the edge is defined does not matter and (u, v) is equivalent with (v, u) - they are considered to be the same edge. Another way to define an unordered graph is that its edges are sets {u, v} where u, v ∈ V and u ≠ v.

Graph Undirected.png

Self-loops are not allowed in an undirected graph. Every edge consists of two distinct vertices.

If (u, v) is an edge in an undirected graph G = (V, E), we say that (u, v) is incident on both vertices u and v. In the example above, edges incidents on vertex 2 are (1, 2) and (2, 5).

An undirected graph in which each pair of vertices is adjacent is called a complete graph.

A forest is an acyclic, undirected graph. Note that the graph may be disconnected.

A tree is a connected, acyclic, undirected graph. A tree defined as such is sometimes referred to as a free tree. More details about trees are available in the Tree Concepts section.

Vertex Adjacency

If (u, v) is an edge in a graph G = (V, E), we say that the vertex v is adjacent to vertex u. In other words, if two vertices have an edge connecting them, they are adjacent. For undirected graphs, the adjacency relation is symmetric: if vertex u is adjacent to vertex v, then automatically vertex v is adjacent to vertex u. This is not the case for directed graphs.

Vertex Degree

The vertex degree is the count of edges incident on, from and to the vertex, depending on the type of the graph.

For undirected graphs, the vertex degree is the number of edges incident on the vertex, which is the same with the number of adjacent vertices. In the example above, the vertex 2 has degree 2.

For directed graphs, we define the in-degree as the number of edges entering the vertex and the out-degree as the number of edges exiting the vertex. The degree of the vertex is the sum of in-degree and out-degree. In the example above, vertex 2 has an in-degree 2, out-degree 3 and degree 5.

Paths

A path of length k from a vertex u to a vertex u' in a graph G = (V, E) is a sequence (v0, v1, ..., vk) of vertices such that u = v0, u' = vk and the edge (vi-1, vi) ∈ E for i = 1, 2, ... k. Some sources refer to a path as a "walk".

The length of the path is the number of edges in the path.

We say that the path contains the vertices v0, ..., vk and the edges (v0, v1), (v1, v2), ..., (vk-1, vk).

There is always a zero-length path from u to u.

If there is a path p from u to u', we say that u' is reachable from u via path p.

A path is simple if all vertices in it are distinct. In the directed graph example above, the path (1, 2, 5, 4) is a simple path of length 3. The path (2, 5, 4, 5) is not simple.

A subpath of a path p = (v0, v1, ..., vk) is a contiguous subsequence of its vertices: for any 0 ≤ i ≤ j ≤ k, the subsequence of vertices (vi, vi+1, ..., vj) is a subpath.

Cycles

Directed Graphs Cycles

For directed graphs, a path (v0, v1, ... vk) forms a cycle if v0 = vk and the path contains at least one edge. The cycle is simple if, in addition, v1, v2, ... vk are distinct.

A self-loop is a cycle of length 1.

Two paths (v0, v1, ...., vk-1, v0) and (v'0, v'1, ...., v'k-1, v'0) form the same cycle if there exists an integer j such that v'i = v(i + j) mod k for i = 0, 1, ..., k - 1.

Undirected Graphs Cycles

For undirected graphs, a path (v0, v1, ..., vk) forms a cycle if k ≥ 3 and v0 = vk. The circle is simple if v1, v2, ..., vk are distinct.

Acyclic Graphs

An acyclic graph is a graph that has no cycles.

Directed Acyclic Graph

Wikipedia Directed Acyclic Graph

A directed acyclic graph is sometimes abbreviated to DAG.

One of the practical applications of DAGs is to model dependencies between entities: a directed edge between vertices u and v means that u "depends on" v.

Directed acyclic graph algorithms:

Connectivity and Graph Components

An undirected graph is connected if every vertex is reachable from all other vertices. The connected components of a graph are the equivalence classes of vertices under the "is reachable from" relation. The undirected graph example above has three connected components: {1, 2, 5}, {3, 6} and {4}. The edges of a connected component are those that are incident on only the vertices of the component; in other words, edge (u, v) is an edge of a connected component only if both u and v are vertices of the component.

An entire undirected graph is connected if it has exactly one connected component.

A directed graph is strongly connected if every two vertices are reachable from each other. The strongly connected components of a directed graph are the equivalence classes of vertices under are mutually reachable relation.

An entire directed graph is strongly connected if it has only one strongly connected component.

Isomorphic Graphs

Two graphs G = (V, E) and G' = (V', E') are isomorphic if there exists a bijection f : V → V' such that (u, v) ∈ E if and only if (f(u), f(v)) ∈ E'. This also can be expressed as follows: we can relabel the vertices of G to be vertices of G', maintaining the corresponding edges in G and G'.

Subgraphs

We say that a graph G' = (V', E') is a subgraph of G = (V, E) if V' ⊆ V and E' ⊆ E.

Given a set V' ⊆ V, the subgraph of G induced by V' is the graph G' = (V', E') where E' = {(u, v) ∈ E: u, v ∈ V'}.

Contraction

The contraction of an undirected graph G = (V, E) by an edge e = (u, v) is a graph G' = (V', E') where V' = V - {u, v} ⋃ {x} and x is a new vertex. The set of edges E' is formed from E by deleting the edge (u, v) and, for each vertex w incident on u or v, deleting whichever of (u, w) and (v, w) is in E and adding the new edge (x, w). In effect, u and v are "contracted" into a single vertex.

Sparse Graphs

A sparse graph is a graph for which |E| is much less than |V|2.

Dense Graphs

A dense graph is a graph for which |E| is close to |V|2.

Representing Graphs in Computer Memory

TODO CLRS page 589, DDIA location 1392.

Adjacency Lists

Applies to directed and undirected graphs.

An adjacency list representation provides a memory-efficient way of representing sparse graphs, so it is usually the method of choice.

Continue CLRS page 590.

Adjacency Matrices

Applies to directed and undirected graphs.

Cases when adjacency matrix representation is preferred:

  • dense graphs.
  • When we need to tell quickly if there is an edge connecting two given vertices.

Continue CLRS page 590.

Searching a Graph

Searching a graph means systematically following the edges of a graph so we visit all the vertices of that graph. Techiques for searching a graph lie at the heart of the field of graph algorithms.


Breadth-First Search

TODO CLRS page 594.

Depth-First Search

TODO CLRS page 603.

Graph Algorithms