Definitions and Terminology

Question 1

Graph

Answer 1

A diagram that consists of vertices and edges

Question 2

Network

Answer 2

A graph where the edges have weights

Question 3

Connected graph

Answer 3

A graph where all pairs of vertices are connected

Question 4

Simple graph

Answer 4

A graph that does not contain loops or multiple arcs

Question 5

Directed graph

Answer 5

The edges in a directed graph have direction

Question 6

Completed graph Kn

Answer 6

Graph contains n vertices where each vertex joins each of the remaining vertices exactly once. Number of edges n(n-1)/2

Question 7

Trail

Answer 7

Sequences of edges where the end of edge is the start of the next edge.

Question 8

Path

Answer 8

A trail where no vertex can be visited more than once

Question 9

Cycle

Answer 9

A closed path where the first and last vertex are the same

Question 10

Hamiltonian cycle

Answer 10

Cycle that visits all the vertices. In a complete graph there are (n-1)!/2

Question 11

Spanning tree or tree

Answer 11

Connected all vertices of a graph. For a graph with n vertices the spanning tree will have n-1 edges.

Question 12

Minimum spanning tree

Answer 12

For a weighted graph, a spanning tree with minimum weight.

Question 13

Eulerian Graph

Answer 13

Closed trail (cycle) that uses all the edges of a graph. All vertices must have an even order.

Question 14

Semi-Eulerian

Answer 14

Non-closed trail that uses all the edges. The graph will have exactly two vertices with an odd order.