Graph Algorithms I

graph-algo.md

Graph Algorithms I

Outline:

• Prerequisite Terminology.
• Mathematical Structures for representing graphs.
• Graph traversal algorithms.

Terminology:

• Directed graph (Or Digraph): a directed path that is composed of vertexes and edges; where edges are essentially represented by directed arcs from a vertex (known as initial vertex) to another vertex (known as terminating or end vertex).
• Undirected graph (or Multigraph): a non-directed path that is composed of vertexes and edges; where edges are represented by non-directed arcs from a vertex to another vertex (i.e., orientation of arcs are ignored).
• Adjacency Matrix Representation:
  • Definition: an adjacency matrix $$m$$ is $$n \times n$$ matrix; where rows $$i$$ and columns $$j$$ headers represent the vertexes, and the $$m_{ij}$$ enteries represent the number of the arcs from a vertex $$i$$ on the $$i^{th}$$ row to vertex $$j$$ on the $$j^{th}$$ column.
  • Properties: Let M denote the adjacency matrix of a graph $$G(X, E)$$; where $$X$$ is the set of all vertexes, and $$E$$ is the set of all edges connecting vertexes. Then, by the definition of the adjacency matrix, we have the following properties:
  • For a directed or a digraph:
    • 1. The sum of the entries of the $$i^{th}$$ row of M is equal to the out-degree of the vertex i.
    • 2. The sum of the entries of the $$j^{th}$$ column of M is equal to the in-degree of the vertex j.
  • For a non-directed graph or a multigraph:
    • 1, 2. The sum of the entries of the ith row of M is the degree of the vertex i.
  • For all types of graphs:
    • 3. The sum of all the entries of the matrix M is the number of arcs of the graph.
• Incidence Matrix Representation:
  • Definition: an incidence matrix $n \times m$; where $$n$$ is the number of rows, and $$m$$ is the number of columns, in this case representing the arcs, encodes the incident of arcs in the form of integer codes (e.g., 0b01 and 0b10); the incident of an arc with respect to a vertex is encoded together with its orientation if necessary.
  • Properties: Let matrix M denote an incidence matrix to the Graph $$G(X, E)$$; where the set $$X$$ is the set of all vertexes, and $$E$$ is the set of all edges or arcs connecting vertexes. Hence, the following holds:
  • For a directed or a digraph:
    • 1. $$m_{ij} = 1$$ if $$i$$ is the initial vertex.
    • 2. $$m_{ij} = -1$$ if $$i$$ is the final vertex.
    • 3. $$m_{ij} = 2$$ if the edge $$e_j$$ is a loop at vertex $$i$$.
    • 4. $$m_{ij} = 0$$ otherwise.
    • 5. The sum of entries of every column except the ones which represent loops is 0.
    • 6. The sum of entries of every column representing a loop is 2.
    • 7. The sum of entries of the ith row (not containing the entry 2) is $$d^{+}(i)−d^{-}(i)$$.
  • For a non-directed or a multi-graph:
    • 1. $$m_{ij} = 1$$ if the vertex $$i$$ is incident with the edge $$e_j$$.
    • 2. $$m_{ij} = 2$$ if the edge $$e_j$$ is a loop at vertex $$i$$.
    • 3. $$m_{ij} = 0$$ otherwise.
    • 4. The sum of every column entry of an incidence matrix for a multigraph is 2.
    • 5. The sum of the entries of the i-th row of an incidence matrix is the degree of the vertex $$i$$ which is $$d(i)$$.
• Adjacency List Representation:
• Sparse Trees.
• Simple Trees.
• Minimum Spanning Trees.
• Unique elementary path.