🎓 Ui, fast schon PrĂŒfungszeit? Hier geht's zur Mathe-PrĂŒfungsvorbereitung.
Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Aufgaben zum Thema Ordnungsrelationen

  1. 1

    Was fĂŒr partielle Ordnungen und was fĂŒr totale Ordnungen gibt es auf zweielementigen Mengen {x,y}\{x,y\}?

  2. 2

    FĂŒhre das im Beweis verwendete Sortierverfahren fĂŒr die Menge A={d,b,c,a,f,e}A=\{d, b, c, a, f, e\} mit der alphabetischen Sortierung durch. Verwende als Pivotelement zz immer das vorderste Element (am Anfang also dd) und lasse die Reihenfolge der Elemente in A1A_1 und A3A_3 so, wie sie in AA waren (also nicht beim Zerlegen aus Versehen sortieren)!

  3. 3

    Wenn man fĂŒr eine endliche Menge AA mit n=∣A∣n=|A| Elementen nur eine partielle Ordnung hat, funktioniert das Sortieren nicht. (Warum nicht?)

    Es gibt aber einen entsprechenden Satz, der besagt, dass man AA mit seiner partiellen Ordnung topologisch sortieren kann, d.h. es gibt immer (mindestens) eine Nummerierung A={x1,x2,
,xn}A=\{x_1,x_2,\ldots,x_n\}, fĂŒr die gilt:

    ∀i,j∈{1,
,n}:xiRxj⇒i≀j\forall i,j\in\{1,\ldots,n\}: x_iRx_j \Rightarrow i\leq j.

    Beweise mithilfe dieses Satzes folgende Aussage: Zu jeder partiellen Ordnung RR auf einer endlichen Menge AA gibt es eine totale Ordnung Râ€ČR' mit R⊆Râ€ČR\subseteq R'. (In Worten: Jede partielle Ordnung auf einer endlichen Menge kann ich "durch HinzufĂŒgen von Pfeilen"' zu einer totalen Ordnung ausbauen.)


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?