Decision

Question 1

Vertex / Node

Answer 1

Point on a graph

Question 2

Edge / arc

Answer 2

Like segment joining nodes

Question 3

Weight

Answer 3

Number associated with the arc

Question 4

What’s a graph

Answer 4

Certified connected by edges

Question 5

Subgraph

Answer 5

A graph where all nodes and arcs belong to the main graph but just part of it

Question 6

Degree / Valency / Order

Answer 6

Number of arcs on a node

Question 7

Walk

Answer 7

A route through a graph along edges from one vertex to the next

Question 8

Path

Answer 8

A walk where no nodes visited more than once

Question 9

Trail

Answer 9

Walk where no edge is visited more than once

Question 10

Cycle

Answer 10

Walk where start and end node are same, no node visited more than once

Question 11

Hamiltonian cycle

Answer 11

Includes every node

Question 12

Connected

Answer 12

Graph if all vertices are connected

Question 13

Simple graph

Answer 13

No loops and only one edge connecting any pair of nodes

Question 14

Digraph

Answer 14

When arcs have direction

Question 15

Sum of degrees of nodes equal to

Answer 15

2 x no. edges

Question 16

Euler’s handshaking lemma

Answer 16

Even no of odd nodes

Question 17

Tree

Answer 17

Connected graph with no cycles

Question 18

Spanning tree

Answer 18

Subgraph which includes all vertices

Question 19

Complete graph

Answer 19

Every node is directly connected to every node by a single edge
Kn

Question 20

Isomorphic graphs

Answer 20

Show same info but can be drawn differently

Question 21

Adjacency matrix

Answer 21

Describes the number of arcs joining corresponding nodes

Question 22

Distance matrix

Answer 22

The entries represent the weight of each arc not number of arcs

Question 23

Planar graph

Answer 23

Can be drawn in a plane such that no two edges meet except at a vertex

Question 24

Kruskal’s Algorithm finds:

Answer 24

Minimum spanning tree, shortest way of linking all nodes

Question 25

Minimum spanning tree is

Answer 25

Total length of arcs is as small as possible

Question 26

Hot to do Kruskal’s

Answer 26

1) sort arcs into ascending order if weight 2) select arc of least arc to start tree 3) consider next lowest, if cycle would form then reject, if not add to tree 4) repeat till all connected, doesn’t have to be connected during

Question 27

Prim’s Algorithm finds

Answer 27

Minimum spanning tree

Question 28

How to do Prim’s Algorithm

Answer 28

1) choose any vertex to start the tree 2) select arc of least weight that joins any vertex already in the tree to a new one 3) repeat

Question 29

Prim’s Algorithm with a Matrix how

Answer 29

1) choose any vertex to start 2) delete the ROW in matrix for that node 3) number the COLUMN in the matrix for the chosen vertex 4) put a ring around the lowest, I deleted entry in any of the numbered columns 5) ringed entry becomes next arc 6) repeat until all deleted

Question 30

Dijkstra’s Algorithm finds

Answer 30

Shortest path from S to T

Question 31

How to do Dijkstra’s Algorithm

Answer 31

1) label start vertex S, with the final label 0 | 2) y