Deck 20: Graph Algorithms

Question 1

A graph G is a pair, G = (V, E), where V is a finite nonempty set called the set of ____ of G, and the elements of E are the pairs of elements of V.

A) nodes
B) branches
C) vertices
D) edges

Answer 1

C

Question 2

A binary tree has no cycles.

Answer 2

True

Question 3

Y is a(n) ____ of X if every element of Y is also an element of X.

A) derivative
B) subset
C) inheritee
D) shallow copy

Answer 3

B

Question 4

Graph theory started in 1736 with the ____ problem.

A) Königsberg bridge
B) Tower of Hanoi
C) Westminster
D) League of Augsburg

Question 5

The depth first traversal is similar to the postorder traversal of a binary tree.

Question 6

An edge incident on a single vertex is called a(n) ____.

A) block
B) cycle
C) component
D) loop

Question 7

A simple path is a path in which all vertices, except possibly the first and last vertices, are distinct.

Question 8

The ____ of sets A and B is the set of all elements that are in A or in B.

A) intersection
B) union
C) graph
D) reunion

Question 9

The implementation of a breadth first graph traversal uses a stack.

Question 10

The ____ of sets A and B is the set of all elements that are in A and B.

A) intersection
B) union
C) graph
D) reunion

Question 11

We can always traverse an entire graph from a single vertex.

Question 12

It is possible to design Prim's algorithm so that it is of the order O(n²).

Question 13

A graph H is called a(n) ____ of G if V(H) is a subset of V(G) and E(H) is a subset of E(G); that is, every vertex of H is a vertex of G, and every edge in H is an edge in G.

A) matrix
B) intersection
C) subgraph
D) union

Question 14

If the elements of E(G) are ordered pairs, G is called a(n) ____ graph.

A) undirected
B) directed
C) weighted
D) spanning

Question 15

In a directed graph, the pairs (u,v) and (v,u) represent the same edge.

Question 16

Linked lists cannot be used to implement an adjacency list.

Question 17

The two most common graph traversal algorithms are depth first traversal and breadth first traversal.

Question 18

Let G be an undirected graph.Let u and v be two vertices in G.Then u and v are called ____ if there is an edge from one to the other.

A) adjacent
B) weighted
C) connected
D) shortest path

Question 19

A graph might have cycles; therefore, we might not be able to traverse the entire graph from a single vertex.

Question 20

In a(n) ____ graph, the edges are drawn using arrows.

A) pointed
B) vector
C) directed
D) undirected

Question 21

A tree T is called a(n) ____ tree of graph G if T is a subgraph of G such that V(T) = V(G); that is, if all vertices of G are in T.

A) weighted
B) spanning
C) rooted
D) directed

Question 22

Two well-known algorithms, Prim's algorithm and ____'s algorithm, can be used to find a minimal spanning tree of a graph.

A) Euler
B) Dekart
C) Kruskal
D) Dijkstra

Question 23

Let e (u, v) be an edge in an undirected graph G.The edge e is said to be ____________________ on the vertices u and v.

Question 24

A graph is ____________________ if the number of vertices is zero.

Question 25

The edges connecting two vertices can be assigned a non-negative real number, called the ____ of the edge.

A) key
B) weight
C) width
D) height

Question 26

In a graph G, if the edges connecting two vertices have weights assigned to them, the graph is called a ____ graph.

A) source
B) weighted
C) spanning
D) minimal

Question 27

In a graph directed G, for each vertex, v, the vertices adjacent to v are called ____ successors.

A) immediate
B) adjacent
C) path
D) parallel

Question 28

If two edges, e₁ and e₂, are associated with the same pair of vertices {u, v}, then e₁ and e₂ are called ____ edges.

A) parallel
B) adjacent
C) connected
D) incident

Question 29

A graph is called a(n) ____ graph if it has no loops and no parallel edges.

A) simple
B) undirected
C) directed
D) weighted

Question 30

The shortest path algorithm is also called the ____ algorithm.

A) recursive
B) minimal
C) greedy
D) spanning

Question 31

The shortest path algorithm was developed by ____.

A) Euler
B) Kruskal
C) Prim
D) Dijkstra

Question 32

A(n) ____ tree T is a simple graph such that if u and v are two vertices in T, a unique path exists from u to v.

A) rooted
B) free
C) spanning
D) weighted

Question 33

Let G be an undirected graph.Let u and v be two vertices in G.A(n) ____________________ in G is a simple path in which the first and last vertices are the same.

Question 34

A maximal subset of connected vertices is called a ____ of G.

A) cycle
B) union
C) subset
D) component

Question 35

A minimal spanning tree of G is a spanning tree with the minimum ____.

A) path
B) cycle
C) weight
D) height

Question 36

A set Y is called a(n) ____________________ of X if every element of Y is also an element of X.

Question 37

In a(n) ____________________ graph, the tail of a pictorial directed edge is the origin, and the head is the destination.

Question 38

A tree in which a particular vertex is designated as a root is called a(n) ____ tree.

A) spanning
B) weighted
C) free
D) rooted

Question 39

The shortest path is the path with the smallest ____.

A) length
B) index
C) weight
D) key

Question 40

In Prim's algorithm for the minimal spanning tree, we start at a designated vertex, which we call the ____ vertex.

A) index
B) source
C) root
D) destination

Question 41

A(n) ____________________ ordering of the vertices of the accompanying graph is 0, 1, 4, 3, 2, 5, 7, 8, 6, 9.

Question 42

Let G be a weighted graph.Let u and v be two vertices in G, and let P be a path in G from u to v.The weight of the path P is the sum of the weights of all the ____________________ on the path P.

Question 43

____________________ algorithm builds the tree iteratively by adding edges until a minimal spanning tree is obtained.

Question 44

The ____________________ traversal of a graph is similar to traversing a binary tree level by level.

Question 45

The ____________________ algorithm gives the shortest distance for a given node to every other node in the graph.

Question 46

A(n) ____________________ ordering of the vertices of the accompanying graph is 0, 1, 3, 4, 2, 5, 7, 8, 6, 9.

Question 47

A tree T is called a(n) ____________________ of graph G if T is a subgraph of G such that V(T ) = V(G).

Question 48

The starting vertex of a shortest path in a graph is called the ____________________.