Mathe:Mathehelfer Ganter
Die Formatierung kommt noch
Inhaltsverzeichnis
Gruppen
Struktur: $ (G, \circ, ^{-1}, e) $
- G: Trägermenge
- o: assoziative zweistellige Operation (assoziativ: x o (y o z) = (x o y) o z )
- $ {}^{-1} $: bezüglich o inverse Elemente (x o x-1 = x-1 o x = e)
- e: bezüglich o neutrales Element (x o e = e o x = x)
|G| ist die Ordnung von G
|
Beispiel:
Es ist zu zeigen, dass die Funktionen
$ f_1(x) = x, ~f_2(x) = 1-x, ~f_3(x) = \frac{1}{x}, ~f_4(x) = \frac{1}{1-x}, ~f_5(x) = \frac{x-1}{x}, ~f_6(x) = \frac{x}{x-1} $
|
Untergruppe, kleinste Untergruppe, die Teilmenge von G enthält
- enthält neutrales Element
- ist gegen $ {}^{-1} $ und $ \circ $ abgeschlossen ($ e \in G_u;~ \forall x \in G_u: x^{-1} \in G_u;~ \forall x, y \in G_u: x \circ \in G_u $
- Notation: $ U \le G $
- Zu jedem $ T \subseteq G $ existiert kleinste UG, die T enthält ("von T erzeugte Untergruppe <T>"), bestehend aus:
- neutralem Element
- allen Elementen von T
- allen Elementen die durch Anwenden des Operators von allen Elementen aus T und durch Inversenbildung entstehen
Index von Untergruppen
G sei endliche Gruppe, U sei Untergruppe von G. [G: U] ist Index von U (Anzahl der Nebenklassen von U in G.
Satz von LaGrange: $ [G: U] = \frac{\left| G \right| }{\left| U \right| } $
("Die Ordnung einer Untergruppe teilt die der Gruppe")
|
Beispiel: Eine Gruppe mit 62 Elementen kann Untergruppen der Ordnung 1, 2, 31, 62 haben, aber sicher keine mit Ordnung 3, 4, 5, 6, 33 ... |
Nebenklassen
Sei U eine Untergruppe, $ a \in G $(G ist Menge, aus denen Untergruppen gebildet wurden). Es gibt
Linksnebenklassen (LNK): $ a \circ U = \{ a \circ u \vert u \in U \} $
Rechtsnebenklassen (RNK): $ U \circ a = \{ u \circ a \vert u \in U \} $
Jede Nebenklasse von U hat gleiche Mächtigkeit wie U
Zyklische Gruppen
Eine von einem Element erzeugte Gruppe
- besteht aus Potenzen dieses Elements
- ist <a> unendlich, dann ist <a> isomorph zu $ (\mathbb{Z} , +) $
- ist <a> endlich, dann existiert eine kleinste Zahl m mit $ a^m = 1 $und es gilt
$ G = <a> = \{1, a, a^2, ..., a^{m-1} \} $ , G ist dann isomorph zu $ (\mathbb{Z}_m , +) $
- Die Ordnung von a ist |<a>|, entweder unendlich oder m.
Isomorphie von Gruppen
Zwei Gruppen $ \underline{G} := (G, \cdot, {}^{-1}, 1_G) $ und $ \underline{H} := (H, \cdot, {}^{-1}, 1_H) $ sind isomorph (G "isomorphiezeichen" H), wenn es eine bijektive Abbildung $ \varphi : G \to H $ gibt, die strukturerhaltend ist:
- $ \varphi(x \cdot y) = \varphi(x) \cdot \varphi(y) $
- $ \varphi(x^{-1}) = \varphi(x)^{-1} $
- $ \varphi(1_G) = 1_H $
direktes Produkt
Das Produkt zweier Gruppen $ \underline{G} := (G, \cdot, {}^{-1}, 1_G) $ und $ \underline{H} := (H, \cdot, {}^{-1}, 1_H) $ auf der Menge $ G x H := \{(g, h) \vert g \in G, h \in H\} $ ist definiert durch:
- $ (g_1, h_1) \cdot (g_2, h_2) := (g_1 \cdot g_2, h_1 \cdot h_2) $
- Inverse Elemente: $ (g, h)^{-1} := (g^{-1}, h^{-1}) $
- Neutrales Element: $ (1_G, 1_H) $
Permutationen
- bijektive Abbildung: $ \varphi: A \to A $
- Anzahl der Permutationen: |A|!
- Hintereinanderausführung ist bijektiv (Hintereinanderausführung v. Permutationen ist wieder Permutation)
Symmetrische Gruppe
Permutation auf fester Menge A, bezeichnet mit $ S_A $
|
Symmetrische Gruppen werden auch mit Sym(Maximales Element) bezeichnet.
|
Links- / Rechtsnebenklassenzerlegung
siehe Gruppen -> Nebenklassen
|
Es müssen alle a aus G mit allen u aus U verknüpft werden.
Beispiel für $ U_1 = \{1\} $(aus obigem Beispiel): |
Normalteiler
Eine Untergruppe U ist Normalteiler, wenn gilt: LNK = RNK (siehe Links. / Rechtsnebenklassenzerlegung).
Normalteiler sind Kerne von Gruppenhomomorphismen
|
Das Beispiel bei LNK/RNK erfüllt dieses Kriterium und ist Normalteiler. |
Permutationsgruppen
Untergruppen von $ S_A $
Fixpunkt
$ v \in V;~\alpha(v) = v $ ($ \alpha $: Permutation)
(Permutationen ohne Fixpunkte nennt man fixpunktfrei)
Zyklus
Permutation mit $ \alpha $ ist Zyklus der Länge k, wenn es r verschiedene Elemente $ v_0, ..., v_{r-1} $ von V gibt mit:
- Es gilt $ \alpha(v_0) = v_1;~\alpha(v_1) = v_2;~ ...;~ \alpha(v_{r-2}) = v_{r-1} ~und~ \alpha(v_{r-1}) = v_0 $
- Alle anderen Elemente von V sind Fixpunkte
- Notation: $ (a_1 a_2 ... a_r) $
|
Um für gegebene Permutationen die Zyklen(-schreibweise) anzugeben wird die Permutation in seine Zyklen unterteilt. Es wird bei dem ersten Element begonnen und geprüft, wie es sich über die Permutation weg weiter ableitet. Dabei werden Verknüpfungen von rechts nach links betrachtet. |
elementfremde Permutationen
2 Permutationen $ \alpha, \beta \in S_A $ sind elementfremd, wenn aus $ \alpha(x) \ne x $ folgt $ \beta(x) = x $
Transposition
- Zyklus der Länge 2
- jeder Zyklus kann als Produkt von Transpositionen geschrieben werden
- jede Permutation auf einer endlichen Menge lässt sich als Produkt von Transpositionen schreiben
|
Um eine Permutation in Transpositionen zu zerlegen kann folgendes Schema angewandt werden: $ (a_1 a_2 a_3 ... a_{n-1} a_n) = (a_1 a_n)(a_1 a_{n-1}) (a_1 a_{n-2}) ... (a_1 a_2) $ 1. Beispiel: $ (4512) = (42)(41)(45) $ |
Signum
$ \alpha $ ist Permutation, $ sgn(\alpha) \in \{-1, 1\} $
- $ sgn(\alpha \circ \beta) = sgn(\alpha) \circ sgn(\beta) $
- $ sgn(\tau) = -1 $ für jede Transposition $ \tau $
- Ist $ \alpha $ ein r-Zyklus, dann ist $ sgn(\alpha) = (-1)^{r+1} $
|
Alle Permutationen lassen sich in einzelne Transpositionen zerlegen. $ sgn(\pi) $ ist +1, wenn die Anzahl der Transpositionen gerade ist, ansonsten -1. |
Inverse
Umgekehrte Permutation, $ \sigma \circ \sigma^{-1} = id $
|
Lassen sich finden durch umdrehen einer Permutation aber Erhalten der Verknüpfungsreihenfolge, falls mehrere verknüpft sind.
1. Beispiel: $ (123)^{-1} = (321) $ |
Ordnung (maximale Potenz)
Es existiert ein k, so dass $ \sigma^k = id $, k = kgV(Länge der Zyklen).
|
Beispiel:$ \sigma = (1756)(283) $ . k = kgV(4, 3) = 12, das heißt $ \sigma^12 = id $ |
Morphismen
- Morphismus: strukturerhaltende Abbildung v. Mengen A und B durch $ f: A \to B $
- Isomorphismus: f ist bijektiv (jedes Element v. A wird auf genau ein Element von B abgebildet
- Automorphismus: Isomorphismus, bei dem A = B
Graphen
Struktur: (V, E)
- V: Ecken (Vertices)
- E: Kanten (Edges)
Eckengrad
$ deg(a), a \in V $ ist Anzahl der Kanten, in denen A vorkommt, also $ deg(a) = \left| \{k \in E \vert a \in k \} \right| $
Weg
Ein Weg von Ecke a zu Ecke b ist eine Folge $ a_0, a_1, ..., a_n $ von Ecken $ a_i \in V $ mit:
- $ a_0 = a, a_n = b $ mit $ a_i \ne a_j $ für $ i \ne j $
- für alle $ i \in \{0, ..., n-1\} $ ist $ a_i, a_{i+1}\} \in E $
- n ist die Weglänge
- Graph heißt zusammenhängend, wenn es zu je zwei Ecken einen Weg gibt
- Jeder Graph zerfällt in Zusammenhangskomponenten
Kreis
Eine Folge $ a_0, a_1, ..., a_n, a_0 $ von Ecken mit:
- n > 1
- $ a_0, a_1, ..., a_n $ ist ein Weg
- $ \{a_n, a_0\} \in E $
- n+1 ist Länge des Kreises
- Kreise mit n=3 werden Dreiecke genannt, ...
Isomorphie von Graphen
Es gibt eine Abbildung $ \varphi: V_1 \to V_2 $:
- f ist bijektiv
- f ist kantenerhaltend: $ \forall \{v, w\} \in E_1: \{\varphi(v), \varphi(w)\} \in E_2 $
- f ist kantenreflektierend: $ \forall \{y, z\} \in E_1: \exists \{v, w\} \in E_2 $ mit $ \{\varphi(v), \varphi(w)\} = \{y, z\} $
Automorphismengruppe
Menge aller Automorphismen Aut(V, E) ist Permutationsgruppe auf V
Planarität
- Ein Graph (V, E) ist genau dann planar, wenn er als Teilgraph nicht den Graphen $ K_{3,3} $ oder den Graphen $ K_5 $ enthält (kleinste nicht-planare Graphen).
- So ein Graph besitzt keine Dreiecke (also mindestens Vierecke)
- Nach Eulerscher Polyederformel gilt für planare Graphen: $ e+f-k = 2 $
(e: Anzahl der Ecken, f: Anzahl der Flächen, k: Anzahl Kanten)
- Berechnung der Anzahl der Flächen durch: $ f = k+2-e $. Falls ein Graph mindestens Vierecke enthält (also auch $ K_{3,3} $ oder $ K_5 $ müsste auch gelten: $ 2f \leq k $, da eine Kante zwei Vierecke einschließt. Wäre der Graph also planar, müsste gelten: $ 2f \leq k $
(tut es bei nicht-planaren Graphen aber nicht, da die Anwendung der eulerschen Polyederformel für die Flächen ein falsches Ergebnis liefert)
|
Beispiel: Im Petersengraph kann $ K_{3,3} $ gefunden werden. Beschriftet man den Petersengraph von oben im Uhrzeigersinn erst außen und dann innen fortlaufend mit Zahlen, angefangen bei 1, findet sich $ K_{3,3} $ wie rechts (noch nicht) zu sehen. Außerdem funktioniert die eulersche Polyederformel nicht. Danach wären nämlich $ f = k + 2 - e = 9 + 2 - 6 = 5 $ Flächen enthalten. Da der Petersengraph aber minimal Vierecke enthält müsste auch gelten $ 2f \leq k $. Test: $ 10 \leq 9 $. Falsche Aussage, Graph nicht planar. |
Orbits / Bahnen
Ist $ \Gamma \leq S_V $ (Untergruppe von $ S_V $ ist eine Permutationsgruppe und $ v \in V $, dann ist der Orbit oder die Bahn von v unter $ \Gamma $:
$ v^\Gamma := \{ \alpha(v) \vert \alpha \in \Gamma\} $
Es gilt:
- $ v \in w^\Gamma \Leftrightarrow w \in v^\Gamma $
- Aus $ v^\Gamma \cap w^\Gamma \ne \emptyset $ folgt $ v^\Gamma = w^\Gamma $
- Jedes Element von V liegt genau in einem Orbit von $ \Gamma $
Permutationsgruppen mit genau einer Bahn heißen transitiv
Stabilisator
Ist $ \Gamma \leq S_V $ eine Permutationsgruppe und $ v \in V $, dann ist der Stabilisator definiert als:
$ \Gamma_V := \{\gamma in \Gamma \vert \gamma(v) = v\} $
Lemma von Cauchy-Frobenius
$ \left| \Gamma_v \right| \cdot \left| v^\Gamma \right| = \left| \Gamma \right| $
Körper über Primzahlen
Lemma von Fermat
p ist Primzahl, a ist ganze Zahl, die nicht durch p teilbar ist, dann gilt:
$ a^{(p-1)}~mod~p = 1 $
|
1. Beispiel: |
