www.wikidata.de-de.nina.az

Teilgraph Der Begriff beschreibt in der Graphentheorie eine Beziehung zwischen zwei Graphen Ein anderes Wort für ist Unt

Teilgraph

Der Begriff Teilgraph beschreibt in der Graphentheorie eine Beziehung zwischen zwei Graphen. Ein anderes Wort für Teilgraph ist Untergraph. Ein Graph ist Teilgraph des Graphen , wenn alle Knoten und Kanten von auch in enthalten sind. Anders gesagt: Ein Teilgraph entsteht aus einem Graphen , indem einige Knoten und Kanten aus entfernt werden. Dabei müssen beim Entfernen eines Knotens auch alle inzidenten Kanten mit entfernt werden.

Definitionen Bearbeiten

Ein Graph heißt Teilgraph oder Untergraph oder Subgraph von , wenn seine Knotenmenge Teilmenge von und seine Kantenmenge Teilmenge von ist, also und gilt.

Umgekehrt heißt dann Supergraph oder Obergraph von .

Diese Bezeichnungen sind nicht einheitlich. Im unten angegebenen Lehrbuch von Klaus Wagner wird in dieser Allgemeinheit nur der Begriff Teilgraph verwendet und ein Untergraph als Teilgraph definiert, der zusätzlich die Eigenschaft hat, dass jede Kante aus , die zwei Knoten aus verbindet, auch eine Kante in ist. Im Lehrbuch von Claude Berge bedeutet Teilgraph zusätzlich, dass ist, und Untergraph, dass und jede Kante aus , die zwei Knoten aus verbindet, auch eine Kante in ist, der allgemeine Fall heißt dann dort Teil-Untergraph. Es empfiehlt sich daher, bei jedem Autor, die verwendete Definition zu prüfen.

Bei einem knotengewichteten bzw. kantengewichteten Graphen wird von einem Teilgraphen zudem verlangt, dass die Gewichtsfunktion von kompatibel zu der Gewichtsfunktion von sein muss, d. h. für jeden Knoten gilt bzw. für jede Kante gilt .

Gilt für einen Teilgraphen zusätzlich, dass alle Kanten zwischen den Knoten in enthält, die auch in vorhanden sind, so bezeichnet man als den durch induzierten Teilgraphen von und notiert diesen auch mit . Ein induzierter Teilgraph ist also immer eindeutig durch den Obergraphen und die gewählte Knotenmenge bestimmt. Für eine Knotenmenge bezeichnet man mit den induzierten Teilgraphen, der aus durch Weglassen der Knoten aus und aller mit diesen Knoten inzidenten Kanten entsteht, also .

Ein Teilgraph von , der alle Knoten seines Obergraphen enthält, wird aufspannender Teilgraph oder Faktor genannt.

Beispiele Bearbeiten

In der folgenden Abbildung sind die Graphen , und Teilgraphen von , aber nur und sind induzierte Teilgraphen. entsteht dabei aus durch Weglassen der Knoten und ihrer inzidenten Kanten, also ist . Gleichzeitig ist auch ein induzierter Teilgraph von .

Beispiele für Teilgraphenbeziehungen

Siehe auch Bearbeiten

Literatur Bearbeiten

Einzelnachweise Bearbeiten

  1. Klaus Wagner: Graphentheorie, BI-Hochschultaschenbücher (1969), Band 248, Kap. I, §3, Definition 4
  2. Claude Berge: Programme, Spiele, Transportnetze, Teubner-Verlag 1969, Zeiter Teil, Kap. I, Absatz 1, Seite 121
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:
Der Begriff Teilgraph beschreibt in der Graphentheorie eine Beziehung zwischen zwei Graphen Ein anderes Wort fur Teilgraph ist Untergraph Ein Graph H displaystyle H ist Teilgraph des Graphen G displaystyle G wenn alle Knoten und Kanten von H displaystyle H auch in G displaystyle G enthalten sind Anders gesagt Ein Teilgraph H displaystyle H entsteht aus einem Graphen G displaystyle G indem einige Knoten und Kanten aus G displaystyle G entfernt werden Dabei mussen beim Entfernen eines Knotens auch alle inzidenten Kanten mit entfernt werden Inhaltsverzeichnis 1 Definitionen 2 Beispiele 3 Siehe auch 4 Literatur 5 EinzelnachweiseDefinitionen BearbeitenEin Graph G 1 V 1 E 1 displaystyle G 1 V 1 E 1 nbsp heisst Teilgraph oder Untergraph oder Subgraph von G 2 V 2 E 2 displaystyle G 2 V 2 E 2 nbsp wenn seine Knotenmenge V 1 displaystyle V 1 nbsp Teilmenge von V 2 displaystyle V 2 nbsp und seine Kantenmenge E 1 displaystyle E 1 nbsp Teilmenge von E 2 displaystyle E 2 nbsp ist also V 1 V 2 displaystyle V 1 subseteq V 2 nbsp und E 1 E 2 displaystyle E 1 subseteq E 2 nbsp gilt Umgekehrt heisst G 2 displaystyle G 2 nbsp dann Supergraph oder Obergraph von G 1 displaystyle G 1 nbsp Diese Bezeichnungen sind nicht einheitlich Im unten angegebenen Lehrbuch von Klaus Wagner 1 wird in dieser Allgemeinheit nur der Begriff Teilgraph verwendet und ein Untergraph als Teilgraph definiert der zusatzlich die Eigenschaft hat dass jede Kante aus G 2 displaystyle G 2 nbsp die zwei Knoten aus G 1 displaystyle G 1 nbsp verbindet auch eine Kante in G 1 displaystyle G 1 nbsp ist Im Lehrbuch von Claude Berge 2 bedeutet Teilgraph zusatzlich dass V 1 V 2 displaystyle V 1 V 2 nbsp ist und Untergraph dass V 1 V 2 displaystyle V 1 subset V 2 nbsp und jede Kante aus G 2 displaystyle G 2 nbsp die zwei Knoten aus G 1 displaystyle G 1 nbsp verbindet auch eine Kante in G 1 displaystyle G 1 nbsp ist der allgemeine Fall heisst dann dort Teil Untergraph Es empfiehlt sich daher bei jedem Autor die verwendete Definition zu prufen Bei einem knotengewichteten bzw kantengewichteten Graphen G 2 displaystyle G 2 nbsp wird von einem Teilgraphen G 1 displaystyle G 1 nbsp zudem verlangt dass die Gewichtsfunktion g 1 displaystyle g 1 nbsp von G 1 displaystyle G 1 nbsp kompatibel zu der Gewichtsfunktion g 2 displaystyle g 2 nbsp von G 2 displaystyle G 2 nbsp sein muss d h fur jeden Knoten v V 1 displaystyle v in V 1 nbsp gilt g 1 v g 2 v displaystyle g 1 v g 2 v nbsp bzw fur jede Kante e E 1 displaystyle e in E 1 nbsp gilt g 1 e g 2 e displaystyle g 1 e g 2 e nbsp Gilt fur einen Teilgraphen G 1 displaystyle G 1 nbsp zusatzlich dass E 1 displaystyle E 1 nbsp alle Kanten zwischen den Knoten in V 1 displaystyle V 1 nbsp enthalt die auch in E 2 displaystyle E 2 nbsp vorhanden sind so bezeichnet man G 1 displaystyle G 1 nbsp als den durch V 1 displaystyle V 1 nbsp induzierten Teilgraphen von G 2 displaystyle G 2 nbsp und notiert diesen auch mit G 2 V 1 displaystyle G 2 V 1 nbsp Ein induzierter Teilgraph ist also immer eindeutig durch den Obergraphen und die gewahlte Knotenmenge bestimmt Fur eine Knotenmenge W V displaystyle W subseteq V nbsp bezeichnet man mit G W displaystyle G setminus W nbsp den induzierten Teilgraphen der aus G V E displaystyle G V E nbsp durch Weglassen der Knoten aus W displaystyle W nbsp und aller mit diesen Knoten inzidenten Kanten entsteht also G W G V W displaystyle G setminus W G V setminus W nbsp Ein Teilgraph G 1 V E 1 displaystyle G 1 V E 1 nbsp von G 2 V E 2 displaystyle G 2 V E 2 nbsp der alle Knoten seines Obergraphen enthalt wird aufspannender Teilgraph oder Faktor genannt Beispiele BearbeitenIn der folgenden Abbildung sind die Graphen G 1 displaystyle G 1 nbsp G 2 displaystyle G 2 nbsp und G 3 displaystyle G 3 nbsp Teilgraphen von G displaystyle G nbsp aber nur G 2 displaystyle G 2 nbsp und G 3 displaystyle G 3 nbsp sind induzierte Teilgraphen G 3 displaystyle G 3 nbsp entsteht dabei aus G displaystyle G nbsp durch Weglassen der Knoten 1 3 7 displaystyle 1 3 7 nbsp und ihrer inzidenten Kanten also ist G 3 G 1 3 7 displaystyle G 3 G setminus 1 3 7 nbsp Gleichzeitig ist G 3 displaystyle G 3 nbsp auch ein induzierter Teilgraph von G 2 displaystyle G 2 nbsp nbsp Beispiele fur TeilgraphenbeziehungenSiehe auch BearbeitenUnterteilungsgraph Minor Graphentheorie Satz von Kuratowski Krausz PartitionLiteratur BearbeitenReinhard Diestel Graphentheorie 4 Auflage Springer Verlag Berlin Heidelberg 2010 ISBN 978 3 642 14911 5 354 Seiten online Lutz Volkmann Fundamente der Graphentheorie Springer Wien 1996 ISBN 3 211 82774 9 neuere Online Version Graphen an allen Ecken und Kanten PDF 3 51 MB Einzelnachweise Bearbeiten Klaus Wagner Graphentheorie BI Hochschultaschenbucher 1969 Band 248 Kap I 3 Definition 4 Claude Berge Programme Spiele Transportnetze Teubner Verlag 1969 Zeiter Teil Kap I Absatz 1 Seite 121 Abgerufen von https de wikipedia org w index php title Teilgraph amp oldid 232815519