Graph theory Flashcards
1
Q
Walk
A
Nodes may repeat, edges may repeat (closed or open)
2
Q
Trail
A
Nodes may repeat, edges cannot repeat (open)
3
Q
Circuit
A
Nodes may repeat, edges cannot repeat (closed)
4
Q
Path
A
Nodes cannot repeat, edges cannot repeat (open)
5
Q
Cycle
A
Nodes cannot repeat, edges cannot repeat (closed)
6
Q
Diameter
A
The max. distance between any pair of nodes in the graph
7
Q
Average distance
A
Ave. distance over all pairs of nodes in the graph
8
Q
Directed
A
edges point from one node to another
9
Q
Strongly connected component (SCC) - directed graph
A
in a subset of the nodes: i) every node in the subset has a path to every other, and ii) the subset is not part of some larger set with the property that every node can reach every other
