# D1 maths glossary

Terms you will need to learn for the exam.

HideShow resource information

## Graphs

Graph

consists of vertices connected by edges

Subgraph

part of a graph

Complete graph

a graph that has every vertex directly connected to every other vertex

Bipartite graph

a graph that has of two sets of vertices, and the edges only join vertices in one set to vertices in the other set

Network

a graph with a number on each edge.

1 of 4

## Matching

Matching

the pairing of elements in one set with elements in another set

Maximum matching

a matching with the largest possible number of elements in one set matched with elements in the other set

Complete matching

all the elements in one set are matched with elements in the other set

Alternating path

a path that starts from an unmatched vertex in one set, alternately uses edges not in and in the matching, and ends at an unmatched vertex in the other set

2 of 4

## Trees

Tree

a connected graph with no cycles

Spanning tree

a subgraph which is a tree and includes all the vertices

Minimum spanning tree

a spanning tree with the minimum total weight

3 of 4

## Paths

Path

a joined-up sequence of edges where no vertex appears more than once

Walk

a joined-up sequence of edges

Cycle

a closed path

Loop

an edge that starts and finishes at the same vertex

4 of 4