FINAL - Graph Concepts

Question 1

Connected graph (undirected)

Answer 1

There is a path between every pair of vertices

Question 2

Path

Answer 2

A sequence of distinct edges that joins a sequence of vertices

Question 3

Simple path

Answer 3

Implies no repeated vertices (and that the term “path” might contain repeated vertices)

Question 4

Connected component

Answer 4

A maximal connected subgraph of G

Question 5

Weakly connected graph (directed)

Answer 5

Replacing all its directed edges with undirected edges produces a connected graph

Question 6

Connected graph (directed)

Answer 6

G contains a directed path from u to v OR from v to u for every pair of vertices u, v

Question 7

Strongly connected graph (directed)

Answer 7

G contains a directed path from u to v AND from v to u for every pair of vertices u, v

Question 8

Complete graph

Answer 8

Every pair of distinct vertices is connected by a unique edge (edges to/from for a digraph)

Question 9

Spanning tree

Answer 9

A subgraph that is a tree and includes all the vertices in G using a minimum number of edges

Question 10

Tree edge

Answer 10

GRAY->WHITE, from parent to child (discovery edge), forms a spanning tree/forest

Question 11

Back edge

Answer 11

GRAY->GRAY, loops back to an ancestor

Question 12

Forward edge

Answer 12

GRAY->BLACK, from ancestor to descendant

Question 13

Cross edge

Answer 13

GRAY->BLACK, between two unrelated nodes

Question 14

If G is undirected, a DFS produces only…

Answer 14

tree edges and back edges

Question 15

For a directed, connected graph with 2 nodes, how many trees will a DFS produce?

Answer 15

It depends on which node is chosen to be the root first!!!!

Question 16

How can I determine if an undirected graph G is connected?

Answer 16

Run DFS. If you end up with 1 tree, it is connected!

Question 17

How do you know if your graph has cycles?

Answer 17

Run DFS. If you have any back edges, you have cycles (for either digraph or undirected)

Question 18

Strongly connected component

Answer 18

A maximal subset of nodes that is strongly connected

Question 19

Tree

Answer 19

A graph in which any two vertices are connected by exactly one path

Question 20

Minimum spanning tree

Answer 20

A spanning tree whose sum of edge weights is as small as possible