Hilfe:Algebra und Diskrete Mathematik

Grundlagen

Zahlen

Peano-Axiome

1. 0 (Null) ist eine natürliche Zahl
2. Jede natürliche Zahl n hat genau einen Nachfolger
3. 0 ist nicht Nachfolger einer natürlichen Zahl
4. Verschiedene natürliche Zahlen besitzen verschiedene Nachfolger
5. Jede Eigenschaft, welche 0 zukommt und sich von jeder natürlichen Zahl auf den Nachfolger überträgt, kommt bereits allen natürlichen Zahlen zu

Vollständige Induktion

1. Induktionsanfang (IA)
2. Induktionsschritt (IS): Induktionsvoraussetzung (IV) $\Rightarrow$ Induktionsbehauptung (IB)

Relationen

Äquivalenzrelation

Symmetrie, Transitivität und Reflexivität, eine Äquivalenzklasse ist eine von einem Element a erzeugte Menge aus b's, in der alle a's in Relation zu b stehen wobei die Relation eine Äquivalenzrelation ist.

Halbordnungsrelation

Antisymmetrie, Transitivität, Reflexivität, eine Halbordnung ist eine Totalordnung wenn je zwei ihrer Elemente vergleichbar sind.

Partition

Eine Partition einer Menge ist eine Zerlegung dieser Menge in nichtleere paarweise disjunkte Teilmengen. (keine Elemente der Teilmengen dürfen gleich sein) Eine Partition {M} einer Menge M nennt man die triviale Partition.

Die verschiedenen Äquivalenzklassen der Elemente von A bilden immer eine Partition von A.--> Äquivalenzklassen

Funktionen

injektiv

zu jedem b gibt es höchstens ein a, wo $a\rightarrow b$. Es gilt: $\forall x_{1},x_{2}:f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}$

surjektiv

zu jedem b gibt es mindestens ein a, wo $a\rightarrow b$.

bijektiv

zu jedem b gibt es genau ein a, wo $a\rightarrow b$. (Surjektiv und Injektiv; impliziert Umkehrfunktion)

Diskrete Mathematik

Graphentheorie

Zwei Kanten heißen adjazent (benachbart), wenn sie einen gemeinsamen Knoten besitzen.

Ein Graph heißt planar, wenn seine Knoten und Kanten so in einer Ebene liegen, daß sich zwei Kanten nur in einem Knoten kreuzen.

Ein Kreis (ungerichtet) oder Zyklus (gerichtet) ist ein geschlossener Kantenzug, bei dem bis auf Anfangs- und Endknoten alle Knoten verschieden sind.

Knotengrad

Die Anzahl der Kanten, die zu einem Knoten inzident sind (dort zusammentreffen), heißt Grad des Knoten.

vollständig

Sind in einem Graphen je zwei verschiedene Knoten durch eine Kante verbunden, so heißt der Graph vollständig.

Ein Graph heißt zusammenhängend, wenn sich je zwei verschiedene Knoten durch zumindest einen Weg miteinander verbinden lassen. Ein isolierter Teilgraph ist ein Teil eines Graphen ohne direkte Kantenverbindung zu diesem.

Kantenfolge

Eine Kantenfolge in einem Graphen ist eine endliche Folge von Kanten, sodaß je zwei aufeinanderfolgende Kanten einen Knoten gemeinsam haben. Die Kantenfolge ist offen, wenn Anfangs- und Endpunkt nicht identisch sind, sonst heißt sie geschlossen.

Kantenzug

Dies ist eine Kantenfolge, in der keine Kante mehrfach auftritt.

Weg

Ein Weg oder eine Bahn ist eine offene Kantenfolge, in der außerdem alle Knoten verschieden sind.

Handschlaglemma

Summe der Grade(v) = 2 * |E|
die Summe der Grade aller Knoten eines Graphen ist genau doppelt so groß wie die Anzahl seiner Knoten, daraus kann man folgern, dass jeder Graph eine gerade Anzahl von Knoten mit ungeradem Knotengrad hat

Baum

Ein Graph heißt Baum, wenn gilt, dass für je zwei seiner Knoten nur jeweils ein Weg existiert, der diese Knoten verbindet. Ist ein Baum vollständig, so ist die Zahl der Kanten immer um eins geringer als die Zahl der Knoten (E = V-1).

Ist ein spannender Teilgraph G1 eines Graphen G zugleich Baum, so spricht man von einem spannenden Baum oder einem Gerüst.

Besteht ein Baum nur aus gerichteten Kanten und existiert ein einziger Knoten, zu dem keine Kante führt, so spricht man von einem Wurzelbaum oder Aboreszenz. Knoten von denen keine Kante wegführt, nennt man Endknoten oder Blätter.

Euler'sche Linie

Eine Kantenfolge in einem Graphen die jeden Knoten und jede Kante enthält und zwar jede Kante nur genau einmal. Man unterscheidet zwischen geschlossen und offen. Ein eulersch'er Graph ist einGraph der eine euler'sche Linie enthält.

Hamilton'sche Linie

Eine Kantenfolge in einem Graphen die jeden Knoten genau einmal enthält. Man unterscheidet zwischen geschlossen und offen. Ein hamilton'sche Graph ist ein Graph der eine hamilton'sche Linie besitzt.

Euler'sche Polyederformel

x0(G) – x1(G) + x2(G) = 2
x0 = Anzahl der Eckpunkte; x1= Anzahl der Kanten; x2 die Anzahl der Flächen des Polyeders

Algebraische Strukturen

Gruppoid (=binäre algebraische Struktur)

abgeschlossen bezüglich der definierenden binären Operation der Struktur

Halbgruppe

+ assoziativ = abgeschlossen, assoziativ

Monoid

+ neutrales Element = abgeschlossen, assoziativ, neutrales Element

Gruppe

+ inverse Elemente = abgeschlossen, assoziativ, neutrales Element, inverse Elemente

können kommutative Halbgruppe/Monoid/Gruppe sein wenn sie das Kommutativgesetz erfüllen, kommutative Gruppen werden auch abel'sche Gruppen genannt.

Zyklische Gruppe

eine Gruppe die von einem einzelnen Element a erzeugt wird. Sie besteht aus allen Potenzen von a.

Ring

Ring

Ein Ring $(R,+,\cdot )$ ist eine Menge $R$ mit zwei binären Operationen $+$ und $\cdot$, sodass

• $(R,+)$ eine kommutative Gruppe ist,
• $(R,\cdot )$ eine Halbgruppe ist,
• die Distributivgesetze

$a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ und

$(a+b)\cdot c=(a\cdot c)+(b\cdot c)$

für alle $a,b,c\in R$ gelten.

Lineare Algebra

Matrizen

transponierte Matrix

Mit $A^{T}$ bezeichnet man die zu A transponierte Matrix. Sie geht daraus hervor, dass Zeilen und Spalten von A vertauscht werden.

Eine Matrix ist invertierbar (regulär) wenn die Determinante nicht 0 ist. Nicht invertierbare Matrizen werden auch als singulär bezeichnet.

Eigenwerte

Sei $A\in K^{n\times n}$ eine quadratische Matrix. Zur Bestimmung der Eigenwerte $\lambda _{1},...,\lambda _{n}$ setze: $det(A-\lambda *I_{n})=0$, ($I_{n}$... Einheitsmatrix der Dimension $n$, Dimension der Matrix A = Anzahl ihrer maximalen Eigenwerte). Zur Bestimmung der Eigenvektoren $x$ zum Eigenwert $\lambda _{i}$setze: $det(A-\lambda _{i}*I_{n})*x=0$.

4x4 Matrix Determinante:

Unsere Matrix M in vier 3x3 Matrizen aufteilen (A,B,C,D), dann nach dem unteren Muster Vorzeichen anpassen: z.B. für die erste Zeile: det(M) = det(A) - det(B) + det(C) - det(D) .

${\begin{bmatrix}+&-&+&-&\cdots \\-&+&-&+&\cdots \\+&-&+&-&\cdots \\-&+&-&+&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{bmatrix}}$

Operationen auf Matrizen:

• Addition: einzelne Werte am selben Index miteinander addieren
• Multiplikation: nicht kommutativ, MxN einzelne Werte von N mit zugehöriger Spalte in M jeweils multiplizieren und dann aufsummieren.
• Transponieren: Zeilen und Spalten vertauschen
• Invertieren: wenn Determinante ungleich 0, A*A' = A'*A= e (e = Einheitsmatrix)

Zur Bestimmung der inversen Matrix schreibt man die Matrix A und die Einheitsmatrix I übereinander (oder nebeneinander). Nun formt man A mithilfe von ausschließlich Spaltenumformungen (oder ausschließlich Zeilenumformungen) auf die Einheitsmatrix um. Die Umformungen wendet man dabei jeweils auch auf die darunter-(oder daneben-)stehende Matrix I an. Wenn A fertig auf die Einheitsmatrix geformt wurde, steht an der Stelle von I die Inverse Matrix A'.

Differenzengleichungen

Eine Differenzengleichung heißt linear, wenn sie in der Form

   f0(n)yn + f1(n)yn−1 + . . . + fk(n)yn−k = s(n)

geschrieben werden kann. Hängen die Koeffizienten nicht von n ab, so heißt die Differenzengleichung linear mit konstanten Koeffizienten. Gilt s(n) = 0, so heißt die Differenzengleichung homogen sonst inhomogen.

Die allgemeine Lösung obiger Differenzengleichung ist gegeben durch die Summe der allgemeinen Lösung der homogenen und einer partikulären Lösung der inhomogenen Gleichung.