„Wurzelgraph“ – Versionsunterschied
| [ungesichtete Version] | [ungesichtete Version] |
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
[[Wurzel]]{{–}}[[Graph]] {{agrie.-dt.}} '[[gewurzelter]] Graph' | [[Wurzel]]{{–}}[[Graph]] {{agrie.-dt.}} '[[gewurzelter]] Graph' | ||
[[Datei:Bicolored path, Misra and Gries edge coloring algorithm.png|mini|<span style="font-size: 14.4px;">Graph 𝐺 mit Knoten 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔</span>]] | [[Datei:Bicolored path, Misra and Gries edge coloring algorithm.png|mini|<span style="font-size: 14.4px;">Graph 𝐺 mit Knoten 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔</span>|230x230px]] | ||
In der [[Graphentheorie]] ist ein '''Wurzelgraph''' oder '''gewurzelter Graph''' (𝐺, 𝑜) ein [[Graph (Graphentheorie)|Graph]] 𝐺, in dem ein [[Knoten (Graphentheorie)|Knoten]] 𝑜 (die [[Wurzel (Graphentheorie)|Wurzel]]) ausgezeichnet worden ist.<ref><span class="reference-text">Peter Tittmann: <cite>Einführung in die Kombinatorik</cite>. 2014, [https://de.wikipedia.org/wiki/Spezial:ISBN-Suche/9783642545887 ISBN 978-3-642-54588-7], S. 210, [https://de.wikipedia.org/wiki/Digital_Object_Identifier doi]:<span class="uri-handle">[https://doi.org/10.1007/978-3-642-54589-4 10.1007/978-3-642-54589-4]</span> ([https://link.springer.com/book/10.1007%2F978-3-642-54589-4 springer.com] [abgerufen am 10. Mai 2018]).</span></ref> | In der [[Graphentheorie]] ist ein '''Wurzelgraph''' oder '''gewurzelter Graph''' (𝐺, 𝑜) ein [[Graph (Graphentheorie)|Graph]] 𝐺, in dem ein [[Knoten (Graphentheorie)|Knoten]] 𝑜 (die [[Wurzel (Graphentheorie)|Wurzel]]) ausgezeichnet worden ist.<ref><span class="reference-text">Peter Tittmann: <cite>Einführung in die Kombinatorik</cite>. 2014, [https://de.wikipedia.org/wiki/Spezial:ISBN-Suche/9783642545887 ISBN 978-3-642-54588-7], S. 210, [https://de.wikipedia.org/wiki/Digital_Object_Identifier doi]:<span class="uri-handle">[https://doi.org/10.1007/978-3-642-54589-4 10.1007/978-3-642-54589-4]</span> ([https://link.springer.com/book/10.1007%2F978-3-642-54589-4 springer.com] [abgerufen am 10. Mai 2018]).</span></ref> | ||
Zwei Wurzelgraphen (𝐺<sub>1</sub>, 𝑜<sub>1</sub>) und (𝐺<sub>2</sub>, 𝑜<sub>2</sub>) sind isomorph zueinander, wenn es einen [https://de.wikipedia.org/wiki/Isomorphie_von_Graphen Isomorphismus] 𝐺<sub>1</sub> → 𝐺<sub>2</sub> gibt, der 𝑜<sub>1</sub> auf 𝑜<sub>2</sub> abbildet.<p>Beispiel: Im Bild rechts sind die Wurzelgraphen (𝐺, 𝑏), (𝐺, 𝑐), (𝐺, 𝑑), (𝐺, 𝑒) isomorph zueinander, aber nicht zu den anderen Wurzelgraphen. (𝐺, 𝑎) und (𝐺, 𝑓) sind ebenfalls isomorph zueinander. (𝐺, 𝑔) ist zu keinem der anderen Wurzelgraphen isomorph.</p> | Zwei Wurzelgraphen (𝐺<sub>1</sub>, 𝑜<sub>1</sub>) und (𝐺<sub>2</sub>, 𝑜<sub>2</sub>) sind isomorph zueinander, wenn es einen [https://de.wikipedia.org/wiki/Isomorphie_von_Graphen Isomorphismus] 𝐺<sub>1</sub> → 𝐺<sub>2</sub> gibt, der 𝑜<sub>1</sub> auf 𝑜<sub>2</sub> abbildet.<p>Beispiel: Im Bild rechts sind die Wurzelgraphen (𝐺, 𝑏), (𝐺, 𝑐), (𝐺, 𝑑), (𝐺, 𝑒) isomorph zueinander, aber nicht zu den anderen Wurzelgraphen. (𝐺, 𝑎) und (𝐺, 𝑓) sind ebenfalls isomorph zueinander. (𝐺, 𝑔) ist zu keinem der anderen Wurzelgraphen isomorph.</p> | ||
== <span id="Einzelnachweis">Einzelnachweis</span> == | == <span id="Einzelnachweis">Einzelnachweis</span> == | ||
Version vom 28. März 2024, 14:16 Uhr
Wurzel–Graph Vorlage:agrie.-dt. 'gewurzelter Graph'
In der Graphentheorie ist ein Wurzelgraph oder gewurzelter Graph (𝐺, 𝑜) ein Graph 𝐺, in dem ein Knoten 𝑜 (die Wurzel) ausgezeichnet worden ist.[1]
Zwei Wurzelgraphen (𝐺1, 𝑜1) und (𝐺2, 𝑜2) sind isomorph zueinander, wenn es einen Isomorphismus 𝐺1 → 𝐺2 gibt, der 𝑜1 auf 𝑜2 abbildet.
Beispiel: Im Bild rechts sind die Wurzelgraphen (𝐺, 𝑏), (𝐺, 𝑐), (𝐺, 𝑑), (𝐺, 𝑒) isomorph zueinander, aber nicht zu den anderen Wurzelgraphen. (𝐺, 𝑎) und (𝐺, 𝑓) sind ebenfalls isomorph zueinander. (𝐺, 𝑔) ist zu keinem der anderen Wurzelgraphen isomorph.
Einzelnachweis
- ↑ Peter Tittmann: Einführung in die Kombinatorik. 2014, ISBN 978-3-642-54588-7, S. 210, doi:10.1007/978-3-642-54589-4 (springer.com [abgerufen am 10. Mai 2018]).