TU Wien:Algebra und Diskrete Mathematik VO (Gittenberger)/Flashcards

From VoWi
Jump to navigation Jump to search
Das kartesische Produkt
A x B zweier Mengen A, B ist die Menge aller geordneter Paare (a,b) mit a ∈ A und b ∈ B, dh. A × B = {(a,b) | a ∈ A ∧ b ∈ B}
eine Relation
Eine Relation R zwischen zwei Mengen A und B ist eine Teilmenge des Karthesischen Produkts A × B.
eine binäre Relation
Ist eine Teilmenge des Karthesischen Produkts A × B wobei A = B.
eine Äquivalenzrelation
Eine binäre Relation R auf einer Menge A heißt Äquivalenzrelation, wenn sie Reflexiv, Symmetrisch und Transitiv ist.
Reflexivität
für alle a ∈ A : aRa
Symmetrie
für alle a,b ∈ A : aRb => bRa
Transitivität
für alle a,b,c ∈ A : (aRb ∧ bRc) => aRc
Äquivalenzklassen
ist ein System von nichtleeren Teilmengen Ai (i ∈ I) einer Menge A heißt Partizion oder Zerlegung von A, wenn die Ai (i ∈ I) paarweise disjunkt sind, d.h. Ai ⋂ Aj = 0 für i ≠ j, und A die Vereinigeung aller Ai (i ∈ I) ist.
Halbordnung
Eine binäre Relation R auf einer Menge A heißt Halbordnung, wenn sie Reflexiv, Antisymmetrisch und Transitiv ist.
Antisymmetrie
für alle a,b ∈ A : (aRb ∧ bRa) => a = b
Hassediagramm
-weglassen aller Schlingen

-weglassen aller Kanten bezogen auf die Transitivität -weglassen aller Orientierungen da Antisymetrie

Injektion
f: A -> B heißt injektiv, wenn zu jedem b ∈ B höchstens ein a ∈ A mit b = f(a) gibt. Wenn also a1 ≠ a2 => f(a1) ≠ f(a2) => b1 ≠ b2
Surjektion
f: A -> B heißt surjektiv, wenn es zu jedem b ∈ B mindestens ein a ∈ A mit b = f(a) gibt.
Bijektion
f: A -> B heißt bijektiv, wenn es zu jedem b ∈ B genau ein a ∈ A mit b = f(a) gibt.
Inverse Funktion
eine Funktion f : A -> B besitzt genau dann eine inverse Funktion f^-1 : B -> A wenn f bijektiv ist.
Variation mit Wiederholung
n^k => würfeln (einem Würfel) bzw. Tototip
Variation ohne Wiederholung
n*(n-1)*(n-2)*(n-3)...(n-k+1)= n!/(n-k)! => Wörter aus einer gewissen Anzahl Buchstaben des normalen Alphabets
Permutation einer Menge
n! => drei verschiedene Bücher in welcher Reihenfollge ins regal stellen. 3! = 6
Permutation einer Multimenge
(k1+k2+...kn)! / k1!*k2!...kn! => zwei Gläser Bier, 1 Glas Schnaps und 1 Glas Wein können in 4! / (2!*1!*1!) = 12 verschiedenen Reihenfolgen getrunken werden.
Auswahl einer Teilmenge
(Kombinationen ohne Wiederholung)

Eine (ungeordnete ) Auswahl von k verschiedenen Elementen einer Menge : n! / k!(n-k)! => Lottotipp => (45 über 6) = 45! / 6!(45-6)!

Auswahl einer Teilmultimenge
(Kombinationen mit Wiederholung) (würfeln mit mehreren Würfeln)

Einzelne Elemente können mehrfach auftreten : (n+k-1)! / k!(n-1)! = (n+k-1 über k)

Euler'sche Linie
Eine Kantenfolge in einem Graphen G heißt Euler'sche Linie, wenn sie jeden Knoten und jede Kante enthält, jedoch die Kanten nur ein mal. Bei einer geschlossenen Euler'schen Linie stimmen Anfangs- und Endknoten über ein. Offene Euler'sche Linie sind sie verschieden
Euler'sche Graph
Wenn der Graph eine Euler'sche Linie besitzt.
Hamilton'sche Linie
Eine Kantenfolge in einem Graph G heißt Hamilton'sche Linie, wenn sie jeden Knoten, mit Ausnahme des Anfangsknotens so er auch der Endknoten ist, genau ein mal enthält. Bei einer geschlossenen Hamilton'sche Linie stimmen Anfangs- und Endknoten über ein. Offene Hamilton'sche Linie sind sie verschieden
Hamilton'scher Graph
Wenn der Graph eine Hamilton'sche Linie besitzt.
Netzwerke (Graphen)
sind gerichtete oder ungerichtete Graphen , wobei jeder Kante dieses Graphen ein Wert zugeordnet wird.
Kruskal-Algorithmus
Bestimmt das minimale Gerüst eines Graphen. In jedem Schritt versucht man jene Kante mit minimal möglichem Gewischt zu verwenden um einen Knoten zu erreichen ohne Kreise zu bilden.
Dijkstra-Algorithmus
Bestimmt den kürzesten weg zwischen unterschiedlichen Knoten. Dabei wird zur besseren Übersicht einer Tabelle angelegt.
Man bestimme für das "6 aus 45"-Lotto die Anzahl der möglichen richtigen Fünfer, die mit einer vorgegebnene 6-elemetigen Teilmenge genau 5 Elemente gemeinsam haben.
Ergibt 6 Möglichkeiten: n! / k!(n-k)! = 6!/5! = 6 . Für den 6. Platz dann jeweils 39 Tips : 6 * 39 = 234 Möglichkeiten.
Jemand wirft eine Münze 2n mal. Wievele verschiedene Spielverläufe gibt es, wenn gleich oft Kopf und Adler auftreten.
Permutation einer Multimenge : Anzahl Kopf = n, Anzahl Adler = n, Anzahl der Würfe = 2n : (2n)! / n!*n! bei vier Münzwürfen : (2xKopf und 2xAdler) => n = 2 ; 2n = 4 =>

4! / 2!*2! = 24/4 = 6

Wie viele natürliche Zahlen n < 100.000 enthalten in ihrer Dezimalentwicklung genau dreimal die Ziffer 3?
1. Es gibt genau 100.000 Möglichkeiten für 5- stellige Dezimalzahlen von 00000 bis 99999

2. Es gibt folgende Kombinationen von 3*3 Ziffern auf 5 Positionen: n! / k!(n-k)! = 120/12 = 10 3. Jede Kombination wird an 2 Stellen mit einer Ziffer aus 0-2 und 4-9, also 9 Möglichkeiten aufgefüllt. Das ergibt 9*9 oder 81 Möglichkeiten. 4. Die Anzahl der Ziffern ist Anzahl der Kombinationen 10 *81 = 810

Wieviele Möglichkeiten gibt es, 23 verschiedengroße Kugeln so zu färben, dass 9 rot, 5 schwarz, 4 blau, 4 grün sind und eine weiß ist?
Permutation mit Multimengen :

23! / 9!*5!*4!*4!*1! = 1.03 * 10^12

Wie viele Möglichkeiten gibt es, drei (voneinander unterscheidbare) Würfel so zu werfen, dass genau zwei dieselbe Augenzahl zeigen?
der erste Würfel kann fallen wie er will: 6 Möglichk.

der zweite Würfel muss so fallen wie der erste: 1 Möglichk. der dritte kann fallen wie er will, nur nicht so wie der erste: 5 Möglichkeiten : 6*5*1 = 30 Das Ergebnis muss noch permutiert werden:Es könnten ja der erste und der zweite, oder der zweite und der dritte oder der erste und der dritte gleich sein: (2+1)! / 2!*1! = 3 3*30=90

Wie viele natürliche Zahlen n < 1.000.000 enthalten in ihrer Dezimalentwicklung genau vier mal die Ziffer 2?
1. Es gibt genau 1.000.000 Möglichkeiten für6- stellige Dezimalzahlen von 000000 bis 999999

2. Es gibt folgende Kombinationen von 4*2 Ziffern auf 6 Positionen: n! / k!(n-k)! = 720/48 = 15 3. Jede Kombination wird an 2 Stellen mit einer Ziffer aus 0-2 und 4-9, also 9 Möglichkeiten aufgefüllt. Das ergibt 9*9 oder 81 Möglichkeiten. 4. Die Anzahl der Ziffern ist Anzahl der Kombinationen 15 *81 = 1215

Wie viele Möglichkeite gibt es, k ununterscheidbare Kugeln auf n unterscheidbare Kästchen zu verteilen, wenn jedes Kästchen beliebig viele Kugeln (einschließlich 0) aufnehmen kann?
Auswahl einer Teilmultimenge (Kombinationen mit Wiederholung): Einzelne Elemente können mehrfach auftreten : (n+k-1)! / k!(n-1)! = (n+k-1 über k) => einzelne Fächer können mehrmalls eine Kugen empfangen.
Bei einer Wahl sollen unter 20 Kandidaten genau 3 angekreuzt werden, wobei zugelassen wird, dass mehrere Kreuze bei einem Kandidaten auftreten dürfen. Wie viele Möglichkeiten gibt es?
Auswahl einer Teilmultimenge (Kombinationen mit Wiederholung): Einzelne Elemente können mehrfach auftreten : (n+k-1)! / k!(n-1)! = (n+k-1 über k) : (20+3-1)/3!*(20-1)! = 1540
Wie viele "Bilder" gibt es beim Kegeln (d.h. umgefallene und stehengebliebene Kegel)?
Variation mit Wiederholung : 2^9 (9 Kegel stehend oder liegend) = 512
Wie viele Möglichkeiten für einen "Vierer" bei "6 aus 45" gibt es?
6 über 4 (4er aus möglichen 6er) * 39 über 2 (4er wurden schon gewählt jetzt muessen noch die restlichen 2 Kugeln berücksichtig werden ohne 6er) = 11115
Grupoid (algebraische Struktur)
Eine binäre Operation ° auf eine nicht leere Menge A ist eine Abbildung der Art A×A -> A. Je zwei Elemente a,b ∈ A wird ein Element a ° b zugeordnet. Das Paar (A,°) heißt dann Grupoid (bzw. eine algebraische Struktur).
Halbgruppe
wenn sie assoziativ. Für alle a,b,c ∈ A gilt: (a°b)°c = a°(b°c)
Monoid
wenn sie assoziativ + neutrales Element besitzt. Für alle a,b,c ∈ A gilt: (a°b)°c = a°(b°c) und e ∈ A mit der Eigenschaft : e°a = a°e = a
Gruppe
wenn sie assoziativ + neutrales element + zu jedem Element ein inverses Element gibt. Für alle a,b,c ∈ A gilt: (a°b)°c = a°(b°c) und e ∈ A mit der Eigenschaft : e°a = a°e = a und a' ∈ A mit a°a' = a'°a = e, wobei e das neutrale Element ist.
kommutative(s) Gruppoid, Halbgruppe, Monoid, Gruppe ; (werden auch als auch abelsche Gruppen)
genau dann, wenn die entsprechende Struktur zusätzlich noch kommutativ ist. Also noch a,b ∈ A wobei a°b = b°a.
Untergruppe
Eine (∅) Teilment U ⊆ G einer Gruppe (G,°) heißt Untergruppe von G wenn auch (U,°) eine Gruppe ist. Geschrieben als (U,°) ≤ (G,°) bzw. U ≤ G.
Linksnebenklasse / Rechtsnebenklasse
Sei (G,°) eine Gruppe, U eine Untergruppe von G und a ∈ G. Dann heißt a°U = { a°u | u ∈ U } die Linksnebenklasse von U in G und U°a = { u°a | u ∈ U } die Rechtsnebenklasse von U in G.
Index von G nach U
Sei (G,°) eine endliche Gruppe und U ≤ G. Die Anzahl der Links- bzw. der Rechtsnebenklassen von U in G wird als Index von G nach U ( |G:U| ) bezeichnet.
Ordnung von G
Die Anzahl der Elemente einer Gruppe ( |G| ) wird als Ordnung von G bezeichnet.
Satz von Lagrange
Ist (G,°) eine endliche Gruppe, so ist die Ordnung |U| einer Untergruppe U ≤ G stets Teiler der Gruppenordnung |G|, und es gilt |G:U| = |G| / |U|.
Normalteiler
Eine Untergruppe N einer n Gruppe G heißt Normalteiler, wenn die Links- und Rechtsnebenklassen übereinstimmen. Es wird dann die Kurzschreibweise N ⊴ G.
Homomorphismus
Eine Abbildung φ : G -> H zwischen zwei Gruppen (G,°) und (H,*) heißt Homomorphismus (oder Gruppenhomomorphismus), wenn für alle a,b ∈ G gilt

φ(a°b) = φ(a)*φ(b).

Isomorphismus
Ist eine Abbildung φ : G -> H zwischen zwei Gruppen (G,°) und (H,*) ( alle a,b ∈ G | φ(a°b) = φ(a)*φ(b) ) bijektiv, so heißt φ Isomorphismus. Die inverse Abbildung φ^-1 : H -> G ist dann auch ein Isomorphismus. G und H sind dann Isomorph (G ≅ H).
Kern
Sei φ : G -> H ein Gruppenhomomorphismus. Das Urbild φ^-1({eH}) des neutralen Elements eH wird als Kern bezeichnet. ker(φ) = { a ∈ G | φ(a) = eH }

Weiters nennt man φ(G) = { b ∈ H | ∃ a ∈ G : φ(a) = b } Bild von G unter φ.

Homomorphiesatz
Sei φ : G -> H ein Gruppenhomomorphismus. Dann ist die Faktorgruppe G/ker(φ) zum Bild φ(G) isomorph:
G/ker(φ) ≅ φ(G)
Ring
Eine algebraische Struktur (R,+,*) heist Ring, wenn die folgenden drei Eigenschaften erfüllt sind.

- (R,+) ist eine kommutative Gruppe (mit n.E. 0) - (R,*) ist eine Halbgruppe - es gelten die Distributivgesetze

Ring mit Einselement / kommutativer Ring
Besitzt ein Ring (R,+,*) bezüglich * ein neutrales Element, dann nennt man R einen Ring mit Einserelement. Ist R bezüglich * kommutativ, dann nennt man R einen kommutativen Ring.
Integritätsring
Ein kommutativer Ring mit einserelement ohne Nullteiler heißt Integritätsring.
Nulteiler
In einem Ring kann das Produkt zweier von 0 verschiedener Elemente dennoch 0 sein. Zum Beispiel in Z6. Restklasse 2 * Restklasse 3. Man nennt die von Null verschiedenen Elemente die dennoch als Produkt Null ergeben Nullteiler.
Körper
Ein kommutativer Ring (K,+,*) mit Einserelement 1 ≠ 0, in dem jedes Element a ≠ 0 eine Einheit ist, also ein multiplikatives Inverses besitzt, heißt Körper.
Verband
Eine algebraische Struktur (M,∧,∨) heißt Verband, wenn folgende Eigenschaften erfüllt sind.

- (M,∧) ist eine kommutative Halbgruppe - (M,∨) ist eine kommutative Halbgruppe - es gelten die Verschmelzungsgesetze a = a∧(a∨b), a = a∨(a∧b) für alle a,b ∈ M.

distributiver Verband
Ein Verband (M,∧,∨) heißt distributiver Verband, wenn die Distributivgesetze

a = a∧(a∨b) = (a ∧ b) ∨ (a ∧ c) a = a∨(a∧b) = (a ∨ b) ∧ (a ∨ c) für alle a,b,c ∈ M gelten.

Boole'sche Algebra
Ein distributiver Verband (M,∧,∨) heißt Boole'sche Algebra, wenn er die folgenden beiden zusätzlichen Eigenschaften besitzt.

- Es gibt ein neutrales Element 1 ∈ M bezüglich ∧, und es gibt ein neutrales Element 0 ∈ M bezüglich ∨ ( (M,∧) (M,∨) sind Monoide ).

Vektorraum bzw. linearer Raum
K ein Körper, (V,+) eine abelsche Gruppe, weiters werde jedem λ∈K und x∈V ein Produkt λ*x∈V zugeordnet.

Die algebraische Struktur (V,+,K) heißt Vektorraum oder linearer Raum über K, wenn folgende Eigenschaften, für alle λ,μ∈K und x,y∈V erfüllt sind. - λ*(x+y) = λ*x + λ*y - (λ+μ)*x = λ*x + μ*x - (λμ)*x = λ*(μ*x) - 1*x = x

schlichter (einfacher) Graph
Ein Graph G = (V, E) heist schlicht bzw. einfach, wenn G keine Schlingen und keine Mehrfachkanten enthält
Adjazenzmatrix
Sei G ein Graph mit Knotenmenge V(G) = {v1,v2,...,vn}. Die Adjazenzmatrix A(G) = (aij) ist eine quadratische n×n Matrix mit ...

aij = {1 für (vi,vj) ∈ E(G) bzw. vivj ∈ E(G), 0 sonst. }

zusammenhängender Graph
Ein ungerichteter Graph heißt zusammenhängend, wenn es zwischen je zwei Knoten v,e ∈ V(G) eine Kantenfolge von v nach w gibt. Die maximalen zusammenhängenden Teilgraphen eines ungerichteten Graphen G heißen (Zusammenhangs-) Komponenten von G
stark zusammenhängender Graph
Ein gerichteter Graph G heißt stark zusammenhängend, wenn für je zwei verschiedene Knoten v,w ∈ V(G) eine (gerichtete) Kantenfolge von v nach w existiert.
schwach zusammenhängender Graph
Ein gerichteter Graph G heißt schwach zusammenhängend, wenn für je zwei verschiedene Knoten v,w ∈ V(G) eine Kantenfolge existiert, die bei Missachtung der Richtung der Kanten v und w verbindet.
Wald und Baum Graphen
Ein schlichter ungerichteter Graph W, der keine Kreise positiver Länge enthält, heißt Wald. Ein Wald T, der zusammenhängend ist, heißt Baum.
spannender Baum
Ein spannender Baum T eines schlichten ungerichteten zusammenhängenden Graphen G ist ein Baum mit V(T) = V(G) und E(T) ⊆ E(G). Er enthält die selben Knoten wie G aber nur gewisse Kanten von G.
spannender Wald
Ein Gerüst bzw. spannender Wald W eines schlichten ungerichteten Graphen G ist ein Wald mit V(W) = V(G) und E(E) ⊆ E(G) und denselben zusammenhangskomponenten wie G.
minimales Gerüst
Ist ein Graph G ein bewerteter Graph, dann bezeichnet man ein Gerüst W als ein minimales Gerüst, wenn die Summe aller Kantengewichte des Gerüstes unter allen möglichen Gerüsten von demselben Grathen die kleinstmögliche ist.
Kruskal-Algorrithmus Implementation
- nummerieren der Kanten E = {e1,e2...,en} nach steigendem Gewicht

- Setze E' := 0 und j := 1 - ist der Graph (V,E' ⋃ {e1}) kreisfrei, dann E' := E' ⋃ {e1} setzen - ist j = |V| - 1 oder j = m dann beenden und W = (V,E') ist ein minimales Gerüst von G. Ansonsten setze j := j + 1 und weiter mit schritt 3.

Linearkombination
Seien v1,v2,...,vn Elemente eines Vektorraums V (über dem Körper K) und λ1,λ2,...λn ∈ K. Dann heißt die Summe

λ1*v1 + λ2*v2 + ... λn*vn Linearkombination der Vektoren v1,v1 bis vn. Die Skalare λ1,λ2,...,λn heißen Koeffizienten der Linearkombination.

triviale Linearkombination
Eine Linearkombination heißt trivial, wenn alle koeffizienten λi = 0 sind (1 ≤ i ≤ n) ansonsten heißt sie nichttrivial.
lineare Hülle
Die Lineare Hülle einer nichtleere Teilmenge M von einem Vektorraum V ist die Menge aller Vektoren, welche durch Linearkombinationen von (endlich vielen) Vektoren aus M gebildet werden können. Weiters wird [∅] = {0} gesetzt.
linear unabhängig
Eine Menge M von Vektoren heißt linear unabhängig, wenn kein Vektor aus M als Linearkombination anderer Vektoren aus M dargestellt werden kann. Für alle v ∈ M gilt also: v ∉ [M \ {v}]. Ansonsten heißt eine Menge M von Vektoren linear abhängig: v ∈ [M \ {v}].
Basis eines Vektorraums
Eine Teilmenge B eines Vektorraums V heißt Basis von V, wenn sie linear unabhängig ist und ihre lineare Hülle [B] gleich V ist. Jeder Vektor x lässt sich eindeutig als Linearkombination von Vektoren der Basis darstellen. Die Koeffizienten dieser Linearkombination werden als Koordinaten von x bezüglich der Basis B bezeichnet.
transponierte Matrix
Ist A ∈ K^m×n eine m×n Matrix, so bezeichnet man mit A^T die zu A transponierte Matrix. Sie ist eine n×m Matrix und geht aus A dadurch hervor, dass Zeilen und Spalten vertauscht werden. Die erste Spalte von A ist die erste Zeile von A^T usw.
symmetrische Matrix
Eine quadratische Matrix A ∈ K^n×n heißt symmetrisch, wenn A^T = A ist.
Einheitsmatrix In
Unter einer n-dimensionale, n≥1 ∈ Z, Einheitsmatrix In ∈ K^n×n versteht man die Matrix ...
100...00
010...00

( ............ )

000...10
000...01 

die Spalten sind wie die Vektoren e1...en der Kanonischen basis.

invertierbar bzw. regulär
Sei A ∈ K^n×n eine quadratische Matrix. Sie heißt invertierbar oder regulär, wenn es eine Matrix A^-1 ∈ K^n×n gibt mit A*A^-1 = A^-1*a = In

Die Matrix A^-1 heißt dann die zu A inverse Matrix. Nicht invertierbare Matrizen werden auch als singulär bezeichnet.

lineare Abbildung zwischen Vektorräumen
Eine Abbildung f : V -> W zwischen zwei Vektorräumen V und W (über demselben Körper K) ist linear, wenn sie die folgenden beiden Eigenschaften (für x,y ∈ V und λ ∈ K hat.

- f(x+y) = f(x) + f(y) - f(λ*x) = λ*f(x)

Kern und Bild
Sei f : V -> W eine lineare Abbildung. Die Mengen

ker(f) = {x ∈ V : f(x) = 0} und f(V) = {f(x) : x ∈ V} heißen Kern und Bild von f. Die Dimension des Kerns und des Bildes sind der Defekt und der Rang von f: def(f) = dim(ker(f)) und rg(f) = dim(f(V))

Determinante
|a11 a12|

|a21 a22| = a11a22 -a12a21

|a11 a12 a13| |a21 a22 a23| = a11a22a33 + a12a23a31 + a13a21a32 |a31 a32 a33| - a13a22a31 - a12a21a33 - a11a23a32

Eigenwert - Skalar
Sei f : V -> V eine lineare Abbildung. Ein Skalar λ ∈ K heißt Eigenwert von f, wenn es einen Vektor x ∈ V \ {0} mit f(x)=λ*x gibt.

Sei A ∈ K^n×n eine Quadratische Matrix. Ein Skalar λ ∈ K heißt eigenwert von A, wenn es einen Vektor x ∈ K^n\{0} mit A*x = λ*x gibt.

Eigenvektoren
Die Vektoren x ∈ V \ {0} mit f(x) = λ*x heißen die zum Eigenwert λ gehörigen Eigenvektoren.

Sei A ∈ K^n×n eine Quadratische Matrix. Die Vektoren x ∈ K^n\{0} mit A*x = λ*x heißen die zum Eigenwert λ gehörigen Eigenvektoren.

Eigenwert einer Matrix bestimmen
det(λ*I2 - A)

(1 2 2 2) = A |λ-1 -2| |-3 λ-2| = λ^2 - 3λ - 4 => zwei Lösungen: λ = 4; λ = -1 Die Eigenwerte von A sind 4 und -1.

Eigenvektor zum Eigenwert
(4*I2 - A) * x

(3 -2 -3 2) * x = 0 Nach auflösen der lin. Gleichung x1 = (2 3) für λ = 4 x2 = (1 -1) für λ = -1

Skalarprodukt
Das gewöhnliche Skalarprodukt <x,y> zweier Vektoren ist gegeben durch <x,y> = x1y1 + x2y2 + ... + xn,yn.

Die Vektoren x,y heißen orthogonal (sie steh im rechten Winkel zu einander), wenn das Skalarodukt = 0 ist.

Determinante Definition
Die Determinante ist eine spezielle Funktion mit der man feststellen kann, ob ein lineares Gleichungssystem lösbar ist (Det ≠ 0).

- Für nichtquadratische Matrizen ist die Determinante nicht definiert. - Die Determinante ist eindeutig. Die Determinante einer reellen Matrix beschreibt das orientierte (d.h. mit einem Vorzeichen versehenen) Volumen des Parallelotops (Parallelepipeds).

U ist die durch (123) gebildete Untergruppe von S3
alle sich in der Untergruppe U befindlichen Elemente können durch das Element (123) mit der Operation ° bei mehrfacher Ausführung dieser erzeugt werden.
Der Satz von Lagrange
(U ist die durch (123) gebildete Untergruppe von S3)

|S3| = |U|*|S3:U| -> da |S3| = 6 und |U| = 3 -> der Index |S3:U| = 2

Berechnung LNK (U ist die durch (123) gebildete Untergruppe von S3)
Ein Element aus S3 auswählen, welches nicht auch schon ein Element aus U ist. Gewähltes a=(1)(23) und dann ...

LNK = {a°U | a∈S3 ∧∀u ∈ U} wobei a ≠ u

Berechnung Normalteiler (U ist die durch (123) gebildete Untergruppe von S3)
a°U = U°a | a∈S3 ∧∀u ∈ U wobei a ≠ u
Berechnung RNK (U ist die durch (123) gebildete Untergruppe von S3)
Ein Element aus S3 auswählen, welches nicht auch schon ein Element aus U ist. Gewähltes a=(1)(23) und dann ...

LNK = {U°a | a∈S3 ∧∀u ∈ U} wobei a ≠ u

Wie viele Diagonalen hat ein regelmäßiges Vieleck
n(n-3)/2
Sei Kn der vollständige Graph mit 66 Kanten und n Knoten. Wie groß ist n
n(n-1)/2 = 66 -> n(n-1) = 132 -> 12*12 = 144 -> 12*11 = 132 also n=12
eigen Sie, daß es in jeder Stadt mindestens zwei Bewohner mit der gleichen Anzahl von Nachbarn gibt
Angenomen 3 Personen haben eine unterschiedliche anzahl Nachbarn. Dann hatt eine der Personen n-1 nachbarn und somit ist sie ein Nachbar von der Person die keine Nachbarn hat. Was ein wiederspruch ist.
31 Freunde vereinbaren, daß jeder von ihnen an 15 andere Ansichtskarten schicken. Untersuchen Sie, ob das so geschehen kann, daß jeder denjenigen schreibt, die auch ihm geschrieben haben
jeder schreibt an 15 andere : Knotengrade 31*15. Jere schreibt an den zurüch der an ihn geschrieben hat... bedeutet das es Knotengrade / 2 ungerichtete Kanten gibt : 465 / 2 -> halbe Kante gibt es nicht.
Wann nennt man G zyklisch?
Eine Gruppe G heißt zyklisch, falls ein b∈G existiert mit
G={b^n ∣ n ∈ ℤ}

b heißt Erzeuger oder erzeugendes Element von G.

Sind zyklische Gruppen immer abelsch?
Ja.

<a> eurzeugte Zyklische Gruppe -> y=a^n ; x= a^m y*x = a^n*a^ m = a^n+m = a^m+n = a^m * a^n = x*y

Wie lassen sich jene Graphen charakterisieren, die Bäume sind?
(1) kreisfrei und zusammenhängend

(2) kreisfrei und maximal bzgl. der Inklusion auf der Kanten menge

begründen der Aquivalen von

(1) kreisfrei und zusammenhängend (2) kreisfrei und maximal bzgl. der Inklusion auf der Kanten menge

(1)⇒(2): Gibt man in einem kreisfreien, zusammenhängenden Graphen eine Kante (x, y) dazu, so entsteht ein Kreis, da ja x und y

bereits vorher durch einen Weg miteinander verbunden waren. (2)⇒(1): Ist G ein maximaler kreisfreier Graph, so muß er auch zusammenhängend sein. Andernfalls könnte man zwei verschiedene Zusammenhangskomponenten durch eine Kante verbinden, ohne daß ein Kreis entstünde, was der Maximalität entsprich.

Wie viele Diagonalen hat ein regelmäßiges Elfeck
n(n-3)/2 = 44
Sei A = {1, 4, 9, 16, 25, . . . } die Menge aller Quadratzahlen, B die Menge aller ganzen Zahlen, die Potenzen von 3 sind
Geben Sie die Mengen A und B in "mathematischer Notation" an.
A:= { n∈N | ∃k∈N : n=k² }
B:= { n∈N | ∃k∈N : n=3^k}