Deck 16: Graphs

Question 1

Consider a digraph with the following vertices and edges: vertices: 1, 2, 3, 4
Edges: (1,2), (2,1), (3,4)
Which of the following statements are true?

A) The graph has a cycle
B) The graph is connected
C) The graph is acyclic
D) all of the above are true
E) neither a, b, nor c are true.

Answer 1

A
Explanation: This graph has a cycle, namely edge (1,2) and (2,1). It is not connected because there is no path between 1 and 4, for example.

Question 2

A(n) ___________________ is a two-dimensional array that can be used to represent a graph.

A) adjacency list
B) adjacency matrix
C) digraph list
D) graph node
E) none of the above

Answer 2

B
Explanation: An adjacency matrix is a two-dimensional array that can be used to represent a graph.

Question 3

A digraph is a __________________________ .

A) graph in which every cycle contains 2 edges.
B) graph in which every cycle contains 3 edges.
C) graph in which there are no cycles.
D) graph in which there are 2 cycles.
E) directed graph.

Answer 3

E
Explanation: A digraph is another name for a directed graph.

Question 4

A graph in which every edge is connected to every other edge is said to be ___________________ .

A) sparse
B) complete
C) full
D) balanced
E) connected

Question 5

In a(n) _____________________ graph, an edge from node labeled A to a node labeled B is the same as having an edge from B to A.

A) directed
B) undirected
C) sparse
D) tree-like
E) none of the above

Question 6

A graph is said to have a(n) ________________, if there exists a path where the first and last vertices are the same, and no edge is repeated.

A) connected component
B) algorithm
C) cycle
D) weight
E) complete component

Question 7

A graph is a special kind of tree.

Question 8

A(n) _______________________ is one implementation of a graph where the graph is implemented as a linked structure, and each node contains a structure that contains links to all other nodes.

A) adjacency list
B) adjacency matrix
C) digraph list
D) graph node
E) none of the above

Question 9

A graph with integer weights or costs associated with edges is sometimes called a(n) _________________.

A) acyclic graph
B) directed graph
C) network
D) adjacency matrix
E) none of the above

Question 10

A depth-first traversal of a graph uses which of the following data structures?

A) binary search tree
B) stack
C) queue
D) array
E) none of the above

Question 11

In graph terminology, the nodes are referred to as ____________________.

A) vertices
B) edges
C) parents
D) children
E) none of the above

Question 12

A spanning tree of a graph is a tree with that always has which of the following properties?

A) It includes some of the edges and some of the vertices of the graph.
B) It includes all of the edges and some of the vertices of the graph.
C) It includes some of the edges and all of the vertices of the graph.
D) It includes all of the edges and all of the vertices of the graph.
E) none of the above

Question 13

A digraph and an directed graph are the same thing.

Question 14

Which of the following describes vertices that are adjacent?

A) They are close to one another in the visual representation of the graph.
B) They are far apart in the visual representation of the graph.
C) There is no edge connecting them.
D) There is an edge connecting them.
E) None of the above describes adjacent vertices.

Question 15

In an undirected graph, an edge of the form (A, B) is the same as an edge of the form (B, A).

Question 16

A connected graph has which of the following properties?

A) For any pair of vertices, there is an edge between them.
B) Every vertex is adjacent to every other vertex.
C) No vertex is adjacent to every other vertex.
D) For any pair of vertices, there is a path between them.
E) There exists a vertex that is adjacent to every other vertex.

Question 17

A breadth-first traversal of a graph uses which of the following data structures?

A) binary search tree
B) stack
C) queue
D) array
E) none of the above

Question 18

A __________________ traversal can be used to determine if a graph is connected.

A) inorder
B) preorder
C) depth-first
D) breadth-first
E) none of the above

Question 19

A complete graph on n vertices has n(n-1)/2 edges.

Question 20

An undirected graph is connected if for every pair of vertices, there is an edge between them.

Question 21

Consider the following undirected graph.
vertices: 1, 2, 3, 4, 5
edges: (1,2),(3,4), (2,4), (2, 3), (3,5), (4,5)
Write out an adjacency matrix for this graph.

Question 22

Explain how a breadth-first traversal of a graph works.

Question 23

Can a tree ever have a cycle? Explain.

Question 24

What data structure is used to support a depth-first traversal of a graph?

Question 25

An adjacency matrix is one approach to implementing a graph that uses a two-dimensional array.

Question 26

Consider the following undirected graph.
vertices: 1, 2, 3, 4, 5
edges: (1,2),(3,4), (2,4), (2, 3)
Is the graph connected?

Question 27

Can an edge be part of more than one cycle in a graph? Explain.

Question 28

What is the maximum number of edges in a directed graph on n vertices? Explain how you arrived at your solution.

Question 29

What does it mean for a graph to be connected?

Question 30

A breadth-first traversal uses a stack as a supporting data structure.

Question 31

Write out all of the edges in a complete graph on 4 vertices.

Question 32

Is every tree a graph? Is every graph a tree? Explain.

Question 33

Consider the following undirected graph.
vertices: 1, 2, 3, 4, 5
edges: (1,2),(3,4), (2,4), (2, 3)
Is the graph acyclic?

Question 34

A spanning tree of a graph does not necessarily include all of the edges of the graph.

Question 35

A minimum spanning tree of a weighted graph is a spanning tree in which the sum of the weights of the edges is less than or equal to the sum of the weights for any other spanning tree for the same graph.

Question 36

A cycle is a path that starts and ends on the same vertex.

Question 37

What is a complete graph? How many edges are contained in a complete graph on n vertices?

Question 38

Consider the following undirected graph.
vertices: 1, 2, 3, 4, 5
edges: (1,2),(3,4), (2,4), (2, 3), (3,5), (4,5)
Give a spanning tree for this graph.

Question 39

What is the difference between a directed graph and an undirected graph?

Question 40

What is the difference between a spanning tree and a minimum spanning tree?