Modelling with Graphs and Networks

Question 1

Why does the sum of orders in a graph have to be even?

Answer 1

Because sum of orders = arc endings and each arc has 2 endings
so arc ending = 2 x no. of arcs which is even

Question 2

What is a simple graph?

Answer 2

One without loops or direction

Question 3

What is the order of node with 1 loop?

Answer 3

2

Question 4

What is a complete graph?

Answer 4

One where every vertex is connected to every other vertex by an arc

Question 5

What is the total sum of arcs in a complete graph?

Answer 5

n(n-1)/2

Question 6

What is a digraph?

Answer 6

Has at least one edge with a direction associated with it

Question 7

What is a bipartite graph?

Answer 7

One where there’s 2 distinct sets of nodes

Question 8

Trail vs path vs closed cycle

Answer 8

Trail - no edge is repeated
Path - no vertex is repeated
Closed cycle - start and end with same vertex

Question 9

What’s a tree?

Answer 9

Connected graph with no cycles

Question 10

Spanning tree?

Answer 10

A subgraph which has all the vertices and is also a tree