Combinatorics and Graph Theory (CombGra)5 ECTS

Lehrveranstaltungen:

• • Combinatorics and Graph Theory
    (Vorlesung, 4 SWS, Wolfgang Degen, Mi, 14:00 - 16:00, 0.141; Do, 14:00 - 16:00, Raum n.V.; Lehrstuhl Informatik 10, Cauerstraße 6; Vorbesprechung: 19.10.2010, 15:15 - 16:00 Uhr, 0.141)

Inhalt:

Combinatorial part:

• binomial coefficients

• pigeonhole principles

• Polya's theory of counting

• Striling numbers

• generating functions

Graph Theory part:

• spanning trees

• Hamiltonian cycles

• colouring problems and their algorithms

• matchings

• Ramsey theory

Combinatorics and Graph Theory from the standpoint of Set Theory

Lernziele und Kompetenzen:

The student will achieve some theoretical equipment of a computer scientist and will learn about the relations between Combinatorics and Graph Theory to Computer Science.

Literatur:

• Harris, Hirst, Mossinghoff: Combinatorics and Graph Teory, Springer 2008

• Graham, Knuth, Patashnik: Concrete Mathematics, Addison-Wesley, 1994

• Diestel: Graph Theory, Springer 2005

• Matousek: Lectures on Discrete Geometries, Springer 2002

• Matousek, Nesetril: Diskrete Mathematik - Eine Entscheidungsreise, Springer 2007