imported>Dexxor: konsistent mit Artkel planarer Graph

2024-09-19T12:18:23Z

konsistent mit Artkel planarer Graph

Neue Seite

Als '''Kantenzahl ''' bezeichnet man in der [[Graphentheorie]] die [[Anzahl]] der [[Kante (Graphentheorie)|Kanten]] eines [[Graph (Graphentheorie)|Graphen]].

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

== Definition ==
Bei ungerichteten Graphen ist die Kantenzahl <math>m(G)</math> eines gegebenen Graphen <math>G = (V, E)</math> 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 (Mathematik)|Mächtigkeit]] <math>|E|</math> der Kantenmenge <math>E</math> sehen.

== Eigenschaften ==
* Es gilt: <math>m(G) \ge \Delta_{\tau(G) - 1} = \frac{\tau(G)(\tau(G) - 1)}{2}</math>. Dabei ist <math>\tau(G)</math> die [[Clique (Graphentheorie)|Cliquenzahl]] von <math>G</math>; die Anzahl der Knoten in der größten Clique von <math>G</math>. Gleichheit tritt bei [[Vollständiger Graph|vollständigen Graphen]] ein.
* Außerdem gilt
:<math>m(G) \ge \sum_{v \in U} d(v)</math>.<br /><math>U</math> ist dabei eine [[stabile Menge]] von <math>G</math> und <math>d(v)</math> der [[Grad (Graphentheorie)|Grad]] des Knoten <math>v</math>. Tritt Gleichheit ein, so ist <math>U</math> eine [[stabile Menge#Maximale stabile Menge|maximale stabile Menge]] des Graphen <math>G</math>.
* Die Summe der Knotengrade <math>\sum_{v\in V} d(v) = 2m</math> ist nach dem [[Handschlaglemma]] das Doppelte der Kantenzahl.

=== 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 <math>i</math> und <math>j</math> verbindet, einen Eintrag in der <math>i</math>-ten Zeile und der <math>j</math>-ten Spalte. Ist der Graph ungerichtet, steht die 1 auch in der <math>j</math>-ten Zeile und der <math>i</math>-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 [[Einfacher Graph|einfachen Graphen]] ausgegangen, also [[Ungerichteter Graph|ungerichteten]] Graphen ohne [[Mehrfachkante]]n.

=== Vollständige Graphen ===
[[Datei:Complete graph K5.svg|mini|Der vollständige Graph <math>K_5</math> mit 10 Kanten]]
Die Kantenzahl <math>m</math> des [[Vollständiger Graph|vollständigen Graphen]] mit <math>n</math> Knoten <math>K_n</math> entspricht
:<math>m = {n \choose 2} = \frac{n(n-1)}{2} = \Delta_{n-1}</math>,
also der [[Dreieckszahl]] <math>\Delta_{n-1}</math>.

Das ist daran zu sehen, dass jede Kante durch zwei Knoten definiert wird und es <math>{n \choose 2}</math> Möglichkeiten gibt zwei Knoten auszuwählen.

=== Bäume ===
[[Baum (Graphentheorie)|Bäume]] mit <math>n</math> Knoten haben nach der [[Cayley-Formel]] <math>m = n-1</math> Kanten. Sie ist ein Sonderfall des [[Eulerscher Polyedersatz#Der Eulersche Polyedersatz für planare Graphen|Eulerschen Polyedersatzes für planare Graphen]] (vgl. planare Graphen). Zu der Graphenklasse der Bäume zählen auch [[Linearer Graph|lineare Graphen]] und [[Sterngraph|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 [[Planarer Graph|planaren Graphen]] lässt sich berechnen mithilfe des [[Eulerscher Polyedersatz#Der Eulersche Polyedersatz für planare Graphen|Eulerschen Polyedersatzes für planare Graphen]]
:<math>n - m + f = 2</math>.
Dabei gilt <math>n = |V|, m = |E|</math> und <math>f</math> ist die Anzahl der [[Fläche (Graphentheorie)|Flächen]].

Löst man die Gleichung nach <math>m</math> auf, erhält man
:<math>m = n + f - 2</math>.

=== Maximal planare Graphen ===
[[Datei:Goldner-Harary graph.svg|mini|240px|Der [[Goldner–Harary Graph]] ist ein maximal planarer Graph. Er besitzt 11 Knoten und 27 Kanten]]
Ein [[Dreiecksgraph|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 jede seiner Flächen ist von 3 Kanten umgeben.

Die Kantenzahl eines maximalen planaren Graphen mit mindestens 3 Knoten ist <math>m = 3n - 6</math>.

=== Reguläre Graphen ===
Bei einem [[Regulärer Graph|regulären Graphen]] mit Grad <math>k</math> und <math>n</math> Knoten ist die Kantenzahl
:<math>m = \frac{n \cdot k}{2}</math>.

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

=== Gegebener Durchschnittsgrad ===
Bei gegebenem [[Durchschnittsgrad]] <math>d(G)</math> und [[Knotenzahl]] <math>n</math> kann man die Kantenzahl folgendermaßen berechnen
:<math>m = \frac{d(G) \cdot n(G)}{2}</math>.

Durch die Multiplikation mit <math>n</math> 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 <math>G</math> um einen [[Bipartiter Graph|bipartiten Graphen]], dessen Knotenmenge <math>V</math> sich in zwei [[disjunkt]]e [[Teilmenge]]n <math>V_1</math> und <math>V_2</math> aufteilen lässt, dann lässt sich nur ein Maximum für die Kantenzahl angeben.

Jeder Knoten <math>v \in V_1</math> kann mit maximal <math>|V_2|</math> verschiedenen Knoten <math>w \in V_2</math> durch eine Kante verbunden sein.

Also gibt es maximal <math>m = |V_1| \cdot |V_2|</math> Kanten.

Ist <math>G</math> ein [[vollständig bipartiter Graph]], dann ist die Kantenzahl maximal und erreicht genau <math>|V_1| \cdot |V_2|</math>.

Allgemein beträgt die maximale Kantenzahl eines [[K-partiter Graph|k-partiten Graphen]] <math>G = (V, E)</math> mit den <math>k</math> disjunkten Teilmengen <math>V_1, \dotsc, V_k</math>
:<math>\begin{align}
m & = \Delta_{|V| - 1} - \Delta_{|V_1| - 1} - \dotsb - \Delta_{|V_k| - 1}\\
& = \left( \frac{|V|(|V|-1)}{2} \right) - \left( \frac{|V_1|(|V_1| - 1)}{2} \right) - \left( \frac{|V_2|(|V_2| - 1)}{2} \right) - \dotsb - \left( \frac{|V_k|(|V_k| - 1)}{2} \right)\\
& = \frac{(|V|^2 - |V|) - (|V_1|^2 - |V_1|) - (|V_2|^2 - |V_2|) - \dotsb - (|V_k|^2 - |V_k|)}{2}\\
& = \frac{|V|^2 - |V| - |V_1|^2 + |V_1| - |V_2|^2 + |V_2| - \dotsb - |V_k|^2 + |V_k|}{2}\\
& = \frac{|V|^2 - |V_1|^2 - |V_2|^2 - \dotsb - |V_k|^2 - |V| + |V_1| + |V_2| + \dotsb + |V_k|}{2}\\
& = \frac{|V|^2 - |V_1|^2 - |V_2|^2 - \dotsb - |V_k|^2}{2}
\end{align}</math>

Dabei steht <math>\Delta_k</math> für die <math>k</math>-te [[Dreieckszahl]].
Die Formel kann man herleiten, indem man überlegt, wie viele Kanten zu einem [[Vollständiger Graph|vollständigen Graphen]] noch fehlen.

Da jeder <math>k</math>-[[Färbung (Graphentheorie)|knotenfärbbare]] Graph auch <math>k</math>-partit ist, kann man bei <math>k</math>-knotenfärbbaren Graphen auch die oben genannte Formel anwenden.

=== Gittergraphen ===
Ein [[Gittergraph]] <math>G_{i, j}</math> mit <math>n = i \cdot j</math> 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
:<math>\begin{align}
m_1 & = (2i - 2) + (2j - 2)\\
& = 2i + 2j - 4
\end{align} </math>
äußere Kanten und
:<math>\begin{align}
m_2 & = [(i - 2)(j - 1)] + [(i - 1)(j - 2)]\\
& = i \cdot j - i - 2j + 2 + i \cdot j - j - 2i + 2\\
& = 2ij - 3i - 3j + 4
\end{align} </math>
innere Kanten.
Zusammen ergibt das
:<math>\begin{align}
m & = m_1 + m_2\\
& = (2i + 2j - 4) + (2ij - 3i - 3j + 4)\\
& = 2ij - i - j
\end{align}</math>
Kanten.

Alternativ kann man die Anzahl der senkrechten und die Anzahl der waagerechten Kanten addieren und erhält
:<math>\begin{align}
(i-1)\cdot j + (j-1)\cdot i = 2ij-i-j
\end{align} </math>
Kanten.

=== Leitergraphen ===
[[Datei:Ladder graphs.svg|mini|hochkant=1.5|Die Leitergraphen <math>L_1</math>, <math>L_2</math>, <math>L_3</math>, <math>L_4</math> und <math>L_5</math>]]
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 <math>L_n</math> mit <math>2n</math> Knoten besitzt <math>2n - 2</math> Kanten für die Holme und <math>n</math> Kanten für die Sprossen, also insgesamt
:<math>m = 2n - 2 + n = 3n - 2</math>
Kanten.

=== Radgraphen ===
Ein Radgraph besteht aus einem [[Kreisgraph]] <math>C_n</math>, dem ein weiterer mit allen Knoten verbundener Knoten hinzugefügt wurde. Der Radgraph <math>W_n</math> besitzt <math>n + 1</math> Knoten.

Die Kantenzahl von <math>W_n</math> berechnet sich durch
:<math>w = 2n</math>.

== Graphen, die durch Operationen auseinander hervorgehen ==
=== Duale Graphen ===
Zu einem gegebenen Graphen <math>G = (V, E)</math> entsteht der [[Dualität (Mathematik)#Geometrisch dualer Graph|duale Graph]] <math>G' = (V', E')</math>, indem jede Fläche von <math>G</math> durch einen Knoten von <math>G'</math> ersetzt wird. Außerdem werden Kanten, die Flächen von <math>G</math> trennten, zu Kanten, die die neuen Knoten von <math>G'</math> verbinden.

Die Kantenzahl bleibt bei diesem Verfahren gleich, also gilt
:<math>m(G) = m(G')</math>.

=== 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 <math>G</math> und <math>G'</math>
:<math>m(G) = m(G')</math>.

=== Komplementgraphen ===
[[Datei:Petersen graph complement.svg|miniatur|Der [[Petersen-Graph]] (links) und dessen Komplementgraph (rechts)]]
Der [[Komplementgraph]] eines Graphen <math>G = (V, E)</math> ist der Graph <math>G' = (V', E')</math>, der die gleiche Knotenmenge <math>V'</math> wie <math>G</math> besitzt, aber alle Kanten, die <math>G</math> nicht hat.

Die Kantenzahl des Komplementgraphen von <math>G</math> kann abhängig von der Kantenzahl von <math>G</math> berechnet werden.
:<math>\begin{align}
m(G') & = \Delta_{n(G) - 1} - m(G)\\
& = \frac{n(G)(n(G) - 1)}{2} - m(G)
\end{align}</math>

Dabei steht <math>n(G)</math> für die [[Knotenzahl]] von <math>G</math>. Die Formel leitet sich her, da die [[Vereinigungsmenge]] der beiden Knotenmengen einen vollständigen Graph bildet.

=== Kantengraphen ===
Der [[Kantengraph]] <math>L(G) = (V', E')</math> eines Graphen <math>G = (V, E)</math> entsteht, indem jede Kante von <math>G</math> zu einem Knoten von <math>L(G)</math> wird. Dann werden die Knoten von <math>L(G)</math> durch eine Kante verbunden, die in <math>G</math> benachbart waren.

Die Formel für die Kantenzahl von <math>L(G)</math> lässt sich herleiten durch die Überlegung, dass jeder Knoten <math>v \in V</math> von <math>G</math> ersetzt wird durch <math>\tbinom{d(v)}{2}=\Delta_{d(v) - 1}</math> Kanten, die die an Stelle der angrenzenden Kanten entstandenen Knoten verbinden.

Also lautet sie
:<math>m(L(G)) = \sum_{v \in V} \binom{d(v)}{2} = \sum_{v \in V} \Delta_{d(v)-1}</math>.

== Siehe auch ==
* [[Knotenzahl]]
* [[Kante (Graphentheorie)]]

[[Kategorie:Grundbegriff (Graphentheorie)]]

Kantenzahl - Versionsgeschichte

imported>Dexxor: konsistent mit Artkel planarer Graph