Connected graph
A connected graph is a type of graph where there is a path between every pair of vertices. In other words, you can get from any vertex to any other vertex by following the edges of the graph.
Connected graph: a graph where there is a path between every pair of vertices.
Undirected vs. directed graphs
- In an undirected graph, the edges have no direction, so you can traverse them in both directions.
- A connected undirected graph means you can reach any vertex from any other vertex without considering edge directions.
- In a directed graph (or digraph), the edges have a specific direction, so we need to consider the direction of the edges to check if it is possible to get from any vertex to any other vertex.
flashcards
| Question | Answer |
|---|---|
| What is a connected graph? | A graph where there is a path between every pair of vertices. |
| In an undirected graph, what does being connected mean? | You can reach any vertex from any other vertex without considering edge directions. |
| In a directed graph (digraph), how do you check if it is possible to get from any vertex to any other vertex? | You need to consider the direction of the edges. |