Injektivität zeigen (Graphentheorie)

05.12.2013, 19:06	Tenacious	Auf diesen Beitrag antworten »
Injektivität zeigen (Graphentheorie) Hallo, es geht um folgende Aufgabe: "Es sei $\begin{eqnarray} f: E \rightarrow E \end{eqnarray}$ eine partielle Funktion und $\begin{eqnarray} G_f = (E,K_f) \end{eqnarray}$ der dazugehörige Graph, wobei $\begin{eqnarray} K_f = \{ (x,f(x)) : x \in dom(f) \} \end{eqnarray}$ . Zeigen Sie, dass $\begin{eqnarray} f \end{eqnarray}$ genau dann injektiv ist, wenn $\begin{eqnarray} indeg(e) \leq 1 \end{eqnarray}$ für alle $\begin{eqnarray} e \in E \end{eqnarray}$ gilt." Grundsätzlich ist die Behauptung ja logisch, denn wenn jeder Ecke maximal nur eine Kante zugeordnet wird dann ist die Funktion injektiv. Aber wie zeige ich das formal?
06.12.2013, 12:29	jimmyt	Auf diesen Beitrag antworten »
Hi, eine Möglichkeit wäre einen indirekten Beweis zu machen. Dabei bildest du die Negation $\begin{eqnarray} \neg S \end{eqnarray}$ der Ursprungsaussage $\begin{eqnarray} S \end{eqnarray}$ und führst diese zu einem Widerspruch. Dadurch weißt du, daß $\begin{eqnarray} \neg S ~=~ \text{false} \end{eqnarray}$ und damit $\begin{eqnarray} \neg \neg S ~=~ S ~=~ \text{true} \end{eqnarray}$ ist. Also in diesem Fall: $\begin{eqnarray} S: \quad \forall_{e \in E}: indeg(e) \leq 1 ~\Longleftrightarrow~ f \text{ ist injektiv} \end{eqnarray}$ $\begin{eqnarray} \neg S: \quad \dots \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »