„Blätter und innere Knoten in der Graphentheorie“ – Versionsunterschied
Zur Navigation springen
Zur Suche springen
| [gesichtete Version] | [gesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
Link auf "Nachbar" statt auf "Grad" (einfacher) und Beispiel besser eingebunden |
mit literatur |
||
| Zeile 1: | Zeile 1: | ||
In der [[Graphentheorie]] werden bei einem [[Baum (Graphentheorie)|Baum]] die [[Knoten (Graphentheorie)|Knoten]] mit genau einem [[Nachbar (Graphentheorie)|Nachbarn]] als '''Blatt''' oder ''Endknoten'' und die Knoten mit mehr als einem Nachbarn als '''innere Knoten''' oder ''Nicht-Endknoten'' bezeichnet. |
In der [[Graphentheorie]] werden bei einem [[Baum (Graphentheorie)|Baum]] die [[Knoten (Graphentheorie)|Knoten]] mit genau einem [[Nachbar (Graphentheorie)|Nachbarn]] als '''Blatt''' oder ''Endknoten'' (engl. ''leaf'') und die Knoten mit mehr als einem Nachbarn als '''innere Knoten''' oder ''Nicht-Endknoten'' (engl. ''inner vertex'') bezeichnet. Übliche Definitionen sind: |
||
* „Die Ecken vom Grad 1 eines Baumes sind seine Blätter“ (Diestel, 2006, Seite 14) |
|||
Bei [[Gewurzelter Baum|gewurzelten Baum]] wird häufig die [[Wurzel (Graphentheorie)|Wurzel]] von dieser Definition ausgenommen. Die bei diesen Bäumen alternativ übliche Definition von Blättern als Knoten mit Ausgangsgrad Null (beim [[Out-Tree]]; beim [[In-Tree]] ist stattdessen der Eingangsgrad Null) führt ohne die Ausnahme der Wurzel dazu, dass der triviale Baum mit genau einem Knoten aus einem Blatt besteht, das zugleich Wurzel ist. |
|||
* „Die Knoten eines Baumes vom Grad 1 werden Blätter genannt, die Knoten vom Grad |
|||
größer als 1 heißen innere Knoten“ (Meinel und Mundhenk, 2006, Seite 260) |
|||
* „Eine Ecke mit Ausgangsgrad 0 nennt man ein ''Blatt'' des Baumes. Die anderen Ecken nennt man ''innere Ecken''“ (Turau, 2004, Seite 53) |
|||
Die [[Wurzel (Graphentheorie)|Wurzel]] eines [[Gewurzelter Baum|gerichteten Baums]] ist üblicherweise von dieser Definition ausgenommen. Ebenso wird der Sonderfall eines isolierten Knotens meist nicht berücksichtigt. |
|||
== Beispiele == |
== Beispiele == |
||
| Zeile 14: | Zeile 19: | ||
| align=center | [[Bild:directed-tree.svg]] |
| align=center | [[Bild:directed-tree.svg]] |
||
|} |
|} |
||
== Quellen und weiterführende Literatur == |
|||
* {{Literatur|Autor=Reinhard Diestel|Titel=Graphentheorie|Auflage=3.|Jahr=2006|Verlag=Springer|ISBN=3-540-21391-0}} |
|||
* {{Literatur|Autor=Christoph Meinel, Martin Mundhenk|Titel=Mathematische Grundlagen der Informatik|Auflage=3.|Jahr=2006|Verlag=Teubner|ISBN=3-8351-0049-1}} |
|||
* {{Literatur|Autor=Volker Turau|Titel=Algorithmische Graphentheorie|Auflage=2.|Jahr=2004|Verlag=Oldenbourg|ISBN=3-486-20038-0}} |
|||
[[Kategorie:Graphentheorie]] |
[[Kategorie:Graphentheorie]] |
||
Version vom 19. Mai 2008, 01:52 Uhr
In der Graphentheorie werden bei einem Baum die Knoten mit genau einem Nachbarn als Blatt oder Endknoten (engl. leaf) und die Knoten mit mehr als einem Nachbarn als innere Knoten oder Nicht-Endknoten (engl. inner vertex) bezeichnet. Übliche Definitionen sind:
- „Die Ecken vom Grad 1 eines Baumes sind seine Blätter“ (Diestel, 2006, Seite 14)
- „Die Knoten eines Baumes vom Grad 1 werden Blätter genannt, die Knoten vom Grad
größer als 1 heißen innere Knoten“ (Meinel und Mundhenk, 2006, Seite 260)
- „Eine Ecke mit Ausgangsgrad 0 nennt man ein Blatt des Baumes. Die anderen Ecken nennt man innere Ecken“ (Turau, 2004, Seite 53)
Die Wurzel eines gerichteten Baums ist üblicherweise von dieser Definition ausgenommen. Ebenso wird der Sonderfall eines isolierten Knotens meist nicht berücksichtigt.
Beispiele
In den folgenden Beispielen eines ungerichteten und eines gerichteten Baums sind die Blätter weiß und die inneren Knoten schwarz markiert. Bei dem gerichteten Baum wird die Wurzel (markiert durch einen zusätzlichen Kreis) hier auch als innerer Knoten aufgefasst.
| Ungerichteter Baum | Gerichteter Baum (hier: Out-Tree) |
|---|---|
|
|
Quellen und weiterführende Literatur
- Reinhard Diestel: Graphentheorie. 3. Auflage. Springer, 2006, ISBN 3-540-21391-0.
- Christoph Meinel, Martin Mundhenk: Mathematische Grundlagen der Informatik. 3. Auflage. Teubner, 2006, ISBN 3-8351-0049-1.
- Volker Turau: Algorithmische Graphentheorie. 2. Auflage. Oldenbourg, 2004, ISBN 3-486-20038-0.