Kurs:Diskrete Mathematik (Osnabrück 2020)/Definitionsliste


Definition:Endliche Menge

Eine Menge heißt endlich mit Elementen, wenn es eine Bijektion

gibt.



Definition:Fakultät

Zu einer natürlichen Zahl nennt man die Zahl

die Fakultät von (sprich Fakultät).



Definition:Permutation

Eine Permutation auf einer Menge ist eine bijektive Abbildung



Definition:Potenzmenge

Zu einer Menge nennt man die Menge aller Teilmengen von die Potenzmenge von . Sie wird mit

bezeichnet.



Definition:Binomialkoeffizient

Es seien und natürliche Zahlen mit . Dann nennt man

den Binomialkoeffizienten über “.



Definition:Verknüpfung

Eine Verknüpfung auf einer Menge ist eine Abbildung



Definition:Kommutative Verknüpfung

Eine Verknüpfung

auf einer Menge heißt kommutativ, wenn für alle die Gleichheit

gilt.



Definition:Assoziative Verknüpfung

Eine Verknüpfung

auf einer Menge heißt assoziativ, wenn für alle die Gleichheit

gilt.



Definition:Neutrales Element

Es sei eine Menge mit einer Verknüpfung

gegeben. Dann heißt ein Element neutrales Element der Verknüpfung, wenn für alle die Gleichheit gilt.



Definition:Inverses Element

Es sei eine Menge mit einer Verknüpfung

und einem neutralen Element gegeben. Dann heißt zu einem Element ein Element inverses Element, wenn die Gleichheit

gilt.



Definition:Monoid

Ein Monoid ist eine Menge zusammen mit einer Verknüpfung

und einem ausgezeichneten Element derart, dass folgende beiden Bedingungen erfüllt sind.

  1. Die Verknüpfung ist assoziativ, d.h. es gilt

    für alle .

  2. ist neutrales Element der Verknüpfung, d.h. es gilt

    für alle .



Definition:Kommutativer Halbring

Ein kommutativer Halbring ist eine Menge mit Verknüpfungen und (genannt Addition und Multiplikation) und mit zwei ausgezeichneten Elementen und derart, dass folgende Bedingungen erfüllt sind:

  1. Die Addition ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
  2. Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
  3. Es gilt das Distributivgesetz, also

    für alle

    .


Definition:Gruppe

Eine Menge mit einem ausgezeichneten Element und mit einer Verknüpfung

heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

  1. Die Verknüpfung ist assoziativ, d.h. für alle gilt
  2. Das Element ist ein neutrales Element, d.h. für alle gilt
  3. Zu jedem gibt es ein inverses Element, d.h. es gibt ein mit


Definition:Kommutative Gruppe

Eine Gruppe heißt kommutativ (oder abelsch), wenn die Verknüpfung kommutativ ist, wenn also für alle gilt.



Definition:Untergruppe

Es sei eine Gruppe. Eine Teilmenge heißt Untergruppe von wenn folgendes gilt.

  1. .
  2. Mit ist auch .
  3. Mit ist auch .


Definition:Ring

Eine Menge heißt ein Ring, wenn es zwei Verknüpfungen (genannt Addition und Multiplikation)

und (nicht notwendigerweise verschiedene) Elemente gibt, die die folgenden Eigenschaften erfüllen.

  1. Axiome der Addition
    1. Assoziativgesetz: Für alle gilt .
    2. Kommutativgesetz: Für alle gilt .
    3. ist das neutrale Element der Addition, d.h. für alle ist .
    4. Existenz des Negativen: Zu jedem gibt es ein Element mit .
  2. Axiome der Multiplikation
    1. Assoziativgesetz: Für alle gilt .
    2. ist das neutrale Element der Multiplikation, d.h. für alle ist .
  3. Distributivgesetz: Für alle gilt und .


Definition:Kommutativer Ring

Ein Ring heißt kommutativ, wenn die Multiplikation kommutativ ist.



Definition:Körper

Ein kommutativer Ring heißt Körper, wenn ist und wenn jedes von verschiedene Element ein multiplikatives Inverses besitzt.



Definition:Relation

Es seien und Mengen. Eine Relation zwischen den Mengen und ist eine Teilmenge der Produktmenge , also .



Definition:Graph einer Abbildung

Es seien und Mengen und es sei

eine Abbildung. Dann nennt man

den Graphen der Abbildung .



Definition:Linkseindeutige Relation

Eine Relation heißt linkseindeutig, wenn es zu jedem maximal ein mit gibt.



Definition:Rechtseindeutige Relation

Eine Relation heißt rechtseindeutig, wenn es zu jedem maximal ein mit gibt.



Definition:Linksvollständige Relation

Eine Relation heißt linksvollständig, wenn es zu jedem ein mit gibt.



Definition:Rechtsvollständige Relation

Eine Relation heißt rechtsvollständig, wenn es zu jedem ein mit gibt.



Definition:Relation auf einer Menge

Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge , also .



Definition:Reflexiv

Eine Relation auf einer Menge heißt reflexiv, wenn für alle gilt.



Definition:Transitiv

Eine Relation auf einer Menge heißt transitiv, wenn aus und stets folgt.



Definition:Symmetrisch

Eine Relation auf einer Menge heißt symmetrisch, wenn aus stets folgt.



Definition:Antisymmetrisch

Eine Relation auf einer Menge heißt antisymmetrisch, wenn aus und stets folgt.



Definition:Relationstreu

Es seien und Mengen mit darauf erklärten Relationen bzw. . Man nennt eine Abbildung

relationstreu (oder relationserhaltend), wenn für alle mit auch gilt.



Definition:Ordnungsrelation

Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

  1. Es ist für alle .
  2. Aus und folgt stets .
  3. Aus und folgt .


Definition:Lineare Ordnung

Eine Ordnungsrelation auf einer Menge heißt lineare Ordnung (oder totale Ordnung), wenn zu je zwei Elementen die Beziehung oder gilt.



Definition:Angeordneter Ring

Ein kommutativer Ring heißt angeordnet, wenn es eine totale Ordnung auf gibt, die die beiden Eigenschaften

  1. Aus folgt für beliebige ,
  2. Aus und folgt für beliebige ,

erfüllt.



Definition:Teilen ()

Man sagt, dass die natürliche Zahl die natürliche Zahl teilt (oder dass von geteilt wird, oder dass ein Vielfaches von ist), wenn es eine natürliche Zahl derart gibt, dass ist. Man schreibt dafür auch .



Definition:Produktordnung

Es sei , , eine Familie von geordneten Mengen. Dann nennt man die auf der Produktmenge durch

falls

für alle gilt, die Produktordnung.



Definition:Ordnungstreu

Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

heißt ordnungstreu (oder monoton), wenn für alle mit stets auch gilt.



Definition:Ordnungsvolltreu

Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

heißt ordnungsvolltreu, wenn für alle genau dann gilt, wenn gilt.



Definition:Monoton fallende Abbildung

Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

heißt monoton fallend, wenn für alle mit stets gilt.



Definition:Größtes Element

Es sei eine geordnete Menge. Ein Element heißt größtes Element von , wenn für jedes gilt.



Definition:Kleinstes Element

Es sei eine geordnete Menge. Ein Element heißt kleinstes Element von , wenn für jedes gilt.



Definition:Maximales Element

Es sei eine geordnete Menge. Ein Element heißt maximal (in ) oder ein maximales Element (von ), wenn es kein Element , , mit gibt.



Definition:Minimum

Es sei eine geordnete Menge. Ein Element heißt minimal (in ) oder ein minimales Element (von ), wenn es kein Element , , mit gibt.



Definition:Obere Schranke

Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt obere Schranke für , wenn für jedes gilt.



Definition:Untere Schranke

Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt untere Schranke für , wenn für jedes gilt.



Definition:Supremum

Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt Supremum von , wenn die kleinste obere Schranke von ist.



Definition:Infimum

Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt Infimum von , wenn die größte untere Schranke von ist.



Definition:Gemeinsamer Teiler

Es seien natürliche Zahlen. Dann heißt eine natürliche Zahl gemeinsamer Teiler der , wenn jedes teilt für .



Definition:Gemeinsamer Teiler

Es seien natürliche Zahlen. Dann heißt eine natürliche Zahl der größte gemeinsame Teiler der , wenn ein gemeinsamer Teiler der ist und wenn jeder gemeinsame Teiler der dieses teilt.



Definition:Gemeinsames Vielfaches

Zu einer Menge von natürlichen Zahlen

heißt eine natürliche Zahl ein gemeinsames Vielfaches, wenn ein Vielfaches von jedem ist, also von jedem geteilt wird.



Definition:Kleinstes gemeinsames Vielfaches

Zu einer Menge von natürlichen Zahlen

heißt eine natürliche Zahl das kleinste gemeinsame Vielfache dieser Zahlen, wenn ein gemeinsames Vielfaches der ist und wenn jedes gemeinsame Vielfache der Zahlen ein Vielfaches von ist.



Definition:Euklidische Restfolge

Es seien zwei ganze Zahlen (mit ) gegeben. Dann nennt man die durch die Anfangsbedingungen und und die mittels der Division mit Rest

rekursiv bestimmte Folge die Folge der euklidischen Reste.



Definition:Verband

Eine geordnete Menge mit der Eigenschaft, dass für je zwei Elemente ein Infimum und ein Supremum existiert, heißt Verband.



Definition:Algebraischer Verband

Eine Menge mit zwei kommutativen und assoziativen Verknüpfungen und heißt algebraischer Verband, wenn die Absorptionsgesetze

und

gelten.



Definition:Zugehörige Ordnung (Verband)

In einem algebraischen Verband nennt man die durch

falls

definierte Ordnung, die zugehörige Ordnung.



Definition:Beschränkter Verband

Ein Verband heißt beschränkt, wenn es in ihm ein kleinstes Element und ein größtes Element gibt.



Definition:Komplementärer Verband

Ein beschränkter Verband heißt komplementär, wenn es zu jedem ein mit und gibt.



Definition:Distributiver Verband

Ein Verband heißt distributiv, wenn in ihm die Distributivgesetze

und

gelten.



Definition:Boolescher Verband

Ein Verband heißt boolesch, wenn er komplementär und distributiv ist.



Definition:Atom

Es sei eine geordnete Menge mit einem kleinsten Element . Ein Element heißt Atom, wenn ist und die Beziehung nur für und gilt.



Definition:Äquivalenzrelation

Eine Äquivalenzrelation auf einer Menge ist eine Relation , die die folgenden drei Eigenschaften besitzt (für beliebige ).

  1. Es ist (reflexiv).
  2. Aus folgt (symmetrisch).
  3. Aus und folgt (transitiv).

Dabei bedeutet , dass das Paar zu gehört.



Definition:Äquivalenzklasse

Es sei eine Äquivalenzrelation und . Dann ist

die Äquivalenzklasse von bezüglich .



Definition:Repräsentantensystem

Es sei eine Äquivalenzrelation auf einer Menge . Eine Teilmenge heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element in aus dieser Klasse gibt.



Definition:Quotientenmenge

Sei eine Äquivalenzrelation. Dann heißt

die Quotientenmenge von .



Definition:Kanonische Projektion

Es sei eine Äquivalenzrelation und die Quotientenmenge. Die Abbildung

heißt kanonische Projektion von .



Definition:Gruppenhomomorphismus

Seien und Gruppen. Eine Abbildung

heißt Gruppenhomomorphismus, wenn die Gleichheit

für alle gilt.



Definition:Ringhomomorphismus

Es seien und Ringe. Eine Abbildung

heißt Ringhomomorphismus, wenn folgende Eigenschaften gelten:

  1. .
  2. .
  3. .


Definition:Äquivalenzrelation zu einer Untergruppe

Es sei eine kommutative Gruppe und eine Untergruppe. Für Elemente setzen wir (und sagen, dass und äquivalent sind), wenn .



Definition:Restklassengruppe

Es sei eine kommutative Gruppe und eine Untergruppe. Die Quotientenmenge

mit der aufgrund von Satz 12.5 eindeutig bestimmten Gruppenstruktur heißt Restklassengruppe von modulo . Die Elemente heißen Restklassen. Für eine Restklasse heißt jedes Element mit ein Repräsentant von .



Definition:Ideal

Eine Teilmenge eines kommutativen Ringes heißt Ideal, wenn die folgenden Bedingungen erfüllt sind:

  1. .
  2. Für alle ist auch .
  3. Für alle und ist auch .


Definition:Multinomialkoeffizient

Es sei eine natürliche Zahl und natürliche Zahlen mit . Dann nennt man

den Multinomialkoeffizienten über .



Definition:Partition

Es sei eine Menge. Eine Teilmenge heißt Partition von , falls die folgenden Bedingungen erfüllt sind.

  1. Für alle gilt .
  2. Für , , gilt .
  3. Die Elemente von bilden eine Überdeckung von , d.h. jedes Element von liegt in mindestens einem Element von .


Definition:Stirling-Zahlen zweiter Art

Die Anzahl der Partitionen einer -elementigen Menge in Blöcke heißt Stirling-Zahl zweiter Art. Sie wird mit bezeichnet.



Definition:Bellzahl

Die Anzahl der Partitionen einer -elementigen Menge heißt Bellzahl und wird mit bezeichnet.



Definition:Ungerichteter Graph

Ein ungerichteter Graph auf einer Menge (die die Eckpunktmenge des Graphen heißt) besteht aus einer gewissen Auswahl an zweielementigen Teilmengen (die die Kantenmenge des Graphen heißt) von .



Definition:Nachbarschaft (Graph)

Zu einem Punkt in einem Graphen nennt man

die Nachbarschaft von .



Definition:Vollständiger Graph

Ein Graph auf einer Menge heißt vollständig, wenn je zwei Punkte miteinander durch eine Kante verbunden sind.



Definition:Kantenfreier Graph

Ein Graph heißt kantenfrei, wenn die Kantenmenge leer ist.



Definition:Linearer Graph

Ein Graph heißt linear, wenn es eine Auflistung aller Knoten derart gibt, dass die Kantenmenge gleich , , ist.



Definition:Sterngraph

Ein Graph heißt Sterngraph, wenn es in ihm einen Knoten (das Zentrum) gibt, der mit allen anderen Knoten verbunden ist und dies die einzigen Kanten des Graphen sind.



Definition:Grad (Graphentheorie)

Zu einem Punkt in einem Graphen nennt man die Anzahl der Kanten, die an anliegen, den Grad von . Er wird mit bezeichnet.



Definition:Isolierter Punkt

Ein Punkt eines Graphen mit Grad heißt isoliert.



Definition:Blatt

Ein Punkt eines Graphen mit Grad heißt Blatt.



Definition:Minimalgrad

Zu einem Graphen nennt man

den Minimalgrad des Graphen.



Definition:Maximalgrad

Zu einem Graphen nennt man

den Maximalgrad des Graphen.



Definition:Vollständiger Graph

Ein Graph auf einer Menge heißt -regulär, wenn jeder Punkt den Grad besitzt.



Definition:Untergraph

Ein Graph heißt Untergraph eines Graphen , wenn , und die Kanten aus nur Bezug auf Punkte aus nehmen.



Definition:Voller Untergraph

Ein Untergraph heißt voll, wenn jede Kante aus , die Punkte aus verbindet, auch eine Kante in ist.



Definition:Homomorphismus von Graphen

Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus stets folgt, heißt Graphhomomorphismus.



Definition:Isomorphismus von Graphen

Es seien und Graphen. Ein Graphhomomorphismus heißt Isomorphismus, wenn es einen Graphhomomorphismus

derart gibt, dass

und

gilt.



Definition:Isomorphe Graphen

Zwei Graphen und heißen isomorph, wenn es einen Graphisomorphismus gibt.



Definition:Schwacher Graphhomomorphismus

Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus entweder oder aber folgt, heißt schwacher Graphhomomorphismus.



Definition:Graphautomorphismus

Es sei ein Graph. Ein Isomorphismus heißt Automorphismus.



Definition:Automorphismengruppe (Graph)

Zu einem Graphen nennt man die Gruppe aller Automorphismen

die Automorphismengruppe von . Sie wird mit bezeichnet.



Definition:Homogener Graph

Ein Graph heißt homogen, wenn es zu je zwei Knotenpunkten einen Automorphismus

mit

gibt.



Definition:Starrer Graph

Ein Graph heißt starr, wenn die Automorphismengruppe von trivial ist.



Definition:Komplementärer Graph

Zu einem Graphen nennt man den Graphen den komplementären Graphen (oder Komplementärgraph). Er wird mit bezeichnet.



Definition:Restgraph

Zu einem Graphen und einer Teilmenge der Kantenmenge versteht man unter denjenigen Graphen, dessen Punktemenge ist und dessen Kantenmenge aus besteht.



Definition:Kantengraph

Es sei ein Graph. Man nennt denjenigen Graphen, dessen Knotenmenge die Kantenmenge von ist und bei dem zwei Knoten und (also Kanten aus ) genau dann durch eine Kante verbunden werden, wenn und einen gemeinsamen Punkt in besitzen, den Kantengraphen zu .



Definition:Bildgraph

Es sei ein Graph, eine Menge und eine Abbildung. Unter dem Bildgraphen zu versteht man denjenigen Graphen, dessen Knotenmenge durch das Bild von und dessen Kantenmenge durch

gegeben ist.



Definition:Quotientengraph

Es sei ein Graph und sei eine Äquivalenzrelation auf . Dann nennt man die Quotientenmenge , versehen mit der Bildgraphstruktur zur kanonischen Abbildung

den Quotientengraphen zu . Er wird mit bezeichnet.



Definition:Kontraktionsgraph

Es sei ein Graph und eine Kante, die die Knotenpunkte und verbindet. Man nennt denjenigen Graphen mit der Knotenmenge , bei der und miteinander identifiziert werden, und bei dem die Kantenmenge aus den Bildkanten zur Kontraktionsabbildung besteht, den Kontraktionsgraphen zu . Er wird mit bezeichnet.



Definition:Disjunkte Vereinigung (Graphen)

Zu zwei Graphen und mit disjunkten Knotenmengen und nennt man den Graphen mit der Knotenmenge und der Kantenmenge die disjunkte Vereinigung der Graphen.



Definition:Kartesisches Produkt (Graph)

Zu zwei Graphen und nennt man den Graphen mit Knotenmenge , wobei zwischen zwei Knoten und genau dann eine Kante besteht, wenn entweder und oder und gilt, das kartesische Produkt der Graphen.



Definition:Weg

Ein Weg in einem Graphen ist eine Folge von Knoten derart, dass für alle eine Kante ist.



Definition:Zusammenhängender Graph

Ein Graph heißt zusammenhängend, wenn es zu je zwei Punkten einen Weg gibt, der und verbindet.



Definition:Zusammenhangskomponente (Graph)

Zu einem Punkt in einem Graphen nennt man

die Zusammenhangskomponente von .



Definition:Weglänge (Graph)

Unter der Länge eines Weges in einem Graphen versteht man die Anzahl seiner Kanten.



Definition:Abstand (Graph)

Zu zwei Knotenpunkten und in einem zusammenhängenden Graphen versteht man unter dem Abstand die minimale Länge eines verbindenden Weges von nach .



Definition:Durchmesser (Graph)

Unter dem Durchmesser eines zusammenhängenden Graphen versteht man das Maximum über alle Abstände zu .



Definition:Radius (Graph)

Unter dem Radius eines zusammenhängenden Graphen versteht man den Ausdruck



Definition:Exzentrizität (Graph)

Zu einem Knotenpunkt eines zusammenhängenden Graphen nennt man

die Exzentrizität von .



Definition:Zyklus

Ein Weg in einem Graphen heißt Zyklus, wenn ist.



Definition:Kreis (Graph)

Ein Kreis in einem Graphen ist ein Zyklus der Länge ohne Wiederholungen.



Definition:Rundgang

Ein Graph heißt Rundgang, wenn es in ihm einen Kreis gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.



Definition:Taille

Die Taille eines zyklischen Graphen ist die kürzeste Länge eines Kreises in .



Definition:Umfang

Der Umfang eines zyklischen Graphen ist die längste Länge eines Kreises in .



Definition:Wald

Ein Graph ohne Kreis heißt Wald



Definition:Baum

Ein zusammenhängender Wald heißt Baum.



Definition:Aufspannender Baum

Ein Untergraph eines Graphen heißt aufspannender Baum von , wenn ein Baum mit der vollen Knotenmenge ist.



Definition:Matroid

Zu einer endlichen Menge heißt eine Teilmenge

ein Matroid, wenn folgende Bedingungen erfüllt sind.

  1. Es ist .
  2. Aus und folgt .
  3. Wenn mit

    so gibt es ein derart, dass .



Definition:Basis (Matroid)

In einem Matroid auf einer Menge nennt man die maximalen Mengen aus Basen.



Definition:Rang (Matroid)

In einem Matroid auf einer Menge nennt man die gemeinsame Anzahl der Elemente in einer jeden Basis von den Rang des Matroids.



Definition:Aufspannender Wald

Ein Untergraph eines Graphen heißt aufspannender Wald von , wenn ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von übereinstimmen.



Definition:Multigraph

Ein Multigraph besteht aus einer Knotenmenge , einer Kantenmenge und einer Abbildung



Definition:Adjazenzmatrix

Zu einem Graphen versteht man unter der Adjazenzmatrix diejenige - Matrix, deren Einträge durch

gegeben sind.



Definition:Charakteristisches Polynom (Graph)

Zu einem Graphen nennt man das charakteristische Polynom der Adjazenzmatrix das charakteristische Polynom von .



Definition:Inzidenzmatrix

Es sei ein Graph. Unter der Inzidenzmatrix zu verstehen wir die - Matrix, deren Einträge durch

gegeben sind.



Definition:Gradmatrix

Es sei ein Graph. Unter der Gradmatrix zu verstehen wir die - Diagonalmatrix, deren Diagonaleintrag an der Stelle durch den Grad im Knotenpunkt gegeben ist.



Definition:Laplace-Matrix

Zu einem Multigraphen versteht man unter der Laplace-Matrix die Differenz

aus Gradmatrix und Adjazenzmatrix .



Definition:Bipartiter Graph

Ein Graph heißt bipartit, wenn es eine disjunkte Zerlegung

derart gibt, dass es nur Kanten zwischen und gibt.



Definition:Vollständiger bipartiter Graph

Der vollständige bipartite Graph ist derjenige Graph, dessen Knotenmenge aus der disjunkten Vereinigung einer -elementigen Menge und einer -elementigen Menge besteht und dessen Kantenmenge durch

gegeben ist.



Definition:Paarung (Graph)

Eine Paarung in einem Graphen ist eine Kantenmenge , wobei die Kanten aus zueinander disjunkt sind.



Definition:Abgedeckter Knotenpunkt

Wir sagen, dass eine Paarung in einem Graphen einen Knotenpunkt abdeckt, wenn es eine Kante aus gibt, zu der gehört.



Definition:Paarung (Teilknotenmenge)

Eine Paarung in einem Graphen heißt Paarung für eine Teilmenge , wenn jeder Knoten aus von einer Kante aus abgedeckt wird.



Definition:Perfekte Paarung

Eine Paarung in einem Graphen heißt perfekt, wenn die Kanten der Paarung jeden Knoten des Graphen abdecken.



Definition:Maximale Paarung

Eine Paarung in einem Graphen heißt maximal, wenn jedes mit keine Paarung ist.



Definition:Optimale Paarung

Eine Paarung in einem Graphen heißt optimal, wenn sie unter allen Paarungen von die größtmögliche Anzahl von Kanten enthält.



Definition:Paarungszahl

Die Paarungszahl eines bipartiten Graphen ist die größtmögliche Anzahl von Kanten in einer Paarung von .



Definition:Paarungsbedingung

Es sei ein bipartiter Graph mit einer Bipartition und sei . Man sagt, dass die Paarungsbedingung erfüllt, wenn für jede Teilmenge die Beziehung gilt.



Definition:Alternierender Weg

Es sei ein Graph und eine Paarung. Man nennt einen Weg in alternierend (bezüglich der gegebenen Paarung), wenn er abwechselnd Kanten aus und aus besitzt.



Definition:Knotenüberdeckung

Es sei ein Graph. Eine Teilmenge heißt Knotenüberdeckung von , wenn jede Kante mindestens einen Knoten aus trifft.



Definition:Minimale Knotenüberdeckung

Es sei ein Graph. Eine Knotenüberdeckung von heißt minimal, wenn zu jedem keine Knotenüberdeckung ist.



Definition:Optimale Knotenüberdeckung

Es sei ein Graph. Eine Knotenüberdeckung von heißt optimal, wenn es keine Knotenüberdeckung von mit weniger als Elementen gibt.



Definition:Knotenüberdeckungszahl

Es sei ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von heißt Knotenüberdeckungszahl von .



Definition:Hamiltonkreis

Ein Kreis in einem Graphen heißt Hamiltonkreis, wenn in ihm jeder Knotenpunkt vorkommt.



Definition:Hamiltonscher Graph

Ein Graph heißt hamiltonsch, wenn es in ihm einen Hamiltonkreis gibt.



Definition:Eulerscher Kantenzug

Es sei ein Graph. Ein Kantenzug heißt eulersch, wenn in ihm jede Kante aus genau einmal vorkommt.



Definition:Eulerscher Graph

Ein Graph heißt eulersch, wenn in ihm ein geschlossener Eulerzug existiert.



Definition:Kantendisjunkte Untergraphen

Zwei Untergraphen und in einem Graphen heißen kantendisjunkt, wenn ist.



Definition:Färbung

Es sei ein Graph. Eine Abbildung

in eine Menge heißt Färbung des Graphen.



Definition:Zulässige Färbung

Es sei ein Graph. Eine Färbung

heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.



Definition:Chromatische Zahl

Zu einem Graphen nennt man die minimale Anzahl an Farben, die man für eine zulässige Färbung benötigt, die chromatische Zahl des Graphen. Sie wird mit bezeichnet.



Definition:Chromatisches Polynom

Zu einem Graphen versteht man unter dem chromatischen Polynom die Funktion, die durch

gegeben ist.



Definition:Geometrische Realisierung eines Graphen

Es sei ein Graph. Eine (überschneidungsfreie) geometrische Realisierung von im besteht aus folgenden Daten.

  1. Eine injektive Abbildung

    zu jedem Knotenpunkt gibt es also einen Punkt und verschiedene Knotenpunkte besitzen verschiedene Realisierungen .

  2. Zu jeder Kante eine injektive stetige Abbildung

    mit und .

  3. Für verschiedene Kanten ist


Definition:Planarer Graph

Ein Graph heißt planar, wenn er eine geometrische Realisierung im besitzt.