### Outline of IB Maths HL option Discrete mathematics

Posted:

**Mon Feb 25, 2013 5:43 pm**Outline of IB Mathematics Higher Level- Option: Discrete mathematics

Here you can find a description of the course not so detailed.

You can find the official syllabus of IB maths SL on the following link of IBO

http://www.ibo.org or http://store.ibo.org

Strong induction. Pigeon-hole principle. Division and Euclidean algorithms. The greatest common divisor, gcd(a,b) , and

the least common multiple, lcm(a,b) , of integers a and b.

Prime numbers; relatively prime numbers and the fundamental theorem of arithmetic.

Linear Diophantine equations ax + by = c

Modular arithmetic. The solution of linear congruences. Solution of simultaneous linear congruences (Chinese remainder theorem).

Representation of integers in different bases.

Fermat’s little theorem. Graphs, vertices, edges, faces. Adjacent vertices, adjacent edges. Degree of a vertex, degree sequence.

Handshaking lemma. Simple graphs, connected graphs, complete graphs, bipartite graphs, planar graphs; trees, weighted graphs, including tabular representation. Subgraphs; complements of graphs. Euler’s relation, theorems for

planar graphs. Walks, trails, paths, circuits, cycles. Eulerian trails and circuits. Hamiltonian paths and cycles.

Graph algorithms: Kruskal’s; Dijkstra’s. Chinese postman problem. Travelling salesman problem. Nearest-neighbour algorithm for determining

an upper bound. Deleted vertex algorithm for determining a lower bound.

Recurrence relations. Initial conditions, recursive definition of a sequence. Solution of first- and second-degree linear

homogeneous recurrence relations with constant coefficients. The first-degree linear recurrence relation.

Modelling with recurrence relations.

Here you can find a description of the course not so detailed.

You can find the official syllabus of IB maths SL on the following link of IBO

http://www.ibo.org or http://store.ibo.org

Strong induction. Pigeon-hole principle. Division and Euclidean algorithms. The greatest common divisor, gcd(a,b) , and

the least common multiple, lcm(a,b) , of integers a and b.

Prime numbers; relatively prime numbers and the fundamental theorem of arithmetic.

Linear Diophantine equations ax + by = c

Modular arithmetic. The solution of linear congruences. Solution of simultaneous linear congruences (Chinese remainder theorem).

Representation of integers in different bases.

Fermat’s little theorem. Graphs, vertices, edges, faces. Adjacent vertices, adjacent edges. Degree of a vertex, degree sequence.

Handshaking lemma. Simple graphs, connected graphs, complete graphs, bipartite graphs, planar graphs; trees, weighted graphs, including tabular representation. Subgraphs; complements of graphs. Euler’s relation, theorems for

planar graphs. Walks, trails, paths, circuits, cycles. Eulerian trails and circuits. Hamiltonian paths and cycles.

Graph algorithms: Kruskal’s; Dijkstra’s. Chinese postman problem. Travelling salesman problem. Nearest-neighbour algorithm for determining

an upper bound. Deleted vertex algorithm for determining a lower bound.

Recurrence relations. Initial conditions, recursive definition of a sequence. Solution of first- and second-degree linear

homogeneous recurrence relations with constant coefficients. The first-degree linear recurrence relation.

Modelling with recurrence relations.