G = (V, E) - graph

V - finite set of vertices

E C V x V (subset of pairs of vertices)

Undirected graph - pair is not ordered. Edge or line.
Directed graph (digraph) - pair is ordered (source, target). Arc or arrow.

Origin (source) and destination (target) of an arc. Adjacent vertices, incident edge and vertex. Outgoing and incoming edges, degree of a vertex, in-degree, out-degree. Neighbours.

If E is a multiset (duplicate elements are allowed), the graph is called a multigraph. Multiple (parallel) edges or arcs are allowed in the multigraph.

Pair (v, v) from E is called a self-loop.

Undirected graph without multiple edges and self-loops is called a simple graph.

Graph G = (V, 0) is called a  null graph (set of edges is empty).

Simple graph G = (V, VxV \ {(v, v)| v belongs to V})  is called a full graph (all vertices are neighbours).

Path  from vertex u to vertex v is a sequence of arcs connected in the following way:

(u, w₀), (w₀, w₁), ... , (w_n, v) belong to E .

Undirected graph is called connected (directed graph is called strongly connected) if there exists a path from each vertex to each other vertex.

Directed graph is called weakly connected, if after leaving out all directions the resulting undirected graph is connected.

Graph G₁ = (V₁, E₁) is called a subgraph of  G = (V, E), if V₁ is a subset of V and E₁ is an intersection of E and V₁xV₁. NB! E₁ is not a subset of this intersection (that is called a block), the subgraph includes all possible arcs.

Adjacency matrix:

|V|x|V| matrix A=a[i, j], where

a[i, j] = 1, if arc (i, j) belongs to E, and a[i, j] = 0 otherwise.

For a multigraph  a[i, j] is a number of arcs from vertex i to vertex j.

Multiplication of graphs is defined as follows.
Product of  G₁=(V, E₁)  and  G₂=(V,E₂)  is a graph  G=(V, E), where

E = { (u, v) belongs to VxV | there exists a vertex w from V such that:
(u, w)  belongs to E₁ and (w, v) belongs to E₂ }.

Transitive closure G⁺ is a result of adding to source graph G all arcs (u, v), for which in G there exists a path from vertex u to vertex v:

G⁺ = G + GG + GGG + ...

Adding self-loops to the transitive closure we get a reflexive transitive closure:

G^* = G⁺ + {(v, v) | v is in V}
G^*G = GG^* = G⁺

From Wikipedia:

A walk is an alternating sequence of vertices and edges, starting and ending at a vertex, in which each edge is adjacent in the sequence to its two endpoints. In a directed graph the ordering of the endpoints of each edge in the sequence must be consistent with the direction of the edge. Some sources call walks paths, while others reserve the term "path" for a simple path (a walk without repeated vertices or edges). Walks are also sometimes called chains.^[10] A walk is open if its starts and ends at two different vertices, and closed if it starts and ends at the same vertex. A closed walk may also be called a cycle. Alternatively, the word "cycle" may be reserved for a simple closed walk (one without repeated vertices or edges except for the repetition of the starting and final vertex). A walk without repeated edges (but with vertex repetition allowed) may be called a trail and a closed trail may be called a tour.

Trail is a path, where arcs do not repeat.

Simple trail is a trail, where vertices do not repeat.

Cycle is a closed trail (trail of positive length from vertex to itself).

Simple cycle is a closed simple trail.

Theorem: each cycle is a union of simple cycles.

Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once.

Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.

Matrix of weights - elements are weights of edges (zero, if there is no edge between i and j).

Set of outgoing arcs from vertex v:

Adj(v) = {e in E | there exists w in V such that: e=(v,w)}

Adjacency list structure is a set:

{ (v, Adj(v) ) | v belongs to V }

Graph representations

1. Graphical representation (see also planar graphs).

2. Collection of arcs (assuming that there is information about endpoints somewhere).

Lists - e.g. adjacency list.

3. Adjacency matrix, incidence matrix, other matrices.

4. Pointer structures.

Graph representation using adjacency list

E={ (A,B), (A,C), (A,D), (B,C), (C,D) }

Graph problems

Traversal of the adjacency structure

Example: toString

   /**
    * Creates textual representation for the graph.
    */
   public String toString() { 
      StringBuffer result = new StringBuffer ("");
      String nl = System.getProperty ("line.separator");
      result.append (nl + "Graph: " + getId().toString());
      Iterator vertIt = vertices();
      while (vertIt.hasNext()) {
	 Vertex vert = (Vertex)vertIt.next();
	 result.append (nl + vert.toString());
	 result.append (" --> ");
	 Iterator outeIt = vert.outEdges();
	 while (outeIt.hasNext()) {
            Edge e = (Edge)outeIt.next();
	    Vertex v2 = e.getToVert();
	    result.append (v2.toString() + " ");
	    result.append ( "(" + e.toString());
	    result.append ( ") " );
         }
      }
      result.append (nl);
      return result.toString();
   } 

Building the adjacency matrix

   /**
    * Builds the matrix for a given graph.
    * @param g graph
    * @return adjacency matrix 
    */
   public static AdjMatrix getAdjMatrix (Graph g) {
      int n = 0;
      Iterator vit = g.vertices();
      while (vit.hasNext()) {
         n++;
         Vertex v = (Vertex)vit.next();
         v.setVInfo (n);
      }
      AdjMatrix result = new AdjMatrix (2*n + 1); // double size!!!
      result.setNvert (n);
      Iterator eit = g.edges();
      while (eit.hasNext()) {
         Edge e = (Edge)eit.next();
         int i = e.getFromVert().getVInfo() - 1;
         int j = e.getToVert().getVInfo() - 1;
         result.set (i, j, result.get (i, j)+1);
      }
      return result;
   }

Lenghts of shortest paths (Floyd-Warshall algorithm)

Problem. Find the matrix of shortest distances between all pairs of distinct vertices.

We can use the adjacency matrix or matrix of distances (arclenghts).
1. Eliminate duplicate arcs and self-loops
2. In case of adjacency matrix: consider the length of an arc equal to one unit, if there is no arc, consider the length equal to infinity.
3. Apply Floyd-Warshall algorithm

   /**
    * Converts adjacency matrix to the matrix of distances.
    * @param mat adjacency matrix
    * @return matrix of distances, where each edge has length 1
    */
   public static DistMatrix getDistMatrix (AdjMatrix mat) {
      int nvert = mat.getNvert();
      DistMatrix result = new DistMatrix (nvert);
      result.setNvert (nvert);
      if (nvert < 1) return result;
      int INFINITY = 2*nvert + 1; // Integer.MAX_VALUE / 2; // NB!!!
      for (int i=0; i<nvert; i++) {
         for (int j=0; j<nvert; j++) {
            if (mat.get (i, j) == 0) {
               result.set (i, j, INFINITY);
            } else {
               result.set (i, j, 1);
            }
         }
      }
      for (int i=0; i<nvert; i++) {
         result.set (i, i, 0);
      }
      return result;
   }

   /**
    * Calculates shortest paths using Floyd-Warshall algorithm.
    * This matrix will contain shortest paths between each pair of vertices.
    */
   public void shortestPaths() {
      int n = getNvert(); // number of vertices
      if (n < 1) return;
      for (int k=0; k<n; k++) {
         for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
               int newlength = get (i, k) + get (k, j);
	       if (get (i, j) > newlength) {
                  set (i, j, newlength); // new path is shorter
               }
            }
         }
      }
   }

    

Complexity: O(n³), where n is number of vertices

Topological sort of vertices of an acyclic graph:

Find the order of vertices < such, that for each arc (i,j) inequality i < j holds. Partial order defined by arcs needs to be "packed" into linear order <.

Topological sort

   /**
    * Topological sort of vertices.
    * For each vertex vInfo=0 if the graph cannot be sorted,
    * otherwise vInfo is the ordinal number of the vertex.
    */
   public void topolSort() {
      boolean cycleFound = false;
      List order = Collections.synchronizedList (new LinkedList());
      setGInfo (0); // count number of vertices
      Iterator vit = vertices();
      while (vit.hasNext()) {
         ((Vertex)vit.next()).setVInfo (0);
	 setGInfo (getGInfo() + 1);
      }
      Iterator eit = edges();
      while (eit.hasNext()) {
         Edge e = (Edge)eit.next();
	 Vertex v = e.getToVert();
	 // count number of incoming edges
	 v.setVInfo (v.getVInfo() + 1);
      }
      List start = Collections.synchronizedList (new LinkedList());
      vit = vertices();
      while (vit.hasNext()) {
         Vertex v = (Vertex)vit.next();
	 if (v.getVInfo() == 0) {
            start.add (v); // no incoming edges
         }
      }
      if (start.size() == 0) cycleFound = true;
      while ((!cycleFound)&(start.size() != 0)) {
         Vertex current = (Vertex)start.remove (0); // first vertex
	 order.add (current);
	 eit = current.outEdges(); // "remove" outgoing edges
	 while (eit.hasNext()) {
            Edge e = (Edge)eit.next();
	    Vertex v = e.getToVert();
	    v.setVInfo (v.getVInfo() - 1);
	    if (v.getVInfo() == 0) {
               start.add (v); // no incoming edges anymore
            }
         }
      }
      if (getGInfo() != order.size()) cycleFound = true;
      if (cycleFound) {
         Iterator it = vertices();
	 while (it.hasNext()) {
            Vertex v = (Vertex)it.next();
	    v.setVInfo (0);
         }
      } else {
         int i = 0;
	 Iterator it = order.iterator();
	 while (it.hasNext()) {
            i++;
	    Vertex v = (Vertex)it.next();
	    v.setVInfo (i);
         }
      }
      setGInfo (0);
      return;
   } // end of topolSort()