Kantenzahl

Als Kantenzahl  bezeichnet man in der Graphentheorie die Anzahl der Kanten eines Graphen.

Ist  der betrachtete Graph, so notiert man diese Zahl in der Regel mit  (oder kurz , falls klar ist, um welchen Graph es sich handelt). Alternativ schreibt man auch .

Definition 
Bei ungerichteten Graphen ist die Kantenzahl  eines gegebenen Graphen  die Anzahl seiner Kanten, bzw. die Summe der Vielfachheiten der einzelnen Kanten, wenn es sich um einen Graphen mit Mehrfachkanten handelt.

Man kann sie auch als Mächtigkeit  der Kantenmenge  sehen.

Eigenschaften 
 Es gilt: . Dabei ist  die Cliquenzahl von ; die Anzahl der Knoten in der größten Clique von . Gleichheit tritt bei vollständigen Graphen ein.
 Außerdem gilt
. ist dabei eine stabile Menge von  und  der Grad des Knoten . Tritt Gleichheit ein, so ist  eine maximale stabile Menge des Graphen .

Berechnung aus einer Adjazenzmatrix 
Ist die Adjazenzmatrix eines Graphen gegeben, kann man daraus sehr leicht die Kantenzahl dieses Graphen bestimmen.

Eine Adjazenzmatrix besitzt für eine Kante, die die Knoten  und  verbindet, einen Eintrag in der -ten Zeile und der -ten Spalte. Ist der Graph ungerichtet, steht die 1 auch in der -ten Zeile und der -ten Spalte.

Um die Kantenzahl zu berechnen, muss man nur alle Einträge addieren und noch durch 2 teilen. Dieses Verfahren funktioniert auch für Graphen mit Mehrfachkanten.

Berechnung bei verschiedenen Klassen von Graphen 
Im folgenden Abschnitt wird immer von einfachen Graphen ausgegangen, also ungerichteten Graphen ohne Mehrfachkanten.

Vollständige Graphen 

Die Kantenzahl  des vollständigen Graphen mit  Knoten  entspricht
,
also der Dreieckszahl .

Das ist daran zu sehen, dass jede Kante durch zwei Knoten definiert wird und es  Möglichkeiten gibt zwei Knoten auszuwählen.

Bäume 
Bäume  mit  Knoten haben nach der Cayley-Formel  Kanten. Sie ist ein Sonderfall des Eulerschen Polyedersatzes für planare Graphen (vgl. planare Graphen). Zu der Graphenklasse der Bäume zählen auch lineare Graphen und Sterngraphen. Ein Sterngraph ist ein Graph, der einen zentralen Knoten besitzt, der mit allen anderen Knoten verbunden ist. Die anderen Knoten besitzen nur diesen einen Nachbarn.

Planare Graphen 
Die Kantenzahl eines planaren Graphen lässt sich berechnen mithilfe des Eulerschen Polyedersatzes für planare Graphen
.
Dabei gilt  und  ist die Gebietszahl.

Löst man die Gleichung nach  auf, erhält man
.

Maximal planare Graphen 

Ein maximal planarer Graph ist ein Graph, dem keine weiteren Kanten hinzugefügt werden können. Besitzt er mindestens 3 Knoten, so ist er ein Dreiecksgraph und jedes seiner Gebiete ist von 3 Kanten umgeben.

Die Kantenzahl eines maximalen planaren Graphen mit mindestens 3 Knoten ist .

Reguläre Graphen 
Bei einem regulären Graphen mit Grad  und  Knoten ist die Kantenzahl
.

Das kommt daher, dass von jedem Knoten  Kanten ausgehen; dabei zählt man allerdings jede Kante zweimal und muss deshalb durch 2 teilen.

Gegebener Durchschnittsgrad 
Bei gegebenem Durchschnittsgrad  und Knotenzahl  kann man die Kantenzahl folgendermaßen berechnen
.

Durch die Multiplikation mit  steht im Zähler die Anzahl aller Kanten; dabei ist allerdings jede doppelt gezählt, deshalb wird noch durch 2 geteilt.

Diese Formel ist eine Verallgemeinerung der Formel für reguläre Graphen.

Bipartite Graphen 
Handelt es sich bei einem gegebenen Graphen  um einen bipartiten Graphen, dessen Knotenmenge  sich in zwei disjunkte Teilmengen  und  aufteilen lässt, dann lässt sich nur ein Maximum für die Kantenzahl angeben.

Jeder Knoten  kann mit maximal  verschiedenen Knoten  durch eine Kante verbunden sein.

Also gibt es maximal  Kanten.

Ist  ein vollständig bipartiter Graph, dann ist die Kantenzahl maximal und erreicht genau .

Allgemein beträgt die maximale Kantenzahl eines k-partiten Graphen  mit den  disjunkten Teilmengen 

Dabei steht  für die -te Dreieckszahl.
Die Formel kann man herleiten, indem man überlegt, wie viele Kanten zu einem vollständigen Graphen noch fehlen.

Da jeder -knotenfärbbare Graph auch -partit ist, kann man bei -knotenfärbbaren Graphen auch die oben genannte Formel anwenden.

Gittergraphen 
Ein Gittergraph  mit  Knoten lässt sich als Rechteck darstellen, in dem alle Kanten die gleiche Länge haben.

Die Kantenzahl kann man berechnen, indem man erst die äußeren Kanten zählt und dann die inneren addiert.

Es gibt

äußere Kanten und

innere Kanten.
Zusammen ergibt das

Kanten.

Alternativ kann man die Anzahl der senkrechten und die Anzahl der waagerechten Kanten addieren und erhält

Kanten.

Leitergraphen 

Ein Leitergraph besitzt die Struktur einer Leiter. Er besteht aus zwei linearen Graphen gleicher Länge (die Holme), wobei je zwei einander entsprechende Knoten durch eine Kante (die Sprossen) miteinander verbunden sind.

Der Leitergraph  mit  Knoten besitzt  Kanten für die Holme und  Kanten für die Sprossen, also insgesamt

Kanten.

Radgraphen 
Ein Radgraph besteht aus einem Kreisgraph , dem ein weiterer mit allen Knoten verbundener Knoten hinzugefügt wurde. Der Radgraph  besitzt  Knoten.

Die Kantenzahl von  berechnet sich durch
.

Graphen, die durch Operationen auseinander hervorgehen

Duale Graphen 
Zu einem gegebenen Graphen  entsteht der duale Graph , indem jedes Gebiet von  durch einen Knoten von  ersetzt wird. Außerdem werden Kanten, die Gebiete von  trennten, zu Kanten, die die neuen Knoten von  verbinden.

Die Kantenzahl bleibt bei diesem Verfahren gleich, also gilt
.

Isomorphe Graphen 
Dass zwei Graphen isomorph zueinander sind, bedeutet, dass sie strukturell gleich sind und sich nur in der Bezeichnung der Knoten und Kanten unterscheiden.

Deshalb gilt für zwei zueinander isomorphe Graphen  und 
.

Komplementgraphen 

Der Komplementgraph eines Graphen  ist der Graph , der die gleiche Knotenmenge  wie  besitzt, aber alle Kanten, die  nicht hat.

Die Kantenzahl des Komplementgraphen von  kann abhängig von der Kantenzahl von  berechnet werden.

Dabei steht  für die Knotenzahl von . Die Formel leitet sich her, da die Vereinigungsmenge der beiden Knotenmengen einen vollständigen Graph bildet.

Kantengraphen 
Der Kantengraph  eines Graphen  entsteht, indem jede Kante von  zu einem Knoten von  wird. Dann werden die Knoten von  durch eine Kante verbunden, die in  benachbart waren.

Die Formel für die Kantenzahl von  lässt sich herleiten durch die Überlegung, dass jeder Knoten  von  ersetzt wird durch  Kanten, die die an Stelle der angrenzenden Kanten entstandenen Knoten verbinden.

Also lautet sie
.

Siehe auch 
 Knotenzahl
 Kante (Graphentheorie)

Grundbegriff (Graphentheorie)