Definitions

Question 1

Graph

Answer 1

points (vertices or nodes) connected by lines (edges or arcs)

Question 2

Subgraph

Answer 2

a graph each of whose vertices and edges belongs to another graph

Question 3

Network =

Answer 3

weighted graph = graph with a number/weight associated with each edge

Question 4

The degree or valency of a vertex is

Answer 4

the number of edges incident to it

Question 5

A path is

Answer 5

a finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex of the first edge

Question 6

Two vertices are connected if

Answer 6

there is a path between them

Question 7

A graph is connected if

Answer 7

all its vertices are connected

Question 8

A cycle (circuit) is a

Answer 8

closed path i.e. the end vertex of the last edge is the start vertex of the first edge

Question 9

Digraph =

Answer 9

edges of a graph have an associated direction

Question 10

A tree is

Answer 10

a connected graph with no cycles (MS)

Question 11

a spanning tree of a graph is

Answer 11

a subgraph which includes all the vertices of the graph and is also a tree - all nodes are connected (MS)

Question 12

A minimum spanning tree is

Answer 12

a spanning tree such that the total length of its arcs is as small as possible = minimum connector =
a tree that contains all vertices and wight of tree is as small as possible (MS)

Question 13

A bipartite graph

Answer 13

consists of two sets of vertices in X to vertices in Y, not vertices within a set

Question 14

A matching is

Answer 14

a one to one pairing of elements between two sets

Question 15

Decision variables

Answer 15

number of each of the things can be varied

Question 16

Constrains

Answer 16

things preventing you from using an infinite number of each variable

Question 17

Activity on arc network

Answer 17

activities represented by arcs and the completion of these activities, known as events, are shown as nodes.

Question 18

The early event time is

Answer 18

the earliest time of arrival at the event allowing for the completion of all precceding activities

Question 19

The late event time is

Answer 19

the latest time that the event can be left without extending the time needed for the project

Question 20

Critical activity =

Answer 20

an activity which if its duration is increased or its delayed will increase the duration or delay the whole project

Question 21

Handshaking lemma

Answer 21

sum of degrees = 2*number of edges as counting each end of each end

Question 22

Walk =

Answer 22

path in which you are permitted to return to vertices more than once

Question 23

Loop =

Answer 23

edge that starts and finishes at the same vertex (counts as two on a matrix)

Question 24

Simple graph =

Answer 24

no loops, no more than one edge connecting any pair of vertices

Question 25

Isomorphic graphs

Answer 25

show same information but are drawn differently - same number of edges and vertices - lines can be curved or straight

Question 26

Distance matrices

Answer 26

records weight on the edges
useful to input networks onto a computer

can use Prims but not Kruskals

Question 27

Planar graph =

Answer 27

no edges crossing each other

Question 28

Hamiltonian cycle =

Answer 28

cycle visiting every edge of graph

Question 29

Eulerian cycle =

Answer 29

cycle travels along every edge of the graph

Question 30

adjacency matrix

Answer 30

records the number of direct links between vertices

Question 31

A graph is traversable if it possible to

Answer 31

traverse (travel along) every arc just once without taking your pen off the paper - all valencies are even

Question 32

A graph is semi-traversable if it

Answer 32

has two odd valencies - the start and finish point will be those two vertices

Question 33

A graph is not traversable if

Answer 33

it has > 2 odd valencies