www.wikidata.de-de.nina.az

Trenner Graphentheorie Trenner sind in der Graphentheorie besondere Teilmengen von Knoten und Kanten eines Graphen bei d

Trenner (Graphentheorie)

Trenner sind in der Graphentheorie besondere Teilmengen von Knoten und Kanten eines Graphen, bei deren Entfernen aus dem Graphen bestimmte Wege im Graphen unmöglich werden.

Definition Bearbeiten

Die Menge ist ein --Trenner
Der Knoten ist ein Gelenkpunkt, die Kante ist eine Brücke.

Es seien ein einfacher Graph und Teilmengen der Knotenmenge .

Ein Paar , bestehend aus einer Knotenmenge und einer Kantenmenge , heißt --Trenner oder --Separator des Graphen, wenn jeder --Weg wenigstens einen Knoten aus oder eine Kante aus enthält. Man sagt dann auch, dass die Knotenmengen und trennt.

Sind und einelementig, so spricht man auch von der Trennung der Knoten und .

Ein Paar trennt den Graphen genau dann, wenn mindestens zwei Knoten aus trennt.

Äquivalente Definition Bearbeiten

Teilweise wird in der Literatur ein --Trenner für einen Graphen auch als eine Menge von Knoten und Kanten definiert, so dass jeder --Weg mindestens ein Element aus enthält. Die weitergehenden Definitionen erfolgen analog zu den oberen.

Spezialfälle Bearbeiten

Artikulation Bearbeiten

Ist ein Knoten, der zwei Knoten trennt, die zur selben Zusammenhangskomponente des Graphen gehören, so nennt man eine Artikulation, einen Gelenkpunkt oder einen Schnittknoten des Graphen. Einem Gelenkpunkt entspricht also ein Trenner mit und .

Besitzt ein zusammenhängender Graph einen Gelenkpunkt, so ist seine Knotenzusammenhangszahl gleich 1 und er wird als separabel bezeichnet.

Brücke Bearbeiten

Ist eine Kante, die ihre beiden Endknoten trennt, so nennt man eine Brücke. Einer Brücke entspricht also ein Trenner mit und . Äquivalent dazu ist, dass in keinem Kreis des Graphen liegt.

Besitzt ein zusammenhängender Graph eine Brücke, so ist seine Kantenzusammenhangszahl gleich 1.

Verwendung Bearbeiten

Trenner gehören zu den Grundbegriffen der Graphentheorie. Sie werden beispielsweise verwendet, um die Grapheigenschaften k-Zusammenhang und Kantenzusammenhang zu definieren. In diesen beiden Fällen interessieren Trenner, die nur aus Knoten bzw. nur aus Kanten bestehen.

Literatur Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Trenner sind in der Graphentheorie besondere Teilmengen von Knoten und Kanten eines Graphen bei deren Entfernen aus dem Graphen bestimmte Wege im Graphen unmoglich werden Inhaltsverzeichnis 1 Definition 1 1 Aquivalente Definition 2 Spezialfalle 2 1 Artikulation 2 2 Brucke 3 Verwendung 4 LiteraturDefinition Bearbeiten nbsp Die Menge S displaystyle S nbsp ist ein A displaystyle A nbsp B displaystyle B nbsp Trenner nbsp Der Knoten a displaystyle a nbsp ist ein Gelenkpunkt die Kante e displaystyle e nbsp ist eine Brucke Es seien G V E displaystyle G V E nbsp ein einfacher Graph und A B V displaystyle A B subset V nbsp Teilmengen der Knotenmenge V displaystyle V nbsp Ein Paar Z X Y displaystyle Z X Y nbsp bestehend aus einer Knotenmenge X V displaystyle X subseteq V nbsp und einer Kantenmenge Y E displaystyle Y subseteq E nbsp heisst A displaystyle A nbsp B displaystyle B nbsp Trenner oder A displaystyle A nbsp B displaystyle B nbsp Separator des Graphen wenn jeder A displaystyle A nbsp B displaystyle B nbsp Weg wenigstens einen Knoten aus X displaystyle X nbsp oder eine Kante aus Y displaystyle Y nbsp enthalt Man sagt dann auch dass Z displaystyle Z nbsp die Knotenmengen A displaystyle A nbsp und B displaystyle B nbsp trennt Sind A a displaystyle A a nbsp und B b displaystyle B b nbsp einelementig so spricht man auch von der Trennung der Knoten a displaystyle a nbsp und b displaystyle b nbsp Ein Paar Z X Y displaystyle Z X Y nbsp trennt den Graphen G displaystyle G nbsp genau dann wenn Z displaystyle Z nbsp mindestens zwei Knoten aus G displaystyle G nbsp trennt Aquivalente Definition Bearbeiten Teilweise wird in der Literatur ein A displaystyle A nbsp B displaystyle B nbsp Trenner fur einen Graphen G V E displaystyle G V E nbsp auch als eine Menge X V E displaystyle X subseteq V cup E nbsp von Knoten und Kanten definiert so dass jeder A displaystyle A nbsp B displaystyle B nbsp Weg mindestens ein Element aus X displaystyle X nbsp enthalt Die weitergehenden Definitionen erfolgen analog zu den oberen Spezialfalle BearbeitenArtikulation Bearbeiten Hauptartikel Gelenkpunkt Graphentheorie Ist v V displaystyle v in V nbsp ein Knoten der zwei Knoten trennt die zur selben Zusammenhangskomponente des Graphen gehoren so nennt man v displaystyle v nbsp eine Artikulation einen Gelenkpunkt oder einen Schnittknoten des Graphen Einem Gelenkpunkt entspricht also ein Trenner Z X Y displaystyle Z X Y nbsp mit X v displaystyle X v nbsp und Y displaystyle Y emptyset nbsp Besitzt ein zusammenhangender Graph einen Gelenkpunkt so ist seine Knotenzusammenhangszahl gleich 1 und er wird als separabel bezeichnet Brucke Bearbeiten Ist e E displaystyle e in E nbsp eine Kante die ihre beiden Endknoten trennt so nennt man e displaystyle e nbsp eine Brucke Einer Brucke entspricht also ein Trenner Z X Y displaystyle Z X Y nbsp mit X displaystyle X emptyset nbsp und Y e displaystyle Y e nbsp Aquivalent dazu ist dass e displaystyle e nbsp in keinem Kreis des Graphen liegt Besitzt ein zusammenhangender Graph eine Brucke so ist seine Kantenzusammenhangszahl gleich 1 Verwendung BearbeitenTrenner gehoren zu den Grundbegriffen der Graphentheorie Sie werden beispielsweise verwendet um die Grapheigenschaften k Zusammenhang und Kantenzusammenhang zu definieren In diesen beiden Fallen interessieren Trenner die nur aus Knoten bzw nur aus Kanten bestehen Literatur BearbeitenReinhard Diestel Graphentheorie 4 Auflage Springer Berlin 2010 ISBN 978 3 642 14911 5 englisch diestel graph theory com Erstausgabe 1996 Abgerufen von https de wikipedia org w index php title Trenner Graphentheorie amp oldid 238934702