LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Diskrete Strukturen I: Tutorgruppe GS


*12. November
Wieviele Personen kennen sich?
Wie groß müßen Graphen sein, damit sie einfarbige vollständige Teilgraphen enthalten? Obere und untere Schranken...
*19.November
Rauf und runter
Auf- und absteigende Teilfolgen und der Quicksort-Algorithmus...
*10.Dezember
Graphen ohne Kreise, ohne Dreiecke und mit vielen Farben
Im Kapitel über Ramsey-Zahlen, haben wir uns überlegt, wieviele Knoten ein vollständiger Graph mit roten und blauen Kanten haben muß, damit er einen blauen K_s oder einen roten K_t enthält. Genau dieselbe Fragestellung kann auch folgendermassen formuliert werden: wenn die blauen Kanten wirklich im Graph vorhanden sind, und die roten Kanten aus dem vollständigen Graph herausgenommen werden, haben die Frage beantwortet, wieviele Knoten ein Graph mindestens enthalten muß, damit er entweder einen K_s als Teilgraph enthält, oder aber es eine Menge von mindestens t Knoten gibt, zwischen denen keine Kante verläuft.
Hier wollen wir nun eine ähnliche Fragestellung betrachten - allerdings wollen wir nun Bedingungen für die Anzahl Kanten herleiten...


Martin Raab Last modified: Tue Jan 18 11:07:16 MET 2000