Basic DefinitionsΒΆ

  • An undirected graph \(G=(V,E)\) is defined by a set of vertices, \(V\), and a set of edges, \(E\), where each edge in \(E\) is an unordered pair of vertices drawn from \(V\).

  • A weighted undirected graph \(G=(V,E,W)\) is an undirected graph \((V,E)\) with an associated weight function, \(W: E \rightarrow {\mathbb R}_{+}\), that assigns a non-negative real weight to each edge in \(E\).

  • A labeled weighted undirected graph \(G=(V,E,W, L)\) is a weighted undirected graph \((V,E,W)\) with an associated labeling function, \(L\), that assigns a label to each vertex in \(V\). In GraSPI, we label each vertex by a color.

  • A path between a source vertex, \(s \in V\), and a target vertex, \(t \in V\) is a sequence \(p=[v_0, v_1, \dots v_i \dots v_k]\) of vertices such that \(v_o=s\), \(v_k=t\) and for each \(i\) from \(0\) to \(i-1\), vertices \(v_i\) and \(v_{i+1}\) are adjacent in \(G\). The length of path \(p\) is \(\sum_{i=0}^{k-1}w(e(v_i,v_{i+1}))\).

  • A shortest path between a source vertex \(s \in V\) and a target vertex \(t \in V\) is a path between \(s\) and \(t\) that is of the shortest length among all paths between \(s\) and \(t\) in \(G\). The distance between vertices \(s\) and \(t\) in \(G\) is the length of a shortest path between \(s\) and \(t\) in \(G\). If no such path exists, the distance is defined as infinity. Note that the shortest path between a pair of vertices need not be unique, but the distance between them is unique.

  • A subgraph of \(G\) is a graph \(G' = (V', E')\) such that \(V' \subseteq V\) and \(E' \subseteq E\). A vertex-induced subgraph on vertex set \(V' \subseteq V\) is the maximal subgraph with the vertex set \(V'\).

  • A graph \(G\) is connected if there is a path between any pair of vertices in \(G\). A connected component \(C\) in \(G\) is a maximal connected subgraph of \(G\).