Kantenzahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Als Kantenzahl bezeichnet man in der Graphentheorie die Zahl 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

  • 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 bei verschiedenen Klassen von Graphen[Bearbeiten | Quelltext bearbeiten]

Im folgenden Abschnitt wird immer von einfachen Graphen ausgegangen, also ungerichteten Graphen ohne Mehrfachkanten.

Vollständige Graphen[Bearbeiten | Quelltext bearbeiten]

Der vollständige Graph mit 10 Kanten

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.

Planare Graphen[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Der Goldner–Harary Graph ist ein maximal planarer Graph. Er besitzt 11 Knoten und 27 Kanten

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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 Teilmengengen

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[Bearbeiten | Quelltext bearbeiten]

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.

Leitergraphen[Bearbeiten | Quelltext bearbeiten]

Die Leitergraphen , , , und

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.

Sterngraphen[Bearbeiten | Quelltext bearbeiten]

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. Die Kantenzahl eines Sterngraphen mit Knoten ist also .

Radgraphen[Bearbeiten | Quelltext bearbeiten]

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

Die Kantenzahl von berechbet sich durch

.

Lineare Graphen[Bearbeiten | Quelltext bearbeiten]

Da lineare Graphen nur aus einem Weg bestehen, ist die Kantenzahl eines linearen Graphen mit Knoten .

Berechnung aus einer Adjazenzmatrix[Bearbeiten | Quelltext bearbeiten]

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.

Graphen, die durch Operationen auseinander hervorgehen[Bearbeiten | Quelltext bearbeiten]

Duale Graphen[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Der Petersen-Graph (links) und dessen Komplementgraph (rechts)

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]