Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

7. Ordnungsrelationen

Graphen

Graph

E1=(K1,K3),E2=(K2,K3),E3=(K2,K4),E4=(K3,K4),K={K1,K2,K3,K4},E={E1,E2,E3,E4},Graph G={K,E}.\def\arraystretch{1.25} \begin{array}{lll}E_1 = (K_1, K_3),\quad E_2 = (K_2, K_3),\quad E_3=(K_2, K_4),\quad E_4=(K_3, K_4),\\K=\{K_1, K_2, K_3, K_4\},\quad E = \{E_1, E_2, E_3, E_4\},\quad \text{Graph } G=\{K, E\}.\end{array}

Spezielle Strukturen

  • Liste

Liste
  • Baum

Baum
  • Schleife/Kreise

Kreis
  • Clique

Clique

Eigenschaften von Relationen

Nun betrachten wir spezielle Relationen auf einer Menge AA, um Ordnung (Struktur) in diese Menge zu bringen. Die Relationen werden dazu dienen, jeweils zwei Elemente zu vergleichen, etwa wie das \leq auf den reellen Zahlen.

  • Transitiv: Wenn wir xx vor yy und yy vor zz einsortieren, sollte auch xx vor zz landen.

  • Antisymmetrisch: Für zwei verschiedene Elemente xyx \neq y wollen wir eine eindeutige Reihung haben, es darf nicht xRyxRy und yRxyRx sein.

  • Reflexiv: Für \leq soll auch xRxxRx gelten. (Für << gilt dies nicht)

Partielle Ordnung

Eine transitive, antisymmetrische und reflexive Relation heißt partielle Ordnung.

Beispiel

Warum "partiell", sieht man am besten an einem Beispiel:

Sei AA die Potenzmenge einer beliebigen Menge, z.B. A=P{1,2,3}A=P \{1{,}2,3 \}. Die Relation \subseteq auf AA, also "ist Teilmenge von", erfüllt die Bedingungen an eine partielle Ordnung. Wenn die Ausgangsmenge aber wenigstens zwei Elemente enthält, ist die Potenzmenge dadurch noch nicht geordnet, da z.B. weder {1}{2}\{1\}\subseteq\{2\} noch {2}{1}\{2\}\subseteq\{1\} gilt.

Die Relation sollte also auch noch konnex sein.

(Totale) Ordnung

Eine konnexe partielle Ordnung nennt man (totale) Ordnung.

In einer endlichen Menge AA mit einer totalen Ordnung RR kann man die Elemente so nummerieren (A={x1,x2,,xn}A= \{x_1, x_2,\dots, x_n\} mit n=An=|A|), dass gilt:

(oder anders ausgedrückt: i,j{1,,n}:ijxiRxj\forall i,j\in\{1,\ldots,n\}: i\leq j \Leftrightarrow x_iRx_j.

Beweis

Der Beweis ist konstruktiv. Wir geben einfach ein Verfahren (einen Algorithmus) an, das diese Ordnung herstellt (Quicksort).

Wir machen einen Induktionsbeweis nach nn. Für n=0n= 0 und n=1n= 1 ist nichts zu zeigen, also sei nun n>2n>2 und der Satz gelte für alle Mengen BB mit 0Bn0 \leq| B|\leq n.

Wir wählen ein beliebiges zAz \in A (man nennt es Pivotelement) und zerlegen AA in drei Mengen:

  • A1:={xA:xRzxz}A_1:=\{x \in A: xRz \wedge x \neq z\}

  • A2:={z}A_2:=\{z\}

  • A3:={xA:zRxxz}A_3:=\{x \in A: zRx \wedge x\neq z\}

Nun ist A=A1A2A3A=A_1\cup A_2 \cup A_3, denn RR ist konnex: für jedes xAx \in A gilt xRzxRz oder zRxzRx und somit

xA:(xRzxz)(x=z)(zRxz)\forall x\in A: (xRz \wedge x \neq z) \vee (x=z) \vee (zRx \neq z)

Weiter sind die AiA_i paarweise disjunkt: A1A2=A1A3=A2A3=A_1\cap A_2 = A_1\cap A_3 = A_2\cap A_3 = \emptyset (Aufgabe: sortieren disjunkt).

Daher ist A=A1+1+A3|A|=|A_1|+ 1 +|A_3|, mithin 0A1=:m<A0 \leq |A_1|=:m <|A|und 0A3=n1m<A0 \leq |A_3|=n-1-m <|A|. Wir wenden die Induktionsvoraussetzung an und nehmen an, dass A1={x1,,xm}A_1=\{x_1,\dots, x_m\} und A3={xm+2,,xn}A_3=\{x_{m+2},\dots, x_n\} sortiert sind (in A3A_3 sind die Indizes um m+1m+ 1 verschoben, das stört die Sortierung nicht). Dann ist auch AA mit der Nummerierung A={x1,,xm,xm+1:=z,xm+2,,xn}A=\{x_1,\dots, x_m, x_{m+1}:=z, x_{m+2},\dots, x_n\} sortiert.

Dieser Induktionsbeweis lässt sich in ein rekursives Programm umsetzen, in dem man zur Sortierung der Teilmengen A1A_1 und A3A_3 das Programm selbst wieder aufruft.

Für den Beweis ist die Effizienz der Konstruktion egal. Ein echtes Sortierverfahren in der Praxis sollte aber effizient (schnell) sein.


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