DCI '00


Barry Tesman
Education Program Director


I.1. Introduction: Games and graphs - a natural connection.

Definitions, digraphs and games of chance.

I.2. Connectivity

Connectivity in graphs and digraphs. k-, dis-, strongly, unilaterally and weakly connected.

I.3. Decomposition and Matchings

Decomposition of graphs (in particular, 1-factors and cycles). Maximum and perfect matchings. Eulerian and Hamiltonian graphs.

I.4. Matchings and Colorings

Coloring the edges and/or vertices of a graph.

I.5. Matchings and Marriages

Stable marriages.


II.1. Stability and Domination

Stability and domination.

II.2. Markov Chains

Stochastic (vs. deterministic) processes. A.A. Markov and his chains.

II.3. Dr. Ecco

The Puzzling Adventures of Doctor Ecco.

II.4. Binary Relations/Order Relations/Posets

Properties of binary relations and their graph theoretic interpretation. Various order relations (e.g., weak, simple) and their applications. Partially ordered sets and lattices. Hasse diagrams and dimension.

II.5. Applications

More applications of the week's materials.

Syllabus last updated May 30, 2000