Difference between revisions of "MAT4323"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
Line 9: Line 9:
 
(4) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem  
 
(4) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem  
 
(5) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems.
 
(5) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems.
(6) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles.
+
(6) Graph Colorings and Ramsey's Theorem.
  
 
== Sample textbooks ==  
 
== Sample textbooks ==  

Revision as of 09:21, 21 April 2023

Catalog entry

Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.

Contents (1) Basic counting principles: Permutations, combinations, binomial coefficients, arrangements with repetitions, and the Inclusion-Exclusion principle. (2) Graph models: Isomorphisms, edge counting (3) Planar graphs. (4) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem (5) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems. (6) Graph Colorings and Ramsey's Theorem.

Sample textbooks

[1] Vladlen Koltun, Discrete Structures, Lecture Notes, Stanford University, 2008. Freely available online here

[2] Alan Tucker, Applied Combinatorics, Freely available online here






Topics List

Week Topic Sections from Tucker's book Subtopics Prerequisite
1-2 Basic counting principles 5.1-5.5 Permutations, combinations, binomial coefficients, arrangements with repetitions MAT1313, CS2233/2231, or instructor consent.
3 Inclusion-Exclusion Principle 8.1-8.2 Counting with Venn diagrams.
4-6 Graph models 12.1-12.3 Isomorphism, edge counting, planar graphs.
7-8 Covering circuits 2.1-2.4 Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
9-10 Trees 3.1-3.4 Search trees, spanning trees, the Traveling Salesman Problem
11-13 Network algorithms 4.1-4.5 Shortest path , minimum spanning trees, matching algorithms, transportation problems.