FAQs – Mathematik
Können 2 Graphen zueinander 2 Homomorphismen haben ohne isomorph zu sein?
Zwei Graphen können zueinander 2 Homomorphismen haben ohne isomorph zu sein.
Definition:
Seien \(G_1 = (V_1, E_1)\) und \(G_2 = (V_2, E_2)\) zwei ungerichtete Graphen. Eine Abbildung \(f: V_1 \to V_2\) heißt Homomorphismus zwischen \(G_1\) und \(G_2\), wenn gilt: Ist \(\{u, v\}\) eine Kante von \(G_1\), dann ist \(\{f(u), f(v)\}\) eine Kante von \(G_2\).
Seien \(G_1 = (V_1, E_1)\) und \(G_2 = (V_2, E_2)\) zwei ungerichtete Graphen. Eine bijektive Abbildung \(f: V_1 \to V_2\) heißt Isomorphismus zwischen \(G_1\) und \(G_2\), wenn gilt: \(\{u, v\}\) ist eine Kante von \(G_1\), genau dann wenn \(\{f(u), f(v)\}\) eine Kante von \(G_2\) ist.
Beispiel:
Seien \(G_1\) und \(G_2\) zwei Graphen:
G1: G2:
0----1 f
-----> 4----5
<-----
2----3 g
Ein Beispiel für einen Homomorphismus \(f\) von \(G_1\) nach \(G_2\) ist:
\(f(0) = f(2) = 4,\quad f(1) = f(3) = 5\).
\(f\) ist ein Homomorphismus von \(G_1\) nach \(G_2\) weil gilt:
\(\{0, 1\} \in G_1 \Rightarrow \{f(0), f(1)\} = \{4, 5\} \in G_2\)
\(\{2, 3\} \in G_1 \Rightarrow \{f(2), f(3)\} = \{4, 5\} \in G_2\)
Ein Beispiel für einen Homomorphismus \(g\) von \(G_2\) nach \(G_1\) ist:
\(g(4) = 2,\quad g(5) = 3\).
\(g\) ist ein Homomorphismus von \(G_2\) nach \(G_1\) weil gilt:
\(\{4, 5\} \in G_2 \Rightarrow \{g(4), g(5)\} = \{2, 3\} \in G_1\)
Es gibt zwischen \(G_1\) und \(G_2\) in jede Richtung einen Homomorphismus, \(G_1\) und \(G_2\) sind aber nicht isomorph. Die Mengen der Kanten \(V(G_1)\) und \(V(G_2)\) sind nicht gleich mächtig. Daher gibt es keine bijektive Abbildung zwischen \(G_1\) und \(G_2\).
Weitere Informationen.
Sind Binärbäume Graphen?
Ja, Binärbäume sind Graphen.
Besondere Eigenschaften solcher Graphen sind:
- Ein Knoten ist als Wurzelknoten ausgezeichnet.
- Binärbäume sind zusammenhängende Graphen.
- Binärbäume enthalten keine geschlossenen Pfade.
Weitere Informationen.
Was ist 0^0?
Zur Beantwortung dieser Frage gibt es unterschiedliche Ansätze:
Die Funktion \(f(x, y) = x^y\) ist an der Stelle \((0, 0)\) divergent. Der Grenzwert \(\lim \limits_{(x, y) \to (0, 0)} x^y\) existiert nicht. Daher wird \(0^0\) oft als unbestimmter Ausdruck gesehen (vgl. \(\frac{0}{0}, \frac{\infty}{\infty}\), …).
Der Grenzwert \(\lim \limits_{x \to 0+} x^0 = 1\) existiert. Daher, und aus praktischen Überlegungen (Berechnung von Potenzreihen, …) definiert man oft \(0^0 = 1\).
In vielen Programmiersprachen, darunter auch Java (java.lang.Math) gilt: \(0^0 = 1\).
Die auf Mathematica basierende Online-Anwendung Wolfram-Alpha liefert als Ergebnis undefined.
Was ist ein Homomorphismus (Graphen)?
Ein Homomorphismus ist eine Abbildung zwischen zwei Graphen desselben Typs (gerichtet / ungerichtet).
Definition:
Seien \(G_1 = (V_1, E_1)\) und \(G_2 = (V_2, E_2)\) zwei ungerichtete Graphen. Eine Abbildung \(f: V_1 \to V_2\) heißt Homomorphismus zwischen \(G_1\) und \(G_2\), wenn gilt: Ist \(\{u, v\}\) eine Kante von \(G_1\), dann ist \(\{f(u), f(v)\}\) eine Kante von \(G_2\).
Beispiel:
Seien \(G_1\) und \(G_2\) zwei Graphen:
G1: G2:
0----1 f
-----> 4----5
2----3
Ein Beispiel für einen Homomorphismus \(f\) von \(G_1\) nach \(G_2\) ist:
\(f(0) = f(2) = 4,\quad f(1) = f(3) = 5\).
Folgende Behauptungen sind wahr:
\(\{0, 1\}\) ist eine Kante von \(G_1\), also ist \(\{f(0), f(1)\} = \{4, 5\}\) eine Kante von \(G_2\).
\(\{2, 3\}\) ist eine Kante von \(G_1\) ist, also ist \(\{f(2), f(3)\} = \{4, 5\}\) eine Kante von \(G_2\).
Daher ist \(f\) ein Homomorphismus von \(G_1\) nach \(G_2\).
Neben den Homomorphismen zwischen ungerichteten Graphen gibt es auch Homomorphismen zwischen gerichteten Graphen, Graphen mit Mehrfachkanten, …
Weitere Informationen.
Was ist injektiv und was ist surjektiv (Funktion)?
Die Begriffe injektiv und surjektiv können ganz allgemein auf Relationen angewendet werden. Oft werden sie auf Funktionen angewendet.
Funktion
Eine Funktion \(f\) ordnet jedem Element \(x\) der Definitionsmenge \(X\) genau ein Element \(y\) der Zielmenge \(Y\) zu. D. h. \(f: X \rightarrow Y, \,\, x \mapsto y\)
Injektiv
Eine Abbildung \(f: X \rightarrow Y\) ist injektiv (linkseindeutig), wenn gilt: \(f(x_1) = f(x_2) \Rightarrow x_1 = x_2\).
In \(Y\) gibt es kein Element, auf das mehr als ein Element aus \(X\) abgebildet wird. Man spricht deswegen von Linkseindeutigkeit.
Surjektiv
Eine Abbildung \(f: X \rightarrow Y\) heißt surjektiv, wenn jedes Element der Zielmenge \(Y\) mindestens einmal als Funktionswert von \(f\) vorkommt.
Definition: \(\forall y \in Y \quad\exists x \in X: f(x) = y\).
Beispiel
Die Funktion \(f: X \rightarrow Y, \,\, x \mapsto x^2\) hat abhängig von der Definitions- und Zielmenge unterschiedliche Eigenschaften:
- \( X = \mathbb{R}, Y = \mathbb{R}\):
\(f\) ist nicht injektiv, weil es in \(Y\) ein Element gibt, auf das mehr als ein Element aus \(X\) abgebildet wird.
Z. B. \(f(2) = f(-2) = 4\)
\(f\) ist nicht surjektiv, weil nicht jedes Element der Zielmenge \(Y\) als Funktionswert von \(f\) vorkommt.
Z. B. Es gibt kein Element aus \(X\), das auf \(-1\) abbildet. - \( X = \mathbb{R}, Y = \mathbb{R}_0^+\):
\(f\) ist nicht injektiv.
\(f\) ist surjektiv, weil jedes Element der Zielmenge \(Y\) als Funktionswert von \(f\) vorkommt. - \( X = \mathbb{R}^+, Y = \mathbb{R}\):
\(f\) ist injektiv, aber nicht surjektiv. - \( X = \mathbb{R}^+, Y = \mathbb{R}^+\):
\(f\) ist injektiv und surjektiv und daher bijektiv.
Wie multipliziere ich im 2er-Komplement?
Im Prinzip wird im Zweier-Komplement genauso multipliziert, wie bei positiven Zahlen. Es ist nur zusätzlich zu berücksichtigen, dass negative Zahlen durch führende Einser auf die für die Summenbildung notwendige Länge ergänzt werden.
Im folgenden Beispiel sind beide Faktoren 4 Bit lang. Für das Ergebnis muss man daher 8 Bit reservieren.
Beispiel: -7 * 5
Im ersten Schritt wird von +7 das Zweier-Komplement gebildet:
0111 // 7 1000 // Bits invertiert 1001 // Bits invertiert + 1
Multiplikation mit +5:
1001 * 0101 ------------ 00000 111001 0000000 11111001 ============ 111011101
Probe – Darstellung von -7 * 5 = -35 im Zweier-Komplement:
0010 0011 // 35 1101 1100 // invertiert 1101 1101 // invertiert + 1
Für weitere Information: Wikipedia, Zweierkomplement
Was sind arithmetische, logische und mathematische Operationen?
Logische Operationen haben als Ergebnis einen Wahrheitswert (true, false).
Beispiele für logische Operatoren sind: \(\wedge, \vee, \geq, \neq, …\)
Mathematische oder arithmetische Operationen arbeiten mit sogenannten mathematischen Objekten (Skalar, Vektor, Matrix, …) und Operatoren.
Beispiele für mathematische oder arithmetische Operatoren sind: \(+, -, *, /, \frac{d}{dx}, \int, …\)
Wie funktioniert der Modulo-Operator?
In Java beschreibt der %-Operator den Rest bei der Ganzzahldivision. Für positive Zahlen verhält sich der %-Operator genauso wie der aus der Mathematik bekannte mod-Operator.
Beispiel: 7 mod 5 = 2, 7 % 5 = 2
Unterschiede zwischen den beiden Operatoren ergeben sich bei negativen Zahlen. Der mod-Operator berechnet eine Restklasse.
Die möglichen Restklassen von n mod m sind 0 … m-1.
Beispiel: -7 mod 5 = 3
Der %-Operator in Java berechnet den Rest bei der Ganzzahldivision.
Beispiel: -7 % 5 = -2
Die mod-Operation kann in Java wie folgt implementiert werden:
static int mod(int n, int m) {
int r = n % m;
if (r < 0) {
r += m;
}
return r;
}