14085 - Graph Theory Modulübersicht

Module Number: 14085
Module Title:Graph Theory
  Graphentheorie
Department: Faculty 1 - Mathematics, Computer Science, Physics, Electrical Engineering and Information Technology
Responsible Staff Member:
  • Prof. Dr. rer. nat. habil. Köhler, Ekkehard
Language of Teaching / Examination:English
Duration:1 semester
Frequency of Offer: Each winter semester odd year
Credits: 8
Learning Outcome:The students
  • Know the most important terms and connections of graph theory
  • Are able to apply graph theoretical concepts to solve practical problems
  • Used the example of graph theroretic topics to attain experience in self-contained scientific working
Contents:
  • Basic concepts, graphs, connectivity, trees
  • Matchings, colorings, flows
  • Hall's theorem, König's theorem, chromatic number, Menger's theorem
  • Planar graphs, Euler characteristic, Kuratowski's theorem, duality, cycle bases
  • Ethical responsibility in the application of models, algorithms and results
Recommended Prerequisites:

Knowledge of the content of the modules

  • 11101: Lineare Algebra und analytische Geometrie I
  • 12868: Algorithmische Diskrete Mathematik

or

  • 11112: Mathematik IT-1 (Diskrete Mathematik)
  • 11113: Mathematik IT-2 (Lineare Algebra)
Mandatory Prerequisites:
  • No successful participation in module 11415 Graphtheorie
Forms of Teaching and Proportion:
  • Lecture / 4 Hours per Week per Semester
  • Exercise / 2 Hours per Week per Semester
  • Self organised studies / 150 Hours
Teaching Materials and Literature:
  • D.B. West: Introduction to Graph Theory. (Prentice Hall, 1996)
  • R. Diestel: Graphentheorie. (Springer,1996)
Module Examination:Prerequisite + Final Module Examination (MAP)
Assessment Mode for Module Examination:

Prerequisite for final module examination:

  • Successful completion of homework (fortnightly) and successful completion of tests (approx. 4 tests of 15-30 minutes each, written during the lecture period)

Final module examination:

  • Written examination, 90 min. OR
  • Oral examination, 30 min.

During the first class meeting, notice will be given on how the prerequisite will be structured and whether the examination will be in written or oral form.

Evaluation of Module Examination:Performance Verification – graded
Limited Number of Participants:None
Part of the Study Programme:
  • Master (research-oriented) / Angewandte Mathematik / PO 2019 - 1. SÄ 2021
  • Master (research-oriented) / Artificial Intelligence / PO 2022 - 1. SÄ 2024
  • Bachelor (research-oriented) / Informatik / PO 2008 - 2. SÄ 2024
  • Master (research-oriented) / Informatik / PO 2008 - 3. SÄ 2024
  • Bachelor (research-oriented) / Künstliche Intelligenz / PO 2022
  • Master (research-oriented) / Künstliche Intelligenz Technologie / PO 2022 - 1. SÄ 2024
  • Master (research-oriented) / Mathematical Data Science / PO 2025
  • Master (research-oriented) / Mathematics / PO 2025
  • Bachelor (research-oriented) / Mathematik / PO 2023
  • Bachelor (research-oriented) - Co-Op Programme with Practical Placement / Mathematik - dual / PO 2023
  • Master (research-oriented) / Physics / PO 2021
  • Bachelor (research-oriented) / Wirtschaftsmathematik / PO 2023
  • Bachelor (research-oriented) - Co-Op Programme with Practical Placement / Wirtschaftsmathematik - dual / PO 2023
Remarks:
  • Study programme Angewandte Mathematik M.Sc.: Compulsory elective module in complex „Analysis / Algebra / Kombinatorik”
  • Study programme Mathematics M.Sc.:Compulsory elective module in complex „Analysis / Algebra / Combinatorics”
  • Study programme Mathematical Data Science M.Sc.: Compulsory elective module in complex „Advanced Mathematical Methods in Data Science”
  • Study programme Mathematik B.Sc.: Compulsory elective module in complex „Vertiefung”, in limited extend 
  • Study programme Wirtschaftsmathematik B.Sc.: Compulsory elective module in complex „Vertiefung”, in limited extend
  • Study programme Informatik B.Sc.: Compulsory elective module in  „Praktische Mathematik” or in field of application „Mathematik”
  • Study programme Informatik M.Sc.: Compulsory elective module in „Mathematik” or in field of application „Mathematik”
  • Study programme Künstliche Intelligenz B.Sc.: Compulsory elective module in complex „Wissensakquise, -repräsentation und -verarbeitung”
  • Study programme Künstliche Intelligenz Technologie M.Sc.: Compulsory elective module in complex „Software-basierte Systeme”
  • Study programme Artificial Intelligence M.Sc.: Compulsory elective module in complex „Knowledge Acquisition, Representation, and Processing”
  • Study programme Physics M.Sc.: Compulsory elective module in complex „Minor Subject”
Module Components:
  • Lecture: Graph Theory
  • Accompanying exercises
  • Related examination
Components to be offered in the Current Semester: