Grad (Graphentheorie) - LinkFang.de





Grad (Graphentheorie)


Grad (auch Knotengrad oder Valenz) ist ein grundlegender Begriff der Graphentheorie, einem Teilgebiet der Mathematik. Er beschreibt Eigenschaften eines Knotens, die sich durch mit ihm verbundene Kanten beschreiben lassen.

Der Grad [math]d_G(v)[/math] in einem Graphen ist die Anzahl der Kanten, die den Knoten [math]v[/math] mit anderen Knoten verbinden. Eine Schlinge wird dabei doppelt gezählt. Oft wird auch die Notation [math]\deg_G(v)[/math] (engl. degree) verwendet

Falls klar ist, um welchen Graphen es sich handelt, lässt man den Index [math]G[/math] bei [math]d[/math], [math]d^+[/math] und [math]d^-[/math] auch oft weg.

Definition

Ungerichtete Graphen

In einem ungerichteten Graph ist [math]d_G(v)[/math] in

Den kleinsten Grad eines Knotens in [math] G [/math] nennt man den Minimalgrad von [math] G [/math] und bezeichnet diesen mit [math] \delta (G)[/math], den größten Grad eines Knotens in [math] G [/math] nennt man den Maximalgrad von [math] G [/math], dieser wird meist mit [math] \Delta ( G ) [/math] bezeichnet. Der Durchschnitt aller Knotengrade von [math] G[/math] wird Durchschnittsgrad genannt und mit [math] d(G) [/math] bezeichnet.

Gerichtete Graphen

In gerichteten Graphen wird unterschieden, ob eine Kante an einem Knoten beginnt oder endet. Mit [math]d_G^-(v)[/math] bezeichnet man den Eingangsgrad des Knotens v in einem gerichteten Graphen G und mit [math]d_G^+(v)[/math] dessen Ausgangsgrad.

Dabei ist [math]d_G^-(v)[/math] in

  • Graphen ohne Mehrfachkanten die Anzahl der Vorgänger von v,
  • Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (v, x).

und [math]d_G^+(v)[/math] in

  • Graphen ohne Mehrfachkanten die Anzahl der Nachfolger von v,
  • Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (x, v).

Einen Knoten ohne Eingangskanten ([math]d_G^-(v)=0[/math]) nennt man Quelle, einen Knoten ohne Ausgangskanten ([math]d_G^+(v)=0[/math]) nennt man Senke.

Verwandte Begriffe

  • Man nennt einen Knoten isoliert, wenn er:
    • in einem ungerichteten Graphen: keine Nachbarn besitzt [math]d_G =0[/math].
    • in einem gerichteten Graphen: keine Vorgänger und keine Nachfolger besitzt. [math]d_G^+ = d_G^- =0[/math].
  • Ein ungerichteter Graph (bzw. Hypergraph) G heißt regulär, falls alle seine Knoten denselben Grad besitzen. Besitzen alle seine Knoten Grad k, so bezeichnet man G als k-regulär. Einen 3-regulären Graphen bezeichnet man auch als kubisch.
  • Ein gerichteter Graph G heißt regulär, falls alle seine Knoten denselben Eingangs- und Ausgangsgrad besitzen. Besitzen alle seine Knoten Eingangs- und Ausgangsgrad k, so bezeichnet man G als k-regulär.
  • Ein Hypergraph G heißt uniform, wenn alle Kanten von G die gleiche Anzahl Knoten enthalten. Enthalten alle Kanten von G genau k Knoten, so nennt man G k-uniform.

Eigenschaften

  • Stets gilt [math] \delta (G) \leq d (G) \leq \Delta (G)[/math]. Gleichheit tritt z.B. bei vollständigen Graphen ein.
  • Die Anzahl der Ecken mit ungeradem Grad ist stets gerade.

Verwendung

Der Grad gehört zu den Grundbegriffen der Graphentheorie und liefert viele wichtige Abschätzungen für Grapheneigenschaften wie z.B. die Kantenfärbungszahl

Literatur


Kategorien: Grundbegriff (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Grad (Graphentheorie) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.