# D1 terms

these are the terms for the first three chapters of edexcels D1

HideShow resource information
• Created by: dillin
• Created on: 30-10-11 17:35

## Complete graph

A graph in which each of the n vertices is connected to

every other vertex.

1 of 29

## Cycle

A closed path, i.e. the end vertex of the last edge is the start

vertex of the first edge. (Same as a circuit.)

2 of 29

## Arc

A curved line connecting points (nodes or vertices) on a

graph

3 of 29

## Bipartite graph

A graph consisting of two sets of vertices X and Y. The

edges only join vertices in X to vertices in Y, not vertices

within a set. (If there are r vertices in X and s vertices in Y

then this graph is Kr ,s.)

4 of 29

## Degree

The degree or valency of a vertex is the number of edges

incident to it. A vertex is odd (even) if it has odd (even)

degree

5 of 29

## Dijkstra’s algorithm

An algorithm that finds the shortest paths from a single

source vertex to all other vertices in a directed graph.

6 of 29

## Edge

A line on a graph connecting two nodes

7 of 29

## Even vertex (or node)

A vertex is even if it has even degree.

8 of 29

## End node

The last point in a network

9 of 29

## Graph

A graph G consists of points (vertices or nodes) which are

connected by lines (edges or arcs).

10 of 29

## Kruskal’s (greedy) algorithm

An algorithm used to find the minimum spanning tree of a

network. Uses a different method to Prim’s algorithm.

11 of 29

## Minimum connector

Same as a minimum spanning tree

12 of 29

## Minimum spanning tree (MST)

A spanning tree such that the total length of its arcs is as

small as possible. (MST is sometimes called a minimum

connector.

13 of 29

## Network

A graph where each edge has a ‘weight’. (Also known as a

weighted graph)

14 of 29

## Node

A point on a graph (same as a vertex)

15 of 29

## Odd vertex (or node)

A vertex is odd if it has odd degree

16 of 29

## Path

A finite sequence of edges, such that the end vertex of one

edge in the sequence is the start vertex of the next, and in

which no vertex appears more then once

17 of 29

## Prim’s algorithm

An algorithm used to find the minimum spanning tree of a

network. Uses a different method to Kruskal’s algorithm.

18 of 29

## Spanning tree

A spanning tree of a graph G is a subgraph which includes

all the vertices of G and is also a tree.

19 of 29

## Subgraph

A subgraph of G is a graph, each of whose vertices belongs

to G and each of whose edges belongs to G.

20 of 29

## Tree

A connected graph with no cycles.

21 of 29

Same as degree

22 of 29

## Vertex

A point on a graph (also called a node).

23 of 29

## Weigh

The number associated with each edge on a graph

24 of 29

## Weighted graph

A graph where each edge has a ‘weight’. (Also known as a

network).

25 of 29

## Bubble sort

A simple sorting procedure that begins by ordering the first

and second items, then the second and third, and so on,

until the end of the set is reached. The process is repeated

until all items are correctly ordered

26 of 29

## Bin packing

Refers to problems that involve the packing of objects into

well defined regions called bins, so that they do not

overlap. The main purpose is to make efficient use of the

available space

27 of 29

## Binary search

A technique for locating a particular value in a sorted list

by finding the median value and comparing it to the target

value

28 of 29

## Connected

Two vertices are connected if there is a path between them.

A graph is connected if all its vertices are connected.

29 of 29