240603 Algebraische Graphentheorie und Komplexitätstheorie (V) (WiSe 2011/2012)
Contents, comment
-
Die Vorlesung setzt die Vorlesung Graphentheorie des SoSe 2011 fort und bereitet ein Bachelorarbeitsseminar im SoSe 2012 vor, das maximal 15 Teilnehmer haben kann.
Zunächst wird es in der Vorlesung um Komplexitätstheorie gehen, genauer um NP-vollständige Probleme. Hierbei wird zunächst die NP-Vollständigkeit des Belegbarkeitsproblems der Aussagenlogik bewiesen werden. Darauf aufbauend werden NP-vollständige Graphentheorie-Probleme, wie das 3-Färbbarkeitsproblem und das Hamiltonkreis-Problem diskutiert werden.
Anschließend wird es um algebraische Graphentheorie gehen. Das beinhaltet zum einen eine kategorielle Heransgehensweise, mit der etwa Färbbarkeit von Produkten diskutiert werden kann. Die kategorielle Herangehensweise erlaubt aber auch die Reduktion graphentheoretischer Fragestellungen auf NP-vollständige Probleme.
Zum anderen kann man man Lineare Algebra einsetzen, um Eigenwert-Spektren von Graph-Matrizen zu untersuchen. Weiterhin kann man Graphen Polynome zuordnen, die Grapheigenschaften widerspiegeln, wie etwa das chromatische Polynom. Hierbei gibt es auch einen Zusammenhang zur Knotentheorie.
Abschließend wird es um den Zusammenhang zwischen Graphen- und Gruppentheorie gehen, insbesondere Gruppenpräsentationen und Freiheit von Gruppen, indem man Gruppenoperationen auf Graphen studiert. Hierbei spielen Cayley-Graphen eine wesentliche Rolle.
Requirements for participation, required level
-
Notwendig: Die Vorlesung Graphentheorie des SoSe 2011, Lineare Algebra I+II
Hilfreich: Algebra I
External comments page
Teaching staff
Dates ( Calendar view )
| Frequency | Weekday | Time | Format / Place | Period | |
|---|---|---|---|---|---|
| weekly | Mo | 14-16 | S0-115 | 10.10.2011-03.02.2012
not on: 12/26/11 / 1/2/12 |
|
| weekly | Mi | 14-16 | C0-269 | 10.10.2011-03.02.2012
not on: 12/28/11 / 1/4/12 |
Subject assignments
| Degree programme/academic programme | Validity | Variant | Subdivision | Status | Semester | LP | |
|---|---|---|---|---|---|---|---|
| Mathematik / Bachelor | (Enrollment until SoSe 2011) | Kernfach | MM09a; MM10 | Wahlpflicht | 4. 5. | 7 | benotet |
| Mathematik / Diplom | (Enrollment until SoSe 2008) | Wahl | 5. 6. 7. 8. | scheinfähig HS | |||
| Mathematik / Master | (Enrollment until SoSe 2011) | MM02S | Wahl | 9 | |||
| Mathematik / Master | (Enrollment until SoSe 2011) | MM01S | Wahlpflicht | 1. | 9 | unbenotet | |
| Mathematik / Master | (Enrollment until SoSe 2011) | MM07S | Wahlpflicht | 1. | 9 | benotet | |
| Mathematik (Gym/Ge als zweites U-Fach) / Master of Education | (Enrollment until SoSe 2014) | M.M.10 | Wahlpflicht | 4. | 7 | benotet | |
| Mathematik (Gym/Ge fortgesetzt) / Master of Education | (Enrollment until SoSe 2014) | M.M.10 | Wahlpflicht | 2. 3. | 7 | benotet | |
| Studieren ab 50 | |||||||
| Wirtschaftsmathematik / Diplom | (Enrollment until SoSe 2005) | Wahl | 5. 6. 7. 8. | scheinfähig HS | |||
| Wirtschaftsmathematik / Master | (Enrollment until SoSe 2011) | MW01S | Wahl | 9 | |||
| Wirtschaftsmathematik / Master | (Enrollment until SoSe 2011) | MW05S | Wahlpflicht | 2. | 9 | benotet | |
| Wirtschaftsmathematik (1-Fach) / Bachelor | (Enrollment until SoSe 2011) | M.WM.14; M.WM.15 | Wahlpflicht | 4. 5. 6. | 7 | benotet |
Wird in der Vorlesung bekanntgegeben.
- Address:
- WS2011_240603@ekvv.uni-bielefeld.de
- This address can be used by teaching staff, their secretary's offices as well as the individuals in charge of course data maintenance to send emails to the course participants. IMPORTANT: All sent emails must be activated. Wait for the activation email and follow the instructions given there.
- If the reference number is used for several courses in the course of the semester, use the following alternative address to reach the participants of exactly this: VST_26084801@ekvv.uni-bielefeld.de
- Notes:
- Additional notes on the electronic mailing lists
- Last update basic details/teaching staff:
- Friday, December 11, 2015
- Last update times:
- Wednesday, July 13, 2011
- Last update rooms:
- Wednesday, July 13, 2011
- Type(s) / SWS (hours per week per semester)
- lecture (V) / 4
- Department
- Faculty of Mathematics
- Questions or corrections?
- Questions or correction requests for this course?
- Planning support
- Clashing dates for this course
- Links to this course
- If you want to set links to this course page, please use one of the following links. Do not use the link shown in your browser!
- The following link includes the course ID and is always unique:
- https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=26084801
- Send page to mobile
-
Click to open QR code
Scan QR code:
- ID
- 26084801