Definition - Graph

• Typen:
  • Multigraph
  • Vollständiger Graph ()
  • Bipartiter Graph
  • Weg ()
  • Kreis ()
  • Eulerscher Graph
  • Baum
  • Wald
    • Wurzelbaum
    • Gepflanzter Baum
    • Aufspannender Baum
• Konstrukte:
  • Knoten
    • Abstand zweier Knoten
  • Kanten
    • Kantendisjunktheit
  • Adjazenz
  • Inzidenz
  • Knotenüberdeckung
  • Teilgraph
    • Weg in einem Graphen
    • Spaziergang
  • Induzierter Teilgraph
    • Zusammenhangskomponente
  • Valenz
  • Zusammenhang
    • k-Zusammenhang
  • Eulertour
  • Isomorphie von Graphen
  • Radius eines Graphen
  • Zentrum eines Graphen
  • Graph Datenbank
• Suchverfahren
  • Breitensuche
  • Tiefensuche
• Generalisierungen:
  • Multigraph
• Eigenschaften:
  • Vollständigkeit
• Hinreichende Aussagen:
  • Satz von Erdös-Gallai
• Charakterisierungen:
  • Adjazenzmatrix
  • Valenzsequenz
• Involvierte Definitionen:
  • Relation
  • Kreuzprodukt
  • Irreflexivität
  • Symmetrie
  • Tupel
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Einfacher Graph

Als Graph bezeichnen wir Strukturen aus Knoten und Kanten.

Sei eine Menge an Knoten und eine Menge von Kanten zwischen diesen Knoten.

Wir schreiben Graphen auch als Tupel

Als Relation auf den Knoten betrachtet, sind die Kanten eines einfachen Graphen:

• irreflexiv
  keine Schleifen:
• symmetrisch
  .

In einfachen Graphen bezeichnen außerdem und dieselbe Kante.

Anmerkung

Keine "mehrfach"-Kanten in einfachen Graphen

Einfache Graphen können keine mehrfachen Kanten zwischen den gleichen Knoten enthalten. Seien zwei unterschiedliche Kanten. Dann kann nicht und . In diesem Fall ist .

Wenn diese beiden Eigenschaften doch gelten müssen, spricht man von einem Multigraphen.

Graphen und die Visualisierung

Graphen lassen sich durch Visualisierungen super veranschaulichen (und das ist auch sinnvoll).

Für die Theorie ist das aber irrelevant. Graphen sind ein abstraktes Konstrukt.