Networks

Question 1

What is a vertex?

Answer 1

A vertex is a point in a network diagram at which lines of pathways intersect/meet. Vertices are also called nodes.

Question 2

What is an edge?

Answer 2

An edge is a line that connects the vertices.

Question 3

What is meant by the degree of a vertex?

Answer 3

The degree of a vertex is the number of edges that are connected to it. The degree of the Broken Hill vertex is 3 because there are three edges attached to the vertex.

Question 4

Finish the sentence…

“The degree of a vertex is ? if it has an even number of edges attached to it.”

Answer 4

The degree of a vertex is even if it has an even number of edges attached to the vertex.

Question 5

Finish the sentence…

“The degree of a vertex is ? if it has an odd number of edges attached to it.”

Answer 5

The degree of a vertex is odd if it has an odd number of edges attached to it.

Question 6

What is a loop?

Answer 6

A loop starts and ends at the same vertex. It counts as one edge, but it contributes two to the degree of the vertex.

Question 7

What is a directed edge?

Answer 7

A directed edge has an arrow and travel is only possible in the direction of the arrow.

Question 8

What is an undirected edge?

Answer 8

An undirected edge has no arrow and travel is possible in both directions.

Question 9

What is a directed network?

Answer 9

In a directed network all the edges are directed - travel is only permissible in the direction of the arrows.

Question 10

What is an undirected network?

Answer 10

In an undirected network, all the edges are undirected and travel on an edge is possible in both directions.

Question 11

What is a simple network?

Answer 11

In a simple network, there are no edges or loops.

Question 12

What is a weighted edge?

Answer 12

A weighted edge is an edge of a network diagram that has a number assigned to it that implies some numerical value such as cost, distance or time.

Question 13

What is a walk?

Answer 13

A walk is a connected sequence of the edges showing a route between vertices where the edges and vertices may be visited multiple times.

Question 14

What is a trail?

Answer 14

A trail is a walk with no repeated edges.

Question 15

What is a path?

Answer 15

A path is a walk with no repeated vertices.

Question 16

What is a cycle?

Answer 16

A cycle is a walk with no repeated vertices that starts and ends at the same vertex. There are no repeated edges in a cycle as there are no repeated vertices. Cycles are closed paths.

Question 17

What is a circuit?

Answer 17

A circuit is a walk with no repeated edges that starts and ends at the same vertex. Circuits are also called closed trails. Alternatively, open trails start and finish at different vertices.

Question 18

What is a traversable graph?

Answer 18

A traversable graph has a trail that includes every edge. The trail A–B–C–A–C is one example.

Question 19

What is a non-traversable graph?

Answer 19

Not all graphs are traversable. It is impossible to find a trail in a non-traversable graph that includes every edge.

Question 20

What is a connected graph?

Answer 20

A connected graph has every vertex connected to every other vertex, either directly or indirectly via other vertices. That is, every vertex in the graph can be reached from every other vertex in the graph.

Question 21

Finish the sentence…

Two graphs are isomorphic if:

• ?
• ?

Answer 21

Two graphs are isomorphic if:

• they have the same numbers of edges and vertices
• corresponding vertices have the same degree and the edges connect to the same vertices.

Question 22

What are isomorphic graphs?

Answer 22

Different looking graphs can contain the same information.

Question 23

What is an eulerian trail?

Answer 23

A trail that uses every edge of a graph exactly once and starts and ends at different vertices. Eulerian trails exist if the graph has exactly two vertices with an odd degree.

Question 24

What is an eulerian circuit?

Answer 24

A circuit that uses every edge of a network graph exactly once, and starts and ends at the same vertex. Eulerian circuits exist if every vertex of the graph has an even degree.

Question 25

What is a hamiltonian path?

Answer 25

A path passes through every vertex of a graph once and only once.

Question 26

What is a hamiltonian cycle?

Answer 26

A Hamiltonian path that starts and finishes at the same vertex.

Question 27

What is a tree?

Answer 27

A tree is a connected graph that contains no cycles, multiple edges or loops. The diagram below shows two network graphs that are trees and one network graph that is not a tree.

Question 28

What is a spanning tree?

Answer 28

Every connected graph will have at least one subgraph that is a tree. If a subgraph is a tree, and if that tree connects all of the vertices in the graph, then it is called a spanning tree.

Question 29

What is the Königsberg Bridge problem?

Answer 29

The Königsberg Bridge problem asked whether the seven bridges of the old city of Königsberg could all be crossed only once during a single trip that starts and finishes at the same place.

Question 30

What is a planar network?

Answer 30

A planar network is one where no edges cross unless there is a vertex at the crossing point.

Question 31

What is meant by the ‘shortest path’?

Answer 31

A shortest path in a network diagram is a path between two vertices in a network where the sum of the weights of its edges are minimised.

Question 32

What is Dijkstra’s algorithm?

Answer 32

A labelling algorithm that can be used to find the shortest path in a network diagram.

Question 33

What is a minimum spanning tree?

Answer 33

A minimum spanning tree is a spanning tree of minimum length. It connects all the vertices together with the minimum total weighting for the edges.