Graphentheorie

Einfache Sprache

Beschäftigt sich mit Graphen, deren Eigenschaften und Bezieheung zueinander.

Grundlagen

• Knoten
• Kante
• Graph
  • Arten
    • Ungerichteter Graph
    • Gerichteter Graph
    • Bipartiter Graph
    • Vollständiger Graph
    • Teilgraph
    • Baum
      • Alternierender Baum
    • Wald
      • Alternierender Wald
    • Flower (Graphentheorie)
  • Darstelllung
    • Adjazenzmatrix
    • Adjazenzliste
    • Inzidenzmatrix
    • Half-Edge-Datenstruktur
• Inzidenz
• Knotengrad
  • Eingangsgrad
  • Ausgangsgrad
  • Quelle
  • Senke
• Weg
  • Hamiltonweg
• Kantenzug
  • Gerichteter Kantenzug
  • Einfacher Kantenzug
  • Alternierender Kantenzug
  • Augmentierender Kantenzug
• Zyklus
  • Hamiltonzyklus

Maßzahlen

• Zentralitätsberechnung
  • Gradzentralität
  • Zwischenzentralität
  • Nähezentralität
• Dichte
• PageRank

Theoreme

Matching

• Bipartiter Graph & Maximum Matching => Satz von König (Graphentheorie)
  • Matching Augmentation Lemma
  • Maximum matching no augmenting path theorem
• Heiratssatz
• Tutte-Berge Formel

Bekannte Probleme

Suchalgorithmus

• MST
• Kürzeste Wegeproblem

Durchlaufbarkeit von Graphen

• Eulerkreisproblem
• Hamiltonkreisproblem
• Traveling Salesman Problem
• Briefträgerproblem

Weitere

• Färbungsproblem
• matching
  • Maximum Kardinalität Matching-Problem
  • Gewichtetes Matching-Problem
• Knotenüberdeckung
  • minimale Knotenüberdeckung
  • Knotenüberdeckungszahl
  • Knotenüberdeckungsproblem
• Flüsse und Schnitte in Netzwerken
• Graphzeichen
• Knotenüberdeckungproblem
• Cliquenproblem
• Zusammenhang

Dafür Bekannte Algorithmen