Unit 5 - Graph Theory

What is a directed graph (digraph)?

• A graph with loops

• A graph with undirected edges

• A graph with directed edges

• A graph with no graph with no verticesvertices

The number of arcs directed into a vertex is called its:

• Out-degree

• In-degree

• Degree

• Path length

The number of arcs directed out of a vertex is its:

• Out-degree

• In-degree

• Degree

• Path weight

In a digraph, the total number of in-degrees equals:

• Total number of vertices

• Twice the number of arcs

• Total number of loops

• Total number of arcs

A self-loop contributes how much to a vertex's in-degree and out-degree?

• 1 to both

• 1 to in-degree only

• 1 to out-degree only

• 0

hich of the following is a simple digraph?

• One with loops and multiple arcs

• No multiple arcs or loops

• Only directed cycles

• One with undirected edges

A complete digraph on n vertices has how many arcs?

• n

• n(n - 1)

• n^2

• 2n

A symmetric digraph is defined by:

• All arcs have same direction

• u→v implies v→u

• Each vertex is isolated

• It contains loops

In a null digraph:

• No vertices exist

• Only one loop exists

• No arcs exist

• Each vertex has an arc

A digraph with arcs from every vertex to all others is:

• Tree

• Null digraph

• Complete digraph

• Eulerian