Question 1

An undirected graph is a graph where the pairings representing the edges are _____________.
A) Unordered
B) Ordered
C) Sorted
D) None of the above

Accepted Answer

In an undirected graph, the edges are defined by unordered pairs of vertices, meaning the order of the vertices does not matter.

Question 2

Two vertices in a graph are ___________ if there is an edge connecting them.
A) Connected
B) Adjacent
C) Ordered
D) None of the above

Accepted Answer

Two vertices in a graph are considered adjacent if there is a direct edge connecting them. This term specifically refers to the direct connection between vertices in a graph.

Question 3

An undirected graph is considered complete if it has the maximum number of edges connecting vertices.
A) Connected
B) Adjacent
C) Complete
D) Full

Accepted Answer

A complete graph is one in which every pair of distinct vertices is connected by a unique edge, meaning it contains the maximum number of edges possible without forming loops or multiple edges between the same pair of vertices.

Question 4

A _________ is a sequence of edges that connects two vertices in a graph.
A) Connection
B) Path
C) Set
D) Cycle

Accepted Answer

A path in graph theory is a sequence of edges that connects two vertices without repeating any vertices.

Question 5

A ________ is a path in which the first and last vertices are the same and none of the edges are repeated.
A) Connection
B) Path
C) Set
D) Cycle

Accepted Answer

A cycle in graph theory is defined as a path that starts and ends at the same vertex without repeating any edges, which matches the description given.

Question 6

An undirected tree is a connected, acyclic, undirected graph with one element designated as the _______.
A) Starting point
B) Root
C) Leaf
D) Cycle

Accepted Answer

In an undirected tree, one element can be designated as the root, which serves as a reference point for various operations, such as traversal. Trees do not inherently have a root, but one can be designated for purposes of discussion or specific algorithms.

Question 7

A directed graph, sometimes referred as a digraph, is a graph where the edges are _________ pairs of vertices.
A) Unordered
B) Ordered
C) Sorted
D) None of the above

Accepted Answer

In a directed graph (digraph), the edges are ordered pairs of vertices, indicating a direction from one vertex to another.

Question 8

A path in a directed graph is a sequence of directed edges that connects two _________ in a graph.
A) Vertices
B) Trees
C) Edges
D) None of the above

Accepted Answer

A path in a directed graph is defined by a sequence of directed edges that connects two vertices.

Question 9

A ________, or a weighted graph, is a graph with weights or costs associated with each edge.
A) Tree
B) Graph
C) Network
D) None of the above

Accepted Answer

A network, or a weighted graph, is defined as a graph where each edge has an associated weight or cost, distinguishing it from a simple graph where edges are unweighted.

Question 10

The only difference between a depth-first traversal of a graph and a breadth-first traversal is the use of a _________ instead of a queue to manage the traversal.
A) Stack
B) Tree
C) List
D) Heap

Accepted Answer

In a depth-first traversal, a stack is used to keep track of the vertices that need to be explored, whereas a breadth-first traversal uses a queue to manage the vertices in the order they should be explored.

Question 11

A graph is connected if and only if the number of vertices in the __________ traversal is the same as the number of vertices in the graph regardless of the starting vertex.
A) Depth-first
B) Breadth-first
C) Level-order
D) None of the above

Accepted Answer

The answer of A graph is connected if and only...

Question 12

A __________ tree is a tree that includes all of the vertices of a graph and some, but possibly not all, of the edges.
A) Directed
B) Undirected
C) Spanning
D) None of the above

Accepted Answer

A spanning tree is defined as a subset of Graph G, which has all the vertices covered with the minimum possible number of edges. Hence, it includes all vertices of the graph and some (or possibly all) of the edges, making it a minimal connected subgraph.

Question 13

A minimum spanning tree is a spanning tree where the sum of the weights of the edges is ____________ to the sum of the weights for any other spanning tree for the same graph.
A) Less than or equal
B) Greater than or equal
C) Equal
D) None of the above

Accepted Answer

A minimum spanning tree is defined as a spanning tree with the smallest possible total edge weight compared to all other spanning trees of the same graph.

Question 14

An ______ graph is a graph where the pairings representing the edges are unordered.

Accepted Answer

The answer of An ______ graph is a graph where...

Question 15

Two vertices in a graph are adjacent if there is an edge ______ them.

Accepted Answer

The answer of Two vertices in a graph are adjacent...

Question 16

An undirected graph is considered complete if it has the ______ number of edges connecting vertices.

Accepted Answer

The answer of An undirected graph is considered complete if...

Question 17

A ______ is a sequence of edges that connects two vertices in a graph.

Accepted Answer

The answer of A ______ is a sequence of edges...

Question 18

A cycle is a path in which the first and last vertices are ______ and none of the edges are repeated.

Accepted Answer

The answer of A cycle is a path in which...

Question 19

An undirected tree is a connected, ______, undirected graph with one element designated as the root.

Accepted Answer

The answer of An undirected tree is a connected, ______,...

Question 20

A ______, sometimes referred as a digraph, is a graph where the edges are ordered pairs of vertices.

Accepted Answer

The answer of A ______, sometimes referred as a digraph,...

Quiz 13: Sets and Maps

An undirected graph is a graph where the pairings representing the edges are _____________.

Two vertices in a graph are ___________ if there is an edge connecting them.

An undirected graph is considered complete if it has the maximum number of edges connecting vertices.

A _________ is a sequence of edges that connects two vertices in a graph.

A ________ is a path in which the first and last vertices are the same and none of the edges are repeated.

An undirected tree is a connected, acyclic, undirected graph with one element designated as the _______.

A directed graph, sometimes referred as a digraph, is a graph where the edges are _________ pairs of vertices.

A path in a directed graph is a sequence of directed edges that connects two _________ in a graph.

A ________, or a weighted graph, is a graph with weights or costs associated with each edge.

The only difference between a depth-first traversal of a graph and a breadth-first traversal is the use of a _________ instead of a queue to manage the traversal.

A graph is connected if and only if the number of vertices in the __________ traversal is the same as the number of vertices in the graph regardless of the starting vertex.

A __________ tree is a tree that includes all of the vertices of a graph and some, but possibly not all, of the edges.

A minimum spanning tree is a spanning tree where the sum of the weights of the edges is ____________ to the sum of the weights for any other spanning tree for the same graph.