Difference between revisions of "MAT4323"
Jump to navigation
Jump to search
Jose.iovino (talk | contribs) |
Jose.iovino (talk | contribs) |
||
| Line 4: | Line 4: | ||
''Contents'' | ''Contents'' | ||
| − | (1 | + | (1) Graph models: Isomorphisms, edge counting, planar graphs. |
| − | + | (2) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem | |
| − | + | (3) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems. | |
| − | ( | + | (4) Ramsey's Theorem and Ramsey numbers. |
| − | ( | ||
| − | ( | ||
== Sample textbooks == | == Sample textbooks == | ||
| Line 42: | Line 40: | ||
|| Counting with Venn diagrams. | || Counting with Venn diagrams. | ||
|- | |- | ||
| − | | | + | | 1-3 |
|| [[Graph models]] | || [[Graph models]] | ||
|| 12.1-12.3 | || 12.1-12.3 | ||
|| Isomorphism, edge counting, planar graphs. | || Isomorphism, edge counting, planar graphs. | ||
|- | |- | ||
| − | | | + | | 4-6 |
|| [[Covering circuits]] | || [[Covering circuits]] | ||
|| 2.1-2.4 | || 2.1-2.4 | ||
|| Euler circuits, Hamilton circuits, graph colorings, coloring theorems. | || Euler circuits, Hamilton circuits, graph colorings, coloring theorems. | ||
|- | |- | ||
| − | | 9 | + | | 8-9 |
|| [[Trees]] | || [[Trees]] | ||
|| 3.1-3.4 | || 3.1-3.4 | ||
|| Search trees, spanning trees, the Traveling Salesman Problem | || Search trees, spanning trees, the Traveling Salesman Problem | ||
|- | |- | ||
| − | | | + | | 10-12 |
|| [[Network algorithms]] | || [[Network algorithms]] | ||
|| 4.1-4.5 | || 4.1-4.5 | ||
|| Shortest path , minimum spanning trees, matching algorithms, transportation problems. | || Shortest path , minimum spanning trees, matching algorithms, transportation problems. | ||
| + | | 13-14 | ||
| + | || [[Network algorithms]] | ||
| + | || | ||
| + | || Ramsey's Theorem and Ramsey numbers | ||
|} | |} | ||
Revision as of 09:34, 21 April 2023
Catalog entry
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
Contents (1) Graph models: Isomorphisms, edge counting, planar graphs. (2) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem (3) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems. (4) Ramsey's Theorem and Ramsey numbers.
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. | ||||
| 1-3 | Graph models | 12.1-12.3 | Isomorphism, edge counting, planar graphs. | ||||
| 4-6 | Covering circuits | 2.1-2.4 | Euler circuits, Hamilton circuits, graph colorings, coloring theorems. | ||||
| 8-9 | Trees | 3.1-3.4 | Search trees, spanning trees, the Traveling Salesman Problem | ||||
| 10-12 | Network algorithms | 4.1-4.5 | Shortest path , minimum spanning trees, matching algorithms, transportation problems. | 13-14 | Network algorithms | Ramsey's Theorem and Ramsey numbers |
