Deck 14: Graphs

Question 1

A ______ is the subset of vertices visited during a traversal that begins at a given vertex.

A)circuit
B)multigraph
C)digraph
D)connected component

Answer 1

D

Question 2

A graph is ______ if each pair of distinct vertices has a path between them.

A)complete
B)disconnected
C)connected
D)full

Answer 2

C

Question 3

A ______ order is a list of vertices in a directed graph without cycles such that vertex x precedes vertex y if there is a directed edge from x to y in the graph.

A)graphical
B)topological
C)hierarchal
D)spatial

Answer 3

B

Question 4

A graph consists of ______ sets.

A)two
B)three
C)four
D)five

Question 5

Two vertices that are joined by an edge are said to be ______ each other.

A)related to
B)bordering
C)utilizing
D)adjacent to

Question 6

A self edge is also called a ______.

A)cycle
B)loop
C)circuit
D)multigraph

Question 7

A graph is ______ if it has at least one pair of vertices without a path between them.

A)complete
B)disconnected
C)connected
D)full

Question 8

In a graph,a vertex is also known as a(n)______.

A)node
B)edge
C)path
D)cycle

Question 9

If there is a directed edge from vertex x to vertex y,which of the following can be concluded about x and y?

A)y is a predecessor of x
B)x is a successor of y
C)x is adjacent to y
D)y is adjacent to x

Question 10

A ______ can have duplicate edges between vertices.

A)spanning tree
B)connected graph
C)complete graph
D)multigraph

Question 11

A path is a sequence of ______ in a graph.

A)vertices
B)edges
C)subgraphs
D)cycles

Question 12

Which of the following is true about a simple cycle?

A)it can pass through a vertex more than once
B)it can not pass through a vertex more than once
C)it begins at one vertex and ends at another
D)it passes through only one vertex

Question 13

The ______ of a weighted graph have numeric labels.

A)vertices
B)edges
C)paths
D)cycles

Question 14

All ______ begin and end at the same vertex and do not pass through any other vertices more than once.

A)paths
B)simple paths
C)cycles
D)simple cycles

Question 15

A graph-traversal algorithm stops when ______.

A)it first encounters the designated destination vertex
B)it has visited all the vertices that it can reach
C)it has visited all the vertices
D)it has visited all the vertices and has returned to the vertex that it started from

Question 16

A subset of a graph's vertices and edges is known as a ______.

A)bar graph
B)line graph
C)subgraph
D)circuit

Question 17

An iterative DFS traversal algorithm uses a(n)______.

A)list
B)array
C)queue
D)stack

Question 18

An iterative BFS traversal algorithm uses a(n)______.

A)list
B)array
C)queue
D)stack

Question 19

The edges in a ______ indicate a direction.

A)graph
B)multigraph
C)digraph
D)spanning tree

Question 20

A complete graph has a(n)______ between each pair of distinct vertices.

A)edge
B)path
C)cycle
D)circuit

Question 21

A ______ is a special cycle that passes through every vertex in a graph exactly once.

A)multigraph
B)tree
C)spanning tree
D)circuit

Question 22

Adjacent vertices are joined by an edge.

Question 23

A(n)______ begins at a vertex v,passes through every vertex exactly once,and terminates at v.

A)multigraph
B)spanning tree
C)Euler circuit
D)Hamilton circuit

Question 24

A connected graph has an edge between every pair of vertices.

Question 25

A graph's edges cannot begin and end at the same vertex.

Question 26

A connected undirected graph that has n vertices must have at least ______ edges.

A)n
B)n - 1
C)n / 2
D)n * 2

Question 27

A(n)______ begins at a vertex v,passes through every edge exactly once,and terminates at v.

A)multigraph
B)spanning tree
C)Euler circuit
D)Hamilton circuit

Question 28

In a digraph,there can be only one edge between a pair of vertices.

Question 29

The sum of the weights of the edges of a path can be called all of the following EXCEPT ______.

A)length
B)weight
C)height
D)cost

Question 30

A tree with n nodes must contain ______ edges.

A)n
B)n - 1
C)n - 2
D)n / 2

Question 31

The adjacency matrix for an undirected graph is symmetrical.

Question 32

A connected undirected graph that has n vertices and more than n - 1 edges ______.

A)cannot contain a cycle
B)must contain at least one cycle
C)can contain at most two cycles
D)must contain at least two cycles

Question 33

A connected undirected graph that has n vertices and exactly n - 1 edges cannot contain a cycle.

Question 34

A connected undirected graph that has n vertices and exactly n - 1 edges ______.

A)cannot contain a cycle
B)must contain at least one cycle
C)can contain at most two cycles
D)must contain at least two cycles

Question 35

All complete graphs are connected.

Question 36

All paths begin and end at the same vertex.

Question 37

A ______ is an undirected connected graph without cycles.

A)tree
B)multigraph
C)digraph
D)connected component

Question 38

A simple cycle only passes through one vertex.

Question 39

A simple path may pass through the same vertex more than once.

Question 40

An Euler circuit exits if and only if each vertex touches ______.

A)two edges
B)three edges
C)an even number of edges
D)an odd number of edges

Question 41

What is a self edge?

Question 42

Why is backtracking necessary in Depth First Search?

Question 43

Does the complete graph with 6 vertices contain an Euler circuit? Explain.

Question 44

What is a planar graph?

Question 45

What is a spanning tree?

Question 46

What is a weighted graph?

Question 47

Define a complete graph.

Question 48

What are the two most common implementations of a graph?

Question 49

What is a minimum spanning tree?

Question 50

How is the cost of a spanning tree calculated?

Question 51

Is it possible for a spanning tree to be a complete graph?

Question 52

What is a simple cycle?

Question 53

What is the shortest path between two vertices in a weighted graph?

Question 54

Suppose we have a weighted graph with n vertices,and at least n edges.Explain is wrong with the following approach for finding the minimum spanning tree:
while(the number of edges in the graph >= n)
find the edge with the highest weight and delete it from the graph

Question 55

If we are given the adjacency matrix of a weighted (undirected)graph,how can we use it to determine the number of edges in the graph?

Question 56

Define a path between two vertices.

Question 57

What is a cycle?

Question 58

What is a simple path?

Question 59

What are two differences between a directed graph and an undirected graph?

Question 60

How is the depth-first search (DFS)strategy of graph traversal different from the breadth-first search (BFS)strategy?