Edexcel IAL - Decision Mathematics 1- Glossary for D1  - New syllabus

1. Algorithms

In a list containing N items, the middle item has position:

• If N is odd: \(\mathrm{ \mathrm{\frac{1}{2}(N + 1)} }\)
• If N is even: \(\mathrm{\mathrm{ \frac{1}{2}N }}\)

Examples:

• \(\mathrm{ N = 9 }\) → middle item is the 5th
• \(\mathrm{ N = 6 }\) → middle item is the 4th

2. Algorithms on Graphs

A graph \(\mathrm{ G }\) consists of vertices (nodes) connected by edges (arcs).

A subgraph of \(\mathrm{ G }\) is formed using some of the vertices and edges of \(\mathrm{ G }\).

If each edge has a numerical value called a weight, the graph is called a weighted graph or network.

The degree (valency) of a vertex is the number of edges incident to it. A vertex is odd or even depending on its degree.

A path is a sequence of edges where no vertex is repeated.

A cycle (circuit) is a closed path.

A graph is connected if there is a path between every pair of vertices.

If edges have direction, the graph is called a digraph.

A tree is a connected graph with no cycles.

A spanning tree contains all vertices of the graph and has no cycles.

A minimum spanning tree (MST) has the smallest possible total edge weight.

A complete graph has every vertex connected to every other vertex.

The travelling salesman problem involves finding the shortest route that visits every vertex.

Triangular inequality: \(\mathrm{ \mathrm{AB \le AC + CB }}\)

A walk is a sequence of edges where vertices may repeat.

A tour is a walk that visits every vertex and returns to its starting point.

3. Critical Path Analysis

The total float \(\mathrm{ F(i, j) }\) of an activity \(\mathrm{ (i, j) }\) is:

\(\mathrm{\mathrm{ F(i, j) = l_j – e_i – \text{duration}(i, j)} }\)

Where:

• \(\mathrm{ e_i }\): earliest time of event \(\mathrm{ i }\)
• \(\mathrm{ l_j }\): latest time of event \(\mathrm{ j }\)