M91199119.fastmail.fm

A graph consists of a set of objects called Description
vertices and a list of pairs of vertices, callededges.
tures, with vertex A represented by a dot The edge joining A to A is called a loop, labelled A and each edge AB represented and the graph is called a loop multigraph.
by a curve joining A and B.
A general graph is one with possible loops data or relationships, and they make it easyto recognise properties which might other-wise not be noticed.
Problems represented by
edges is useful when graphs have to be ma- Many problems require vertices to be con- nipulated by computer. It is also a useful nected by a “path” of successive edges. We starting point for precise definitions of graph shall define paths (and related concepts) next lecture, but the following examples il-lustrate the idea and show how often it Examples of graphs
Description
graph pictures when searching for paths.
1. Gray codes
The binary strings of length n are taken as the vertices, with an edge joining any two tween each pair of vertices, and no vertex vertices that differ in only one digit. This joined to itself, is called a simple graph. Description
Vertices: A, B, C, DEdges: AB, AB, BC, BC, and the 3-digit binary strings form an ordi- more than one edge, is called a multigraph.
the 6-litre jug, and then pour from one jugto another, always stopping when the jugbeing poured to becomes full or when the jug being poured from becomes empty.
Is it possible to reach a state where one A Gray code of length n is a path which jug contains 1 litre and another contains 5 includes each vertex of the n-cube exactly 000, 001, 011, 010, 110, 111, 101, 100 a = number of litres in the 3-litre jug b = number of litres in the 4-litre jug c = number of litres in the 6-litre jug (a , b , c ) can be reached from (a, b, c) bypouring as described above, we put a di- If (a, b, c) can also be reached from (a , b , c ), we join them by an ordinary edge.
Remark. The n-cube has been popular
as a computer architecture in recent years.
reached from (0, 0, 6), we find the following Processors are placed at the vertices of an n-cube (for n = 15 or so) and connectedalong its edges.
2. Travelling salesman problem
Vertices are towns. Two towns are joined byan edge labelled l if there is a road of length edges, is called a directed graph or digraph.
length which includes all towns, in this case (0, 0, 6) → (0, 4, 2) → (3, 1, 2) → (0, 1, 5) 3. Jug problems
hence we can start with a full 6-litre jug and Suppose we have three jugs, which hold ex- in three pourings get 1 litre in the 4-litre jug actly 3, 4 and 6 litres respectively. We fill

Source: http://m91199119.fastmail.fm/mat1830/lecturesetc/lect26.pdf