D1

Question 1

SIMPLE

Answer 1

A graph is simple if it has no loops and at most one edge connecting any pair of vertices

Question 2

CONNECTED

Answer 2

Where all vertices are connected together directly or indirectly

Question 3

COMPLETE

Answer 3

Every vertex is connected to every other vertex.

Question 4

PLANAR

Answer 4

A graph that can be drawn so that none of the arcs cross.

Question 5

HAMILTONIAN CYCLE

Answer 5

A cycle that visits every vertex of a graph exactly once and returns to the start vertex.

Question 6

How many Hamiltonian cycles does a complete graph with n vertices have? Give your answer in terms of n

Answer 6

(n-1)! / 2

Question 7

EULERIAN TRAILS

Answer 7

Covers every edge of the graph exactly once and finishes at the start vertex. Has all even vertices.

Question 8

SEMI-EULERIAN

Answer 8

has only 2 odd orders and the rest are even.

Question 9

TRAVERSABLE

Answer 9

A graph that can be drawn without taking the pen off the paper and without repeating any edges.

Question 10

What does KRUSKAL’s algorithm do?

Answer 10

Minimum spanning tree

Question 11

What does PRIM’s algorithm do?

Answer 11

Minimum spanning tree

Question 12

What does DIJKSTRA’s algorithm do?

Answer 12

Shortest path in a network

Question 13

CHINESE POSTMAN?

Answer 13

Shortest possible path via all the arcs and return to start. (May have to repeat some edges).

Question 14

ISOMORPHIC

Answer 14

Graphs with the same vertices