Sort each term or description by what it is a property of.
Groups: A property of a single vertex · A description of a path or cycle · A property of the whole graph
- Connected
- Acyclic
- Degree
- The number of edges meeting at this point
- A sequence of vertices in which each is joined to the next by an edge
- A route that returns to the vertex it started from
Hints
- Ask what you would have to look at to check each one: a single point, a route through the graph, or everything at once.
- Two items are the same idea stated once as a word and once as a definition.
Show the answer
A property of a single vertex: Degree, The number of edges meeting at this point
A description of a path or cycle: A route that returns to the vertex it started from, A sequence of vertices in which each is joined to the next by an edge
A property of the whole graph: Connected, Acyclic
Degree is local, measured at one vertex. Paths and cycles are routes through the graph. Connectedness and acyclicity are global: you cannot confirm either by inspecting one vertex. Sorting terms this way is the fastest way to keep graph vocabulary straight, because the level a term lives at determines what you must examine to test it.
Practise Graphs and Trees
The app has 4 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Graphs and Trees
- A social network is a graph, a filesystem is a tree, and a tree is a graph. What does the extra restriction…
- Select every statement that must be true of any tree with n vertices.
- The handshaking lemma says the degrees of all vertices sum to twice the number of edges. Why must the total…
- A connected graph with 8 vertices and 8 edges must contain a cycle.