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

• → https://quizlet.com/18302024/mathematik-f-wi-1-flash-cards/

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}