Networks

Question 1

Define

Network diagram

Answer 1

A representation of a group of objects called vertices that are connected together by lines. Network diagrams are also called graphs.

Question 2

Define

Vertex

Answer 2

A point (or dot) in a network diagram at which lines of pathways intersect or branch. Vertices are also called nodes.

Question 3

Define

Edge

Answer 3

The line that connects two vertices. Edges can cross each other without intersecting at a node.

Question 4

Define

Degree

(of a vertex)

Answer 4

The degree of a vertex is the number of edges that are connected to it. The degree of a vertex is either even or odd.

Question 5

Define

Loop

(in a network)

Answer 5

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

Question 6

Define

Directed edge

Answer 6

Also called an arc, it has an arrow and travel is only
possible in the direction of the arrow.

Question 7

Define

Walk

Answer 7

a connected sequence of the edges showing a route between vertices and edges.

Question 8

Define

Trail

Answer 8

A walk with no repeated edges.

Question 9

Define

Path

Answer 9

A walk with no repeated vertices or repeated edges. Open paths start and finish at different vertices while closed paths start and finish at the same vertex.

Question 10

Define

Circuit

Answer 10

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 11

Define

Cycle

Answer 11

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 12

Define

Hamiltonian path

Answer 12

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

Question 13

Define

Hamiltonian cycle

Answer 13

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

Question 14

Define

Eulerian trail

Answer 14

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 15

Define

Eulerian circuit

Answer 15

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 16

Define

Tree

Answer 16

A connected graph that contains no cycles, multiple edges or loops.

Question 17

Define

Spanning tree

Answer 17

A tree which connects all the vertices in
the graph

Question 18

Define

Minimum spanning tree

Answer 18

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

Question 19

Prim’s algorithm

Answer 19

1. Choose a starting vertex (any will do).
2. Inspect the edges starting from the starting vertex and choose the one with the lowest weight. (If there are two edges that have the same weight, it does not matter which one you choose).
3. Inspect all of the edges starting from both of the vertices you have in the tree so far. Choose the edge with the lowest weight, ignoring edges that would connect the tree back to itself.
4. Keep repeating step 3 until all of the vertices are connected.

Question 20

Kruskal’s algorithm

Answer 20

1. List all the edges in ascending order of length.
2. Choose the shortest edge. If two edges are the same length, arbitarily choose one.
3. Choose the next shortest edge. It does not matter if this edge is connected to the first edge or not.
4. Choose the next shortest edge which doesn’t create a cycle
5. Continue until all vertices are connected

Question 21

Dijkstra’s Algorithm

Answer 21

Choose a starting node and calculate the shortest distance to the next nodes. These nodes are then marked as “visited” and their shortest distances is used in calculations for later nodes.