A-level Mathematics/MEI/D1/Graphs

Graphs in discrete mathematics are a little different to graphs in continuous mathematics. In continuous mathematics, graphs are drawn to visualise a mapping between two variables (for example y=x²). In discrete mathematics, graphs depict a relationship between objects, known as vertices or nodes, these objects are connected by edges. Edges can be undirected or directed, if they are directed then an arrow is used to indicated which way the edge can be traversed. The diagram produced by connecting vertices with edges is called a graph.

Pairs of vertices can be created from two sets using the following set comprehension (if you're unfamiliar with set comprehension the expression is saying, from two sets: X and Y, generate every permutation of pairs) . $X\times Y=\{(x,y)|x\in X,y\in Y\}$

Example:

$X=\{London,Cambridge,Birmingham\}$
$X\times X=\{(London,London),(London,Cambridge),(London,Birmingham),$
$(Cambridge,London),(Cambridge,Cambridge),(Cambridge,Birmingham),$ $(Birmingham,London),(Birmingham,Cambridge),(Birmingham,Birmingham)\}$

Glossary

Basic definitions

Graph: A diagram composed of objects, some of which are connected by edges. Interconnected objects are called vertices or nodes and the links that connect nodes are called edges.
Degree/Order of a vertex/node: The number of edges connected to that vertex/node.
Cycle: A closed path formed when the end of one edge is the start of the next and no vertex is repeated.
Directed edge: An edge with a direction associated with it, this is depicted by a arrow in the direction the edge can be traversed.
Loop: An edge with the same vertex at each end.
Digraph: Directed-Graph, a graph that has at least one edge with a direction associated with it

The following definitions are ordered by generality, walks are the most general and Hamilton cycles are the least general.

Walk: A sequence of edges where the end of one edge is the beginning of the next edge. If the last edge is joined to the first, the walk is closed, if it is left unjointed, the walk is open.
Trail: A walk where no edge is repeated.
Path: A trail in which no vertex is repeated.
Cycle: A graph where the end of the last edge is joined to the first edge.
Hamilton Cycle: A cycle that visits every vertex exactly once

Types of graphs

Connected Graph: A graph where there is a path between each pair of vertices
Simple Graph: A graph with no loops and no more than one edge between any pair of edges.
Complete Graph: A simple graph where every pair of vertices is connected by an edge.
Planar Graph: A graph which can be drawn without any pairs of edges crossing.
Biparatite Graph: A graph which is composed of two sets of vertices, each edge connects a vertex from one set, to a vertex from the other set.
Digraph: A graph containing a directed edge.
Tree: A simple connected graph containing no cycles.

Examples of graphs

These examples are those listed in the OCR MEI competences specification, and as such, it would be sensible to fully understand them prior to sitting the exam.

Königsberg bridges

It was said that it was not possible to cross the seven bridges in Königsberg without crossing any bridge twice. Euler studied this problem, translating it into graph theory and proved that any graph with odd vertices cannot be traversed.

The problem was translated into a graph by taking bridges as edges and representing land as nodes. This abstraction of irrelevant details allowed Euler to concentrate on the core properties of the problem and is a fundamental aspect of modelling any problem.

Euler reasoned that when entering a land mass (node) by a bridge (edge), one leaves the land mass by another bridge, hence the number of times one enters a node is the same as the number of times one leaves a node, therefore the number of bridges traversing land masses must be even (providing the node isn't the starting or ending node, in which case the number of times of entry is odd). From this result, it follows that each land mass (excluding the ones chosen for the start and finish) must have an even number of bridges (edges). All four of the land masses in the problem are touched by an odd number of bridges, and only 2 land masses at most can serve as the start/end of the walk, it follows that the bridges cannot be crossed just once in a walk.

In more a more formal tone:
Euler reasoned that when entering a non-terminal (not a start/end) node by an edge, one leaves the node by another edge, therefore the number of times one

A Eulerian walk is a walk which traverses all edges just once, the start and end nodes can be the same or different. If the start and end nodes are the same, then the walk is known as a Eulerian circuit. For a graph to have a Eulerian circuit there must be zero nodes of an odd degree, whereas Eulerian walks can have zero or two nodes of an odd degree. Any graph in which it is possible to trace every edge once, without lifting a pencil from a paper and return to the start is called Eulerian or traversable.

River crossing

Tower of cubes

There are four cubes with four different colours on their faces. The aim of the puzzle is to stack the cubes on top of each other into a 4x1x1 cuboid so that there are four different colours on each face of the cuboid. The cubes are painted as follows:

Cube 1	Cube 2	Cube 3	Cube 4
Blue opposite Green	B opp G	R opp B	Y opp R
Red opposite Red	G opp R	R opp Y	Y opp G
Yellow opposite Blue	B opp Y	G opp Y	B opp G

A graph is drawn where:

nodes represent colours
edges represent mappings between opposite sides of the cube. For example, Cube 3 has a mapping: R opp B, this would be represented by an edge from R to B with the label '3' indicating that mapping belongs to cube 3.

This graph is then split into 3 sub-graphs composed of edges labelled 1,2,3,4 and nodes of order 2. These can be produced by looking at the original graph and picking an edge that will be part of your sub-graph. Remove all other edges that are labelled with the same cube number, remove all other edges connected to

Sub-graphs formed from the graph above

Sub-graph 1.
Sub-graph 2.
Sub-graph 3.

Filing systems

External links

[1] - MathWorld graph classroom.
[2] - MathWorld graphs page.