Diskrete Strukturen (Vorlesung 1)

In der ersten Vorlesung von diskrete Strukturen beschäftigen wir uns grundlegenden Eigenschaften, Graphen und Isomorphie.

Skript-Anfang	manuscript – Seite 1
Skript-Ende	manuscript – Seite 10

Einleitung

Definition für diskrete Strukturen

• Objekte, die sich durch Verknüpfungen, Verkettung, Mengenoperationen, Verschachtelung aus Listen, Mengen und Permutationen bilden lassen

Beispiele für elementare diskrete Strukturen

• Listen: [1,4,3,2]
• Matrizen als Liste von Listen: [[1,2],[4,5],[2,1]] = \( \begin{bmatrix}1 & 4 & 2 \ 2 & 5 & 1\end{bmatrix} \)
• Mengen: {1,4,3}

Darstellung von Mengen durch Listen

• Die Menge {1,4,3} lässt sich durch 6 verschiedene Listen darstellen
• Im Kontext von Mengen fallen diese zu einem einzigen Element zusammen
• Dieses Element wird auch Repräsentant genannt und kann beliebig gewählt werden (meist eine sortierte Liste)

Beispiel für {1,4,3}

1. [1,4,3]
2. [1,3,4] (sortierte Liste)
3. [3,1,3]
4. [3,4,1]
5. [4,1,3]
6. [4,3,1]

Graphen

• Darstellung kann mittels „Adjazenzmatrix“ erfolgen
• Knoten sind nie mit sich selbst verbunden

Isomorphe Graphen

• Diese Graphen haben die gleiche Struktur
• Lässt man die Bezeichnungen weg, sind diese Graphen identisch
• Isomorphie ist ein anderer Begriff von Äquivalenz
• Gleiche Graphen können somit als Äquivalenzklassen zusammengefasst werden

Wie viele Kanten hat ein Graph mit n Punkten/Knoten?

• Anzahl der Knoten = \( \binom{n}{2} = \frac{n(n-1)}{2} \)
• Bei 4 Knoten (n=4) gib es 6 Kanten

Wie viele Graphen gibt es bei n Punkten/Knoten?

• Anzahl der Graphen = \( 2^\binom{n}{2} = 2^\frac{n(n-1)}{2} \)
• Bei 4 Knoten (n=4) gib es 64 (2⁶) verschiedene Graphen
• Bei 4 Knoten gibt es 11 Klassen

Wichtige Fragen

1. Wie bestimme ich das kanonische Element?
2. Welche und wie viele Klassen gibt es bei n Knoten? (via Abzählen oder Formel)
3. Wie viele Elemente sind in einer Klasse?
4. Ist ein Element in einer Klasse? (Äquivalenztest)

Einteilung in Äquivalenzklassen bzw. Partitionierung

• X ist die Gesamtheit bzw. Menge der Ausgangsobjekte
• Bei der Partitionerung gibt es keine doppelten Objekte
• Jedes Element ist durch Reflexivität in einer Klasse (vollständige Partition)
• Ein Element kann wegen der Transitivität nicht in zwei Klassen gleichzeitig sein
• Gibt es eine Schnittmenge, ist es keine Partitionierung

Relationen für Mengen

• Reflexivität: \( x \simeq x \)
• Symmetrie: \( x \simeq y \Rightarrow y \simeq x \)
• Transitivität: \( x \simeq y \wedge y \simeq z \Rightarrow x \simeq z \)

Wie bestimmt man alle Graphen mit n Knoten?

• Man nummeriert alle möglichen Kanten und stellt einen Graph als Vektor dar
• Für die Erzeugung werden die Graphen iterierend durchlaufen

Beispiele

• 012345 = [111111] = voll besetzt
• 0125 = [111001]

Wie prüft man, ob zwei Graphen isomorph sind?

• Zwei graphen sind isomorph, wenn eine Permutation von einem zum anderen angewendet werden kann
• Permutation: \( \Pi \left\{\begin{matrix} 0 \mapsto 3 \ 1 \mapsto 2 \ 2 \mapsto 0 \ 3 \mapsto 1 \end{matrix}\right. \)
• S_n = Menge der Permutationen
• Isomorphie: \( x \simeq x‘ \Leftrightarrow \exists \Pi \in S_{n}:\Pi x=x‘ \ \Rightarrow x \simeq x‘ \Leftrightarrow \exists g \in G:g x=x‘ \)

Beispiel

Permutation: \( \Pi \left\{\begin{matrix} 0 \mapsto 1 \ 1 \mapsto 0 \ 2 \mapsto 2 \ 3 \mapsto 3 \end{matrix}\right. \)