[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]
The intent of the course is obtained by the student by attending the lessons. During the lessons everyone should feel free to pose questions at any time. To ensure the theory of lesson to be explained clearly and at a reasonable speed the blackboard will be used throughout the lessons. Further the exercises are of great help, and the answers are shown on the blackboard by the students.
Kurset vil være en fortsættelse af grafteori I, der i store træk blev udgjort af kapitlerne 1-8 i ovennævnte bog. Grafteori 2 vil fortsætte, hvor grafteori 1 slap, hvilket vil sige, at emnerne konnektivitet og matching (kap. 8), farvning af knuder og kanter i en graf (kap. 9), introduktion til matroider (kap.10) vil blive gennemgået. Flows i netværk vil også blive gennemgået (kap. 12). Matching vil blive relateret til heltalsprogrammering, hvorfor lineær programmering også er en forudsætning, mens heltalsprogrammering vil være en fordel.
The course consists of 3 lectures per week plus at least 6 tutorials. Since it is a two quarter course it consists of 42 lectures and at least 6 tutorials plus an oral exam at the end of the course.
The course is placed as a candidate course and the only prerequisite is the course Graph Theory 1. The course will fit very well for everyone interested in Operation Research or more general, for everyone interested in applied mathematics.
The topics, which make up of 90-100% of the course, are the following. The gap is devoted to suggestions coming from the students.
The topics are: matchings (in general, complete-, perfect-), coloring of nodes and edges of a graph, shortest paths in a directed graph, algorithms for finding a perfect matching, optimal assignment, Chinese postman problem, Euler trails in Euler graphs and maximal flow in oriented networks.
Grafteori 1, lineær programmering, mens heltalsprogrammering vil være en fordel.
Steen Friis Møller.
3 timer pr. uge.
The course consists of regular lessons and in addition some tutorials. Both parts are held by the same teacher. There are no additional requirements to facilitate the course.
.
The course is based on the book "Graphs: Theory and Applications" written by K. Thulasiraman and M. N. S. Swamy, Wileys, 1992. The book is used in both Graph Theory 1 and Graph Theory 2. Graph Theory 2 is based on the chapters 8, 9, 11 and 12 in the above mentioned book.
K. Tulasiraman og N.S. Swamy: Graphs: Theory and Algorithms, John Wiley & Sons, INC.
L.A. Wolsey and G.L. Nemhauser: Integer and combinatorial optimization, Wiley & Sons, INC., 1999.
Institut for Matematiske Fag.
Informationskontoret, Institut for Matematiske Fag.
After the course the student should be familiar with matchings in graphs, coloring of graphs and graph based algorithms. The student should be able to transform the theory of matchings and colorings into practical applications. Concerning the theorems and proofs the requirements are that the students know the theorems and are able to reproduce the proofs. Concerning the algorithms the following is noted: For each algorithm explained during the course, the student should be able to explain why the algorithm works and how the algorithm is used. The list of algorithms explained during the course consists at least of a shortest paths algorithm, perfect matching, optimal assignment, Chinese postman problem, maximal flow in a directed network. Depending on the students suggestions some other algorithms could be added.
30 min. mundtlig eksamen uden forberedelse.
The exam is an individual oral exam without preparation time. The questions are not announced prior to the examination. But the list of literature on which the examination will be based is clear prior to the start of the course; some modifications are allowed, if the students have some specific wishes. The duration time of an examination is 30 minutes per student including drawing the question and the evaluation of the presentation. All this is every year cleared with the students. The set of marks used for evaluation is the 7-steps scale.
