True/False Indicate whether the
statement is true or false.
|
|
1.
|
Mathematically, a graph is a set V of vertices and a set E of
edges, such that each edge in E connects three of the vertices in V.
|
|
2.
|
Vertices and edges can be labeled or unlabeled.
|
|
3.
|
Two adjacent vertices are also called neighbors.
|
|
4.
|
A vertex is reachable from another vertex if and only if there is a path between
the two.
|
|
5.
|
The weight of a path is the number of edges on the path.
|
|
6.
|
A child of a given graph consists of a subset of that graph’s vertices and
the edges connecting those vertices.
|
|
7.
|
A simple path is a path that does not pass through the same vertex more than
once.
|
|
8.
|
A loop is a path that begins and ends at the same vertex.
|
|
9.
|
Each edge in a digraph is called a directed edge.
|
|
10.
|
Lists and trees are special cases of undirected graphs.
|
Multiple Choice Identify the
choice that best completes the statement or answers the question.
|
|
11.
|
We can use the term ____ as a synonym for vertex.
a. | node | c. | index | b. | element | d. | bucket |
|
|
12.
|
When the edges are labeled with numbers, the graph is said to be a(n) ____
graph.
a. | directed | c. | weighted | b. | undirected | d. | labeled |
|
|
13.
|
One vertex is ____ to another vertex if there is an edge connecting the two
vertices.
a. | contiguous | c. | parent | b. | related | d. | adjacent |
|
|
14.
|
A ____ is a sequence of edges that allows one vertex to be reached from another
vertex in a graph.
a. | route | c. | link | b. | path | d. | chain |
|
|
15.
|
A graph is ____ if there is a path from each vertex to every other
vertex.
a. | directed | c. | weighted | b. | connected | d. | complete |
|
|
16.
|
A graph is ____ if there is an edge from each vertex to every other
vertex.
a. | directed | c. | weighted | b. | connected | d. | complete |
|
|
17.
|
The ____ of a vertex is equal to the number of edges connected to it.
a. | degree | c. | label | b. | weight | d. | level |
|
|
18.
|
A ____ is a subgraph consisting of the set of vertices that are reachable from a
given vertex.
a. | cycle | c. | connected component | b. | digraph | d. | child |
|
|
19.
|
The edges of a(n) ____ have no direction.
a. | simple graph | c. | cycle | b. | undirected graph | d. | digraph |
|
|
20.
|
The edges in a(n) ____ specify an explicit direction.
a. | simple graph | c. | cycle | b. | undirected graph | d. | digraph |
|