You are here: Home › … › Previous Courses › 2013 › Graphentheorie

Graphentheorie

In dieser Vorlesung werden Grundlagen der Graphentheorie für Bachelor-Studenten der Informatik behandelt.

Aktuelles

  • 07.10.2013: Webseiten online
  • 23.10.2013: 1. Vorlesung
  • 05.11.2013: Wegen Serverproblemen stellen wir alles Material auch über BitTorrent Sync1 zur Verfügung. Secret: BTDRLQFTNNFVMXTO53SOGYE5AEBZ5TBI3
  • 06.11.2013: Übungsgruppenräume korrigiert
  • 16.12.2013: Websystem läuft auf neuer Domain und neuem Zertifikat
  • 30.01.2014: Beginn der Lehrevaluation!
  • 26.02.2014: Es gibt eine Probeklausur2 zum selbst Üben
  • 08.04.2014: Die Klausureinsicht findet um 10 Uhr im Raum 51-02-07 statt! 
  • 29.08.2014: Die Nachklausur findet um 9 Uhr  im Raum 101-00-010/014 statt!

Inhalt

In dieser Vorlesung werden Grundlagen der Graphentheorie für Bachelor-Studenten der Informatik behandelt.

  1. Grundlagen
  2. Matching
  3. Zusammenhang
  4. Planare Graphen
  5. Färbbarkeit
  6. Flüsse in Graphen
  7. Zufallsgraphen

Organisation

Vorlesung

  • Christian Schindelhauer
    • Mittwoch, 14:00 - 16:00 c.t., Seminarraum 101-01-009/013

Übungen

Übungen finden wie unten im Zeitplan vermerkt statt. Übungsabgabe über das Websystem3. Näheres dazu gibt es in der Vorlesung.

  1. Mittwoch 15-16 Uhr (1h) oder 14-16 Uhr (2h) Seminarraum 51-03-026, Thomas Janson 
  2. Mittwoch 15-16 Uhr (1h) oder 14-16 Uhr (2h), Seminarraum 101-01-009/013, Christian Ortolf
  3. Donnerstag 9-10 Uhr (1h) oder 8-10 Uhr (2h) Seminarraum 78-00-014, Thomas Janson
  4. Donnerstag 14-15 Uhr (1h) oder 14-16 Uhr (2h), Seminarraum 101-01-016, Christian Ortolf

Zeitplan

Datum Vorlesungsstunden Übungsstunden Kapitel Aufzeichnung
23.10.2013 2   Einführung mp44
30.10.2013 2   Einführung Teil15  Teil26
06.11.2013 1 1 Speicherung mkv7
13.11.2013 2   Matching mkv8
20.11.2013 2   Wege, Kreise, Zusammenhang
Topologische Sortierung, Eulerscher Weg		 mkv9
27.11.2013    2 Zusammenhang  
04.12.2013 2   Satz von Euler, Hamiltonsche Graphen, Graphfärbung Teil110  Teil211
11.12.2013 2   Graphfärbung Teil112  Teil213
18.12.2013   2 Bäume, Tiefensuche  
08.01.2014 2   Tiefensuche Teil114  Teil215
15.01.2014 1  1 Flüsse mkv16
22.01.2014 2   Das Flussproblem Teil117  Teil218
29.01.2014    2 Flüsse  
05.02.2014 2   Zufallsgraphen Teil119  Teil220
12.02.2014  1 1 Zufallsgraphen  mkv21

Forum

Zu der Vorlesung ist ein Forum22 eingerichtet, in dem inhaltliche und organisatorische Fragen diskutiert werden können. Eine Registrierung dafür ist nicht notwendig.

Material

Bei dieser Veranstaltung wird hauptsächlich die Tafel und nur ausnahmsweise Vorlesungsfolien verwendet. Die gesamte Veranstaltung wird aufgezeichnet und hier veröffentlicht.

Übungsblätter

Übungsblätter müssen über das Übungsportal abgegeben werden. Deadline ist der jeweilige Dienstag vor der Besprechung.

  1. Übungsblatt23 erschien am 30.10.2013
  2. Übungsblatt24 erschien am 20.11.2013
  3. Übungsblatt25 erschien am 11.12.2013
  4. Übungsblatt26 erschien am 08.01.2014
  5. Übungsblatt27 erschien am 22.01.2014
  6. Übungsblatt28 erschien am 05.02.2014

Tools

Um Graphen zu zeichnen kann das Tool yEd29 verwendet werden.

Prüfung

Die schriftliche Prüfung findet am 25.03.2014 um 9 Uhr s.t. im Kinohörsaal, Gebäude 82 statt . Die Prüfungsanmeldung erfolgt online über das HIS. Weitere Zulassungsvoraussetzungen gibt es nicht. Beachten Sie die Fristen! Außer Schreibzeug sind keine Hilfsmittel mitzubringen. Es wird aber eine Auswahl der eigenen Übungslösungen am Platz bereitgestellt. Hierbei werden nur sinnvolle Abgabe berücksichtigt ohne Programmausdrucke und ohne Korrekturen der Tutoren. Wenn keine Teilnahme am Peer-Review-Verfahren stattfand wird die entsprechende Übungslösung ebenso nicht berücksichtigt. Im Falle von Plagiaten bei der Übungsabgabe behalten wir uns vor überhaupt kein Material bereit zu stellen. Vor der Klausur erhalten Sie die Möglichkeit die Auswahl einzusehen.

Die zugeordneten Studiengänge und Prüfungsmodule sind im Vorlesungsverzeichnis30 aufgeführt.

Literatur

  • Graphentheoretische Konzepte und Algorithmen, Sven Oliver Krumke und Hartmut Noltemeier. Springer 2012. (Online31 nur innerhalb des Uni-Netzes)
  • Graph Theory, Reinhard Diestel, Electronic Edition 2010 pdf32

Weitere Literaturhinweise werden hier im Verlauf der Veranstaltung veröffentlicht.

Links

  1. http://labs.bittorrent.com/experiments/sync.html
  2. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/Material/probeklausur.pdf
  3. https://conesvn.informatik.uni-freiburg.de:13241/websys/student?lecture=graphentheoriews13
  4. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT01-Einf%C3%BChrung-2013-10-23.mp4
  5. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT02-Teil1_Ungerichteter_Graph-2013-10-30.mkv
  6. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT02-Teil2_Ungerichteter_Graph-2013-10-30.mkv
  7. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT03-Speicherung_Matching-2013-11-06.mkv
  8. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT04-Matching-2013-11-13.mkv
  9. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT05-Wege_Kreise_Zusammenhang-2013-11-20.mkv
  10. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT06-Teil1_Hamilton_04-12-2013.mkv
  11. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT06-Teil2_Hamilton_04-12-2013.mkv
  12. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT07-Teil1-Graphfaerbung-11-12-2013.mkv
  13. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT07-Teil2-Graphfaerbung-11-12-2013.mkv
  14. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT08-Teil1-Baum-Tiefensuche-08-01-2014.mkv
  15. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT08-Teil2-Baum-Tiefensuche-08-01-2014.mkv
  16. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT09-DFS-Kreise-15-01-2014.mkv
  17. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT10-Teil1-Flussproblem-22-01-2014.mkv
  18. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT10-Teil2-Flussproblem-22-01-2014.mkv
  19. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT11-Teil1-Kruskal_Prim_Boruvka-05-02-2104.mkv
  20. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT11-Teil2-Kruskal_Prim_Boruvka-05-02-2104.mkv
  21. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/video/GT12-Zufallsgraphen-12-02-2014.mkv
  22. http://archive.cone.informatik.uni-freiburg.de/forum3/viewforum.php?f=23
  23. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/uebung/Blatt01.pdf
  24. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/uebung/Blatt02.pdf
  25. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/uebung/Blatt03.pdf
  26. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/uebung/Blatt04.pdf
  27. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/uebung/Blatt05.pdf
  28. http://archive.cone.informatik.uni-freiburg.de/lehre/lecture/graphentheorie-w13/uebung/Blatt06.pdf
  29. http://www.yworks.com/en/downloads.html
  30. https://www.verwaltung.uni-freiburg.de/qis
  31. http://www.springerlink.com/content/978-3-8348-1849-2/
  32. http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.pdf