Graphs and Networks

Question 1

What is a graph

Answer 1

A diagram involving a set of points and interconnecting lines

Question 2

What is a vertex

Answer 2

A point on a graph

Question 3

What is an edge/arc

Answer 3

A line connecting two nodes/vertices

Question 4

What is an isomorphic graph

Answer 4

two or more graphs that show the same set of vertices and connections

Question 5

What is a connected graph

Answer 5

A graph where you can travel from any vertex to any other vertex via edges

Question 6

What is a multiple edge

Answer 6

two or more edges that connect the same pair of vertices

Question 7

What is a loop

Answer 7

a vertex connected to itself

Question 8

What is a simple graph

Answer 8

A graph with no loops or multiple edges

Question 9

What is a subgraph

Answer 9

A graph formed using only some of the vertices and edges of the original graph

Question 10

What is a sub-division

Answer 10

if you add an extra vertex along the edge of a graph

Question 11

what is a complete graph and its notation

Answer 11

a simple graph that has an edge connected it to all possible vertex pairs. Notation Kn where n = number of vertices.

Question 12

what is a planar graph

Answer 12

A graph where none of the edges cross over eachother

Question 13

what is the degree of a vertex

Answer 13

the number of edges coming out of a vertex

Question 14

what is the formula linking the total degrees and total edges

Answer 14

total number of degrees = 2 x total edges

Question 15

What is Euler’s formula

Answer 15

v + f - e = 2

Question 16

What is an adjacency matrix

Answer 16

a table showing the vertices and number of connections between them

Question 17

what is a compliment graph and its notation

Answer 17

a graph formed by drawing all the edges that don’t exist in the original graph and removing those that do (G’)

Question 18

What is a trail

Answer 18

a continuous journey around a graph with no repeated edges

Question 19

what is a closed trail

Answer 19

a trail that returns to its start vertex

Question 20

what is a path

Answer 20

a continuous journey around a graph with no repeated edges or vertices

Question 21

what is a cycle

Answer 21

a path that returns to its start vertex

Question 22

what is a tree

Answer 22

a connected graph with no cycles

Question 23

What is a hamiltonian cycle

Answer 23

a cycle that visits every vertex once

Question 24

what is an Eulerian Graph and how can you tell

Answer 24

A trail that starts and finishes in the same place, all it’s vertices have an even degree

Question 25

what is a semi eulerian graph and how can you tell

Answer 25

if a graph can only be drawn by starting and finishing at different points, if it has two odd degree vertices

Question 26

What is Kruskal’s algorithm

Answer 26

for MST
1. choose the arc with the least weight
2. choose the arc with the next least weight, avoiding a cycle
3. repeat step 2 until all nodes are connected

Question 27

what is Prim’s algorithm

Answer 27

for MST
1. choose any node
2. choose the arc with the least weight to join a connected node with an unconnected node
3. repeat step 2 until all nodes are connected

Question 28

what is the algorithm for the chinese postman/route inspection problem

Answer 28

1. identify all odd nodes
2. list all possible pairings
3. for each pairing find the shortest route between them and the total weight of these routes
4. choose the pairing with the smallest total and add it to the total weight of the network

Question 29

what is the algorithm for the travelling salesmen problem

Answer 29

Upper bound:
Nearest Neighbour algorithm
1. choose a starting node
2. from current position, choose arc with the least weight leading to an unvisited node
3. repeat step 2 until all nodes are visited
4. travel back to the starting node and find the total weight of this journey

Lower Bound:
1. remove a node and it’s connected arcs
2. construct an MST
3. add the weight of the MST to the weight of the lowest two arcs that have been removed

Question 30

what is the feasibility condition

Answer 30

states that the flow cannot exceed the capacity

Question 31

what is the conservative condition

Answer 31

states that for every node apart from the source and sink, total inflow=total outflow

Question 32

what is the theorem for flows and cuts

Answer 32

maximum flow = minimum cut