Halbordnung auf einen Baum < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Für jeden beliebigen Wurzelbaum T = (V,E) mit Wurzel v* lassen sich
zwei Halbordnungen auf V so definieren, dass v* entweder kleinstes oder
größtes Element ist.
(i) Welche Halbordnungen sind das?
(ii) Sind diese Halbordnungen fundiert oder nicht? Begründen Sie Ihre
Antwort. |
Guten Tag!
Also ich habe Probleme mit der Fragestellung, jedenfalls bin ich mir nicht so sicher ob meine Antwort dazu passt:
Erstmal hab ich mir einen Baum aufgemalt - soweit kein Problem.
Eine Halbordnung ist ja z.B.die [mm] \le [/mm] oder [mm] \ge [/mm] Ordnung.
Wenn ich mir nun einen Baum mit Wurzel v* an oberster Stelle vorstelle, so ist nichts auf auf einer Ebene mit der Wurzel. Alle anderen Knoten sind entweder auf einer Ebene (entspricht der = Relation) oder sind unter der Wurzel bzw. unter anderen Knoten(entspricht der < Relation). Damit hätte ich eine Relation, genauer die [mm] \le [/mm] Relation.
Analog kann man die Wurzel an die unterste Stelle schreibe und alle Knoten darüber, man kommt dann auf die [mm] \ge [/mm] Relation.
Damit kann ich auch gleich (ii) beantworten, denn diese Relationen sind nicht fundiert, denn die Teilmenge der Knoten wo die alle auf einer Ebene liegen besitzen kein minimales Element.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Di 30.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
