Mathe:Mathehelfer Ganter

Aus Tudwiki
Wechseln zu: Navigation, Suche

Die Formatierung kommt noch

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} $


$ \circ $ f1 f2 f3 f4 f5 f6
f1 f1 f2 f3 f4 f5 f6
f2 f2 f1 f5 f6 f3 f4
f3 f3 f4 f1 f2 f6 f5
f4 f4 f3 f6 f5 f1 f2
f5 f5 f6 f2 f1 f4 f3
f6 f6 f5 f4 f3 f2 f1


bezüglich Hintereinanderausführung eine Gruppe bilden. Es muss gezeigt werden, dass die Hintereinanderausführung einer beliebigen Kombination dieser Funktionen in einer der obigen Funktionen resultiert und dass es ein neutrales Element und inverse Elemente gibt. Rechtsstehende Verknüpfungstabelle zeigt das. das Neutrale Element ist $ f_1(x) $. Die Hintereinanderausführung versteht sich als $ (f_1 \circ f_2 )(x) = f_1(f_2(x)) $.


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.

Beispiel: Sym(3) = Menge aller Permutationen über M={1,2,3}.
Untergruppen findet man, indem aus der Verknüpfungstabelle die Permutationen abliest, welche die 3 oben genannten Kriterien für Untergruppen erfüllen (Siehe Gruppen -> Untergruppen).
$ \begin{matrix} U_1=\{1\} & U_2 = \{1,2\} & U_3 = \{1, 3\} \\ U_4 = {1, 23} & U_5 = \{1, 123, 132\} & U_6 = G \end{matrix} $

1 12 13 23 123 132
1 1 12 13 23 123 132
12 12 1 132 123 23 13
13 13 123 1 132 12 23
23 23 132 123 1 13 12
123 123 13 23 12 132 1
132 132 23 12 13 1 123

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):
LNK: $ (1 \circ U_1)\cup(12 \circ U_1)\cup ... \cup(132 \circ U_1) = \{\{1\}, \{12\}, \{13\}, \{23\}, \{123\}, \{132\}\} $
RNK: $ (U_1 \circ 1)\cup(U_1 \circ 12)\cup ... \cup(U_1 \circ 132) = \{\{1\}, \{12\}, \{13\}, \{23\}, \{123\}, \{132\}\} $

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.
Beispiel: $ (12) \circ (123) \circ (12) = (132) $
In (12) wird die 1 zur 2, dann wird in (123) die 2 zur 3, in (12) passiert nichts mehr mit der 3, also beginnt der Zyklus mit (13 ...). Es wird die letzte Zahl des erstellten Zyklus betrachtet: die 3. In der ersten Permutation (12) passiert nichts mit der 3, in (123) wird die 3 zur 1, in der zweiten wird die 1 zur 2, also wird insgesamt die 3 zur 2, Ergebnis (132). Es wird die 2 betrachtet: In (12) wird die 2 zur 1, in (123) wird die 1 zur 2, in (12) wird die 2 zur 1, also wird die 3 zur 1. Zyklus komplett.


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) $
Hinweis: Nicht vergessen, dass Verknpüfungen von rechts nach links ausgewertet werden, also erst (45), dann (41), dann (42).

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) $
2. Beispiel: $ ((123)(456))^{-1} = (321)(654) $


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 $
Die Potenzen einer Permutation können also modulo k genommen werden. Das bedeutet weiterhin:
$ \sigma^13 = \sigma, \sigma^14 = \sigma^2 , ... $
$ \sigma^11 = \sigma^{-1}, \sigma^10 = \sigma^{-2}, ... $



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:
p = 997
$ 2^{1000} = 2^{996} \cdot~2^4~mod~997 = 1~\cdot 2^4~mod~997 = 16 $

2. Beispiel (Ermitteln, ob p eine Primzahl ist):
Wenn p eine Primzahl ist, dann gilt für alle 0 < a < p: $ a^{p-1}~mod~p = 1 $