Section 7.3 Paths
A path between two vertices \(u\) and \(v\) is a sequence of consecutive edges starting at \(u\) and ending at \(v\text{.}\)
To get all paths between two vertices:
The length of a path is defined as the number of edges that make up the path.
Finding the shortest path between two vertices can be achieved using the
shortest_path() function:A graph is said to be connected if there is a path between any two vertices in the graph.
To determine if a graph is connected, we can use the
is_connected() function:A connected component of a graph \(G \) is a maximal connected subgraph of \(G \text{.}\) If the graph \(G \) is connected, then it has only one connected component.
For example, the following graph is not connected:
To identify all connected components of a graph, the
connected_components() function can be utilized:We can visualize the graph as a disjoint union of its connected components, by plotting it.
The diameter of a graph is the length of the longest shortest path between any two vertices.
A graph is bipartite if its set of vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set:
