Deck 20: Graphs

Question 1

Provide a brief description of the Königsberg bridge problem. Who answered the question posed in the problem? What was the answer?

Answer 1

The Königsberg bridge problem is as follows: starting at one land area, is it possible to walk across all the bridges exactly once and return to the starting land area? Euler represented the Königsberg bridge problem as a graph and answered the question in the negative.

Question 2

For a graph G, what does it mean to say that H is a subgraph of G?

Answer 2

A graph H is called a subgraph of graph G if V(H) $\subseteq$ V(G) and E(H) $\subseteq$ E(G). In other words, every vertex of H is a vertex of G, and every edge in H is an edge in G.

Question 3

What does it mean to say that a graph G is connected? Strongly connected?

Answer 3

G is called connected if there is a path from any vertex to any other vertex. G is called strongly connected if any two vertices in G are connected.

Question 4

The adjacency matrix representation discussed in this chapter is a two-dimensional array that stores any nonnegative integer in each slot in the array.

Question 5

List three common operations on graphs.

Question 6

The ____________________ traversal algorithm for graphs is similar to the preorder traversal of a binary tree.

Question 7

Who developed the shortest path (or greedy) algorithm?

Question 8

A graph G must be ____________________ to determine a spanning tree for G.

Question 9

Define a minimal spanning tree of graph G.

Question 10

What does these terms refer to:

- $\gg$ Adjacency list:

Question 11

What does these terms refer to:

- $\gg$ Adjacency matrix:

Question 12

What does these terms refer to:

- $\gg$ Adjacent:

Question 13

What does these terms refer to:

- $\gg$ Adjacent from:

Question 14

What does these terms refer to:

- $\gg$ Adjacent to:

Question 15

What does these terms refer to:

- $\gg$ Breadth first traversal:

Question 16

What does these terms refer to:

- $\gg$ Component:

Question 17

What does these terms refer to:

- $\gg$ Connected:

Question 18

What does these terms refer to:

- $\gg$ Cycle:

Question 19

What does these terms refer to:

- $\gg$ Depth first traversal:

Question 20

What does these terms refer to:

- $\gg$ Destination:

Question 21

What does these terms refer to:

- $\gg$ Digraph:

Question 22

What does these terms refer to:

- $\gg$ Directed graph:

Question 23

What does these terms refer to:

- $\gg$ Edges:

Question 24

What does these terms refer to:

- $\gg$ (Free) tree:

Question 25

What does these terms refer to:

- $\gg$ Graph:

Question 26

What does these terms refer to:

- $\gg$ Greedy algorithm:

Question 27

What does these terms refer to:

- $\gg$ Immediate successors:

Question 28

What does these terms refer to:

- $\gg$ Incident:

Question 29

What does these terms refer to:

- $\gg$ Intersection:

Question 30

What does these terms refer to:

- $\gg$ Loop:

Question 31

What does these terms refer to:

- $\gg$ Minimal spanning tree:

Question 32

What does these terms refer to:

- $\gg$ Origin:

Question 33

What does these terms refer to:

- $\gg$ Parallel edges:

Question 34

What does these terms refer to:

- $\gg$ Path:

Question 35

What does these terms refer to:

- $\gg$ Rooted tree:

Question 36

What does these terms refer to:

- $\gg$ Shortest path:

Question 37

What does these terms refer to:

- $\gg$ Shortest path algorithm:

Question 38

What does these terms refer to:

- $\gg$ Simple graph:

Question 39

What does these terms refer to:

- $\gg$ Simple path:

Question 40

What does these terms refer to:

- $\gg$ Source:

Question 41

What does these terms refer to:

- $\gg$ Spanning tree:

Question 42

What does these terms refer to:

- $\gg$ Strongly connected:

Question 43

What does these terms refer to:

- $\gg$ Subgraph:

Question 44

What does these terms refer to:

- $\gg$ Subset:

Question 45

What does these terms refer to:

- $\gg$ Undirected graph:

Question 46

What does these terms refer to:

- $\gg$ Union:

Question 47

What does these terms refer to:

- $\gg$ Vertices:

Question 48

What does these terms refer to:

- $\gg$ Weight:

Question 49

What does these terms refer to:

- $\gg$ Weight of the edge:

Question 50

What does these terms refer to:

- $\gg$ Weight of the path:

Question 51

What does these terms refer to:

- $\gg$ Weight of tree T:

Question 52

What does these terms refer to:

- $\gg$ Weighted graph:

Question 53

What does these terms refer to:

- $\gg$ Weighted tree: