Option Statistics | Sets, Relations and Groups | Discrete Mathematics | Analysis and Approximation | Euclidean Geometry and Conic Sections | Main Page
- 11.1
- Natural numbers and the well-ordering principle.
- 11.2
- Division and Euclidian algorithms. The greatest common divisor of integers a and b, (a, b). Relatively prime numbers; prime numbers and the fundamental theorem of arithmetic.
- 11.3
- Congruence modulo p as an equivalence class. Residue classes.
- 11.4
- Recurrence relations.Difference equations: basic definitions and solutions of a difference equation.
- 11.5
- Simple graphs; connected graphs; complete graphs; multigraphs; directed graphs; bipartite graphs; planar graphs. Subgraphs; complements of graphs. Graph isomorphism.
Mathmania Graph Theory, from the University of Victoria, provides an introduction to graphs, together with a Graph Glossary. Background and definitions can be found at Graph Theory, from Stephen Locke. Also see Graph Theory Definitions.
Colorful Mathematics, from the University of Calgary, offers a series of games that illustrate concepts from graph theory. Suitable for students in grades K-12.
A thorough treatment is provided at Graph Theory Tutorials, written by Chris Caldwell.
These tutorials require registration, which is free. A Glossary of Graph Theory Terms is included. Another set of tutorials is available at Graph Theory Lessons, from the University of Tennessee.In-depth information is provided by Oberlin College at their Graphs site. The site includes exercises. Also see Graph(Graph Theory), and Graph Theory, from the extensive Eric's Treasure Trove of Mathematics site.
For various examples involving graph theory, see Coloring, from The Geometry Junkyard.
See the Planar Graph entry from Eric's Treasure Trove of Mathematics.
See Null Graph, Complete Graph, Bipartite Graph and Isomorphic Graph, all from Eric's Treasure Trove of Mathematics.
The first five complete graphs.
All but the fifth of these graphs are planar. From the The Glossary of Graph Theory Terms.
Used with the permission of Chris Caldwell.
- 11.6
- Walks; Hamiltonian paths and cycles; Eulerian trails and circuits. Graph colouring and chromatic number of a graph.
See Euler and Hamiltonian Circuits, from Graph Theory Tutorials. Prior knowledge is assumed for this tutorial, and registration (free) is required.
Also see Eulerian Circuit and Hamiltonian Circuit, both from Eric's Treasure Trove of Mathematics.
Each vertex has degree three, since each has three edge ends.
There are also three loops in the diagram. The illustration is taken from
The Glossary of Graph Theory Terms, and is used with the
permission of Chris Caldwell.
Illustration from the game The Chromatic Number of a Graph, from the University of Calgary's Colorful Mathematics site. The player draws circles and lines (vertices and edges), and attempts to color the vertices such that those joined by an edge receive different colors. The object is to use the smallest number of colors possible - the chromatic number of the graph. The site contains several games, including The Four Color Map Problem.
Used with permission.
- 11.7
- Networks and trees: definitions and properties. The travelling salesman problem. Rooted trees; binary search trees; weighted trees; sorting; spanning trees; minimal spanning trees. Prim's, Kruskal's and Dijkstra's algorithms.
See the short Traveling Salesman Problem entry from Eric's Treasure Trove of Mathematics.
A knotted graph, from the Knot Plot Site.
Used with the permission of Bob Sharein
11. Discrete Mathematics
Option Statistics | Sets, Relations and Groups | Discrete Mathematics | Analysis and Approximation | Euclidean Geometry and Conic Sections | Main Page