Paths, cycles, connectivity
Walks and paths, cycles and circuits, distance and diameter, connectivity of a graph, bridges, reachability and strong connectivity in a directed graph.
- 29 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Chain (walk): what is it?
Show the answer
A sequence of vertices in which any two consecutive vertices are joined by an edge; its number of edges is its length.
A-B-C is a chain of length 2 if A-B and B-C are edges. In an undirected graph it can be read in both directions.
A graph has the edges A-B, B-C, C-D, A-E and E-D. What is the distance from A to D?
2345
Show the answer
2A-E-D links A to D in 2 edges. The chain A-B-C-D (3) also exists, but distance is the shortest one. 5 is the length of the whole cycle, 4 the number of vertices of A-B-C-D.
The … of a vertex is its largest distance to another vertex; the … is the largest eccentricity.
Show the answer
The eccentricity of a vertex is its largest distance to another vertex; the diameter is the largest eccentricity.
The diameter is therefore the largest distance in the graph. It is measured with shortest chains, never with the longest chain.
Directed path: what is it?
Show the answer
A sequence of vertices of a directed structure in which each arc is followed in its own direction, from start to end.
A chain ignores the direction of arcs, a path respects it: with A → B and C → B, A-B-C is a chain but not a path.