Kurs:Diskrete Mathematik/7/Klausur mit Lösungen

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	${}\sum$
Punkte	3	3	3	3	4	2	8	2	2	2	3	4	7	4	1	3	5	5	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine endliche Menge ${}M$ mit ${}n$ Elementen.
2. Ein größtes Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Zwei teilerfremde natürliche Zahlen ${}a$ und ${}b$.
4. Rechtsisomorphe Abbildungen ${}f_{1}\colon L\rightarrow M_{1}$ und ${}f_{2}\colon L\rightarrow M_{2}$ zu Mengen ${}L,M_{1},M_{2}$.
5. Ein kantenfreier Graph  ${}G=(V,E)$. 
6. Das chromatische Polynom eines Graphen ${}G$.

Lösung

1. Eine Menge ${}M$ heißt endlich mit ${}n$ Elementen, wenn es eine Bijektion

   $\{1,\ldots ,n\}\longrightarrow M$

   gibt.

2. Ein Element ${}x\in I$ heißt größtes Element von ${}I$, wenn  ${}y\preccurlyeq x$  für jedes ${}y\in I$ gilt.
3. Die beiden natürlichen Zahlen ${}a$ und ${}b$ heißen teilerfremd, wenn sie keinen gemeinsamen Teiler ${}\geq 2$ besitzen.
4. Die Abbildungen ${}f_{1}$ und ${}f_{2}$ heißen rechtsisomorph, wenn es eine bijektive Abbildung ${}\psi \colon M_{1}\rightarrow M_{2}$ mit

   ${}f_{2}=\psi \circ f_{1}\,$

   gibt.

5. Der Graph ${}G$ heißt kantenfrei, wenn die Kantenmenge ${}E$ leer ist.
6. Unter dem chromatischen Polynom ${}P_{G}$ versteht man die Funktion, die durch

   ${}P_{G}\left(k\right)={\#\left\{f:V\rightarrow \{1,\ldots ,k\}\mid f{\text{ zulässige Färbung}}\right\}}\,$

   gegeben ist.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Teilmengenanzahl einer endlichen Menge.
2. Der Satz über die Äquivalenzrelation zu einer Abbildung ${}f\colon M\rightarrow N$.
3. Der Satz von Ore.

Lösung

1. Die Anzahl der ${}k$-elementigen Teilmengen in einer ${}n$-elementigen Menge ist der Binomialkoeffizient

   ${\binom {n}{k}}.$

2. Durch die Festlegung

   ${}x\sim y\,,$

   wenn

   ${}f(x)=f(y)\,,$

   wird eine Äquivalenzrelation auf ${}M$ definiert.
3. Es sei  ${}G=(V,E)$  ein Graph mit mindestens drei Elementen, der die Bedingung

   ${}d(u)+d(v)\geq {\#\left(V\right)}\,$

   für je zwei nicht adjazente Knoten ${}u,v$ erfüllt. Dann ist ${}G$

   hamiltonsch.

Aufgabe (3 Punkte)

Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von ${}20$ Cent begleichen?

Lösung

Wir zählen zunächst die Möglichkeiten, mit den ${}5$-, ${}10$- und ${}20$-Centmünzen die folgenden Beträge darzustellen:

$0{\text{ Cent}}:1{\text{ Möglichkeit}},$

$5{\text{ Cent}}:1{\text{ Möglichkeit}},$

$10{\text{ Cent}}:2{\text{ Möglichkeiten}},$

$15{\text{ Cent}}:2{\text{ Möglichkeiten}},$

$20{\text{ Cent}}:4{\text{ Möglichkeiten}}.$

Dann betrachten wir in jedem Fall, mit wie vielen ${}2$-Centmünzen man jeweils noch unterhalb von ${}20$ Cent bleibt, der verbleibende Rest wird mit ${}1$-Centmünzen aufgefüllt. Hierfür gibt es der Reihe nach

$11,8,6,3,1{\text{ Möglichkeiten}}.$

Diese Möglichkeiten für die Zweier muss man mit den obigen Möglichkeiten multiplizieren, das ergibt insgesamt

${}1\cdot 11+1\cdot 8+2\cdot 6+2\cdot 3+4\cdot 1=11+8+12+6+4=41\,$

Möglichkeiten.

Aufgabe (3 Punkte)

Die Puzzleteile für ein Puzzle haben eine grob rechteckige Form, wobei die eine Seite erkennbar länger als die andere ist, und auf jeder Seite gibt es entweder eine Einbuchtung oder eine Ausbuchtung. Wie viele Typen von Puzzelteilen gibt es?

Lösung

Wir betrachten die Puzzleteile je nachdem, ob sie ${}0,1,2,3$ oder ${}4$ Ausbuchtungen haben (was die Anzahl der Einbuchtungen festlegt). Bei keiner Ausbuchtung gibt es keine weitere Unterscheidung. Bei einer Ausbuchtung kann die Ausbuchtung an einer kurzen oder an einer langen Seite sein. Bei zwei Ausbuchtungen gibt es vier Möglichkeiten: Die beiden Ausbuchtungen können gegenüber an den kurzen Seiten, oder gegenüber an den langen Seiten, oder nebeneinander an einer kurzen und an einer langen Seite sein. Im letzteren Fall macht es aber noch einen Unterschied, ob, wenn man die Ausbuchtung an der kurzen Seite nach oben dreht, die Ausbuchtung an der langen Seite links oder rechts liegt. Für drei Ausbuchtungen gibt es wieder zwei und bei vier Ausbuchtungen wieder eine Möglichkeit. Insgesamt gibt es also

${}1+2+4+2+1=10\,$

Typen.

Aufgabe (4 Punkte)

Beweise den Satz über die Anzahl von bijektiven Abbildungen.

Lösung

Wir führen Induktion über ${}n$, wobei der Fall  ${}n=1$  klar ist. Die Aussage sei nun für ${}n$ schon bewiesen und es liegen zwei ${}(n+1)$-elementige Mengen ${}M$ und ${}N$ vor. Es sei  ${}x\in M$  ein fixiertes Element. Dann gibt es für die Werte ${}\varphi (x)$ genau ${}n+1$ Möglichkeiten, nämlich die Anzahl der Menge ${}N$. Wenn dies festgelegt ist, so entsprechen die bijektiven Abbildungen von ${}M$ nach ${}N$ mit

${}\varphi (x)=y\,$

den bijektiven Abbildungen von ${}M\setminus \{x\}$ nach ${}N\setminus \{y\}$. Nach Induktionsvoraussetzung gibt es ${}n!$ solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen ${}M$ und ${}N$ gleich

${}(n+1)\cdot n!=(n+1)!\,.$

Aufgabe (2 Punkte)

Beweise den Satz über die Lösbarkeit von Gleichungen in einer Gruppe ${}G$.

Lösung

Wir betrachten die linke Gleichung. Aus beidseitiger Multiplikation mit ${}a^{-1}$ von links folgt, dass nur

${}x=a^{-1}\circ b\,$

als Lösung in Frage kommt. Wenn man dies einsetzt, so sieht man, dass es sich in der Tat um eine Lösung handelt.

Aufgabe (8 (1+2+3+2) Punkte)

Wir betrachten eine (einfachere, aber langsamere) Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen ${}a,b$.

Der Algorithmus geht folgendermaßen. Wenn  ${}a\neq b$  ist, so ersetze das Paar ${}(a,b)$ durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn  ${}a=b$  ist, so ist man fertig und es wird das Ergebnis ${}a$ ausgegeben.

1. Führe diesen Algorithmus für das Paar ${}(7,3)$ durch.
2. Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
3. Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsamen Teiler ausgibt.
4. Man gebe für jedes ${}n$ ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante ${}n$ Schritte benötigt.

Lösung

1. Der Algorithmus ersetzt sukzessive

   $(7,3)\mapsto (4,3)\mapsto (3,1)\mapsto (2,1)\mapsto (1,1),$

   der größte gemeinsame Teiler ist also ${}1$.

2. Wenn  ${}a=b$  ist, so hört der Algorithmus auf. Wenn genau eine Zahl ${}0$ ist, so ist das Folgepaar ${}(c,c)$ und dann hört der Algorithmus auf. Es sei also ohne Einschränkung

   ${}a>b>0\,.$

   Das Folgepaar ist dann ${}(a-b,b)$ und beide Zahlen sind kleiner als ${}a$. D.h. unter dieser Voraussetzung wird das Maximum mit jedem Rechenschritt kleiner. Da sich alles innerhalb der natürlichen Zahlen abspielt, bricht das Verfahren irgendwann ab.

3. Bei  ${}a=b$  ist diese Zahl auch der größte gemeinsame Teiler. Wir zeigen, dass sich bei jedem Rekursionsschritt, bei dem ${}(a,b)$ (es sei wieder $a\geq b$) durch ${}(a-b,b)$ ersetzt wird, der größte gemeinsame Teiler der beiden Paare übereinstimmt. Dazu muss man nur zeigen, dass ${}a$ und ${}b$ einerseits und ${}a-b$ und ${}b$ andererseits die gleichen gemeinsamen Teiler haben. Es sei also ${}t\in \mathbb {N}$ und  ${}a=tm$  und  ${}b=tn$.  Dann ist

   ${}a-b=mt-nt=(m-n)t\,$

   ebenfalls ein Vielfaches von ${}t$. Wenn umgekehrt  ${}a-b=rt$  und  ${}b=st$  ist, so ist

   ${}a=a-b+b=rt+st=(r+s)t\,$

   ebenfalls ein Vielfaches von ${}t$.

4. Wir betrachten das Paar ${}(n,1)$. Der euklidische Algorithmus liefert

   ${}n=n\cdot 1+0\,$

   und ist fertig. Die Variante ersetzt ${}(n,1)$ durch ${}(n-1,1)$, sie braucht also ${}n-1$ Schritte, um die Abbruchbedingung ${}(1,1)$ zu erreichen.

Aufgabe (2 Punkte)

Es sei ${}n$ eine natürliche Zahl. Wann ist die Zahl ${}n^{2}-1$ eine Primzahl?

Lösung

Es gilt generell die Zerlegung

${}n^{2}-1=(n-1)(n+1)\,.$

Bei ${}n\geq 3$ sind beide Faktoren ${}\geq 2$ und daher kann ${}n^{2}-1$ nicht prim sein. Bei ${}n=2$ ist

${}2^{2}-1=3\,$

eine Primzahl. Bei ${}n=0,1$ liegt keine Primzahl vor.

Aufgabe (2 Punkte)

Es sei ${}n$ eine ganze Zahl, von der die folgenden Eigenschaften bekannt sind:

1. ${}n$ ist negativ.
2. ${}n$ ist ein Vielfaches von ${}8$, aber nicht von ${}-16$.
3. ${}n$ ist kein Vielfaches von ${}36$.
4. ${}n$ ist ein Vielfaches von ${}150$, aber nicht von ${}125$.
5. In der Primfaktorzerlegung von ${}n$ gibt es keine Primzahl, die größer als ${}5$ ist.

Was ist ${}n$?

Lösung

Wir müssen nur für die Primzahlen ${}2,3,5$ bestimmen, mit welcher Potenz sie in ${}n$ vorkommen. Wegen (2) kommt ${}2$ mit der dritten Potenz vor, aber nicht mit der vierten. Wegen (3) ist ${}9$ kein Teiler von ${}n$, da ja ${}4$ ein Teiler ist, und wegen (4) ist ${}3$ ein Teiler von ${}n$. Wegen (4) kommt ${}5$ mit der zweiten Potenz vor, aber nicht mit der dritten. Daher ist

${}n=-2^{3}\cdot 3\cdot 5^{2}=-600\,.$

Aufgabe (2 Punkte)

Zeige, dass die auf ${}\mathbb {Z} \times \mathbb {N} _{+}$ durch

$(a,b)\sim (c,d),{\text{ falls }}ad=bc,$

festgelegte Relation eine Äquivalenzrelation ist.

Lösung

Die Reflexivität und die Symmetrie ergeben sich unmittelbar aus der Definition. Zum Nachweis der Transitivität seien  ${}(a,b)\sim (c,d)$  und  ${}(c,d)\sim (e,f)$.  Dies bedeutet  ${}ad=bc$  bzw.  ${}cf=ed$.  Somit ist

${}adf=bcf=bde\,.$

Wegen  ${}d\neq 0$  ergibt die Kürzungsregel in ${}\mathbb {Z}$ die Gleichheit

${}af=eb\,,$

also  ${}(a,b)\sim (e,f)$. 

Aufgabe (3 (1+1+0.5+0.5) Punkte)

Wir betrachten in der Gruppe  ${}\mathbb {Z} \times \mathbb {Z} =\mathbb {Z} ^{2}$  die Untergruppe

${}U=\langle {\begin{pmatrix}1\\1\end{pmatrix}},{\begin{pmatrix}1\\-1\end{pmatrix}}\rangle =\left\{a{\begin{pmatrix}1\\1\end{pmatrix}}+b{\begin{pmatrix}1\\-1\end{pmatrix}}\mid a,b\in \mathbb {Z} \right\}\,$

und die zugehörige Äquivalenzrelation.

a) Skizziere die Punkte (eine sinnvolle Auswahl) aus ${}U$ (als Punkte in ${}\mathbb {Z} ^{2}$) mit einer Farbe.

b) Skizziere mit verschiedenen Farben die verschiedenen Äquivalenzklassen (Nebenklassen).

c) Wie viele Äquivalenzklassen gibt es? Beschreibe ein Repräsentantensystem.

d) Erstelle eine Verknüpfungstabelle für die Farben. Welche Farben sind zueinander invers?

Lösung erstellen

Aufgabe (4 Punkte)

Es seien ${}n,m\in \mathbb {Z}$ ganze Zahlen. Zeige, dass ${}n$ genau dann ein Teiler von ${}m$ ist, wenn es einen Ringhomomorphismus

$\mathbb {Z} /(m)\longrightarrow \mathbb {Z} /(n)$

gibt. Zeige durch ein Beispiel, dass es einen injektiven Gruppenhomomorphismus

$\mathbb {Z} /(m)\longrightarrow \mathbb {Z} /(n)$

geben kann, ohne dass ${}n$ ein Teiler von ${}m$ ist.

Lösung

Wenn ${}n$ ein Teiler von ${}m$ ist, so ist ${}m=an$ und daher ist ${}m\in \mathbb {Z} n$ und somit gilt die Idealinklusion ${}\mathbb {Z} m\subseteq \mathbb {Z} n$. Unter dem kanonischen Ringhomomorphismus

$\mathbb {Z} \longrightarrow \mathbb {Z} /(n)$

wird also ${}\mathbb {Z} m$ auf null abgebildet und daher gibt es nach dem Satz vom induzierten Homomorphismus einen Ringhomomorphismus

$\mathbb {Z} /(m)\longrightarrow \mathbb {Z} /(n).$

Wenn es umgekehrt einen solchen Ringhomomorphismus ${}\varphi$ gibt, so betrachten wir insgesamt den Ringhomomorphismus

$\mathbb {Z} \longrightarrow \mathbb {Z} /(m){\stackrel {\varphi }{\longrightarrow }}\mathbb {Z} /(n).$

Die Gesamtabbildung muss also ${}m$ auf null schicken, d.h. ${}m\mod n=0$, und ${}m$ ist ein Vielfaches von ${}n$.

Für das Beispiel betrachten wir ${}n=4$ und ${}m=2$. In ${}\mathbb {Z} /(4)$ bildet die Menge ${}\{{\bar {0}},{\bar {2}}\}$ eine Untergruppe, die zu ${}\mathbb {Z} /(2)$ isomorph ist, sodass ein injektiver Gruppenhomomorphismus ${}\mathbb {Z} /(2)\rightarrow \mathbb {Z} /(4)$ vorliegt.

Aufgabe (7 (2+2+2+1) Punkte)

Wir betrachten die Multiplikationsabbildung auf vierelementigen kommutativen Ringen.

1. Bestimme das Faseranzahltupel zur Multiplikationsabbildung

   $\cdot \colon R\times R\longrightarrow R$

   für  ${}R=\mathbb {Z} /(4)$. 

2. Bestimme das Faseranzahltupel zur Multiplikationsabbildung

   $\cdot \colon K\times K\longrightarrow K$

   für den Körper ${}K$ mit vier Elementen.

3. Bestimme das Faseranzahltupel zur Multiplikationsabbildung

   $\cdot \colon S\times S\longrightarrow S$

   für den Ring

   ${}S=\mathbb {Z} /(2)[X]/{\left(X^{2}\right)}\,.$

4. Sind die Multplikationsabbildungen auf ${}R,K,S$ zueinander isomorph?

Lösung

1. Die Faser der Multiplikationsabbildung über ${}0$ ist

   $(0,0),\,(1,0),\,(2,0),\,(3,0),\,(0,1),\,(0,2),\,(0,3),\,(2,2),$

   die Faser der Multiplikationsabbildung über ${}1$ ist

   $(1,1),\,(3,3),$

   die Faser der Multiplikationsabbildung über ${}2$ ist

   $(1,2),\,(2,1),\,(2,3),\,(3,2),$

   die Faser der Multiplikationsabbildung über ${}3$ ist

   $(1,3),\,(3,1),$

   das Faseranzahltupel ist also ${}(2,2,4,8)$.

2. Die Elemente seien ${}0,1,x,y$. Die Faser der Multiplikationsabbidung über ${}0$ ist

   $(0,0),\,(1,0),\,(x,0),\,(y,0),\,(0,1),\,(0,x),\,(0,y),$

   die Fasern der Multiplikationsabbildung über den drei anderen Elementen, die ja Einheiten sind, sind von der Bauart (Faser zu ${}z$)

   $\left\{{\left(x,x^{-1}z\right)}\mid x\neq 0\right\},$

   sie besitzen also jeweils drei Elemente. Das Faseranzahltupel ist somit ${}(3,3,3,7)$.

3. Die vier Elemente sind ${}0,1,x,1+x$, wobei ${}x$ die Restklasse von ${}X$ bezeichnet. Es gilt  ${}x^{2}=0$.  Die Faser der Multiplikationsabbildung über ${}0$ ist

   $(0,0),\,(1,0),\,(x,0),\,(1+x,0),\,(0,1),\,(0,x),\,(0,1+x),\,(x,x),$

   die Faser der Multiplikationsabbildung über ${}1$ ist

   $(1,1),\,(1+x,1+x),$

   die Faser der Multiplikationsabbildung über ${}x$ ist

   $(1,x),\,(x,1),\,(x,1+x),\,(1+x,x),$

   die Faser der Multiplikationsabbildung über ${}1+x$ ist

   $(1,1+x),\,(1+x,1),$

   das Faseranzahltupel ist also ${}(2,2,4,8)$.

4. Nach Satz 15.5 (Diskrete Mathematik (Osnabrück 2026)) sind die Multiplikationsabbildungen von ${}R$ und von ${}S$ zueinander isomorph, aber nicht zur Multiplikationsabbidung auf ${}K$.

Aufgabe (4 Punkte)

Berechne das Cauchy-Produkt bis zur vierten Potenz der geometrischen Reihe mit der Exponentialreihe.

Lösung

Die geometrische Reihe ist ${}\sum _{n=0}^{\infty }x^{n}$ und die Exponentialreihe ist ${}\sum _{n=0}^{\infty }{\frac {1}{n!}}x^{n}$. Das Cauchy-Produkt von zwei Reihen ergibt sich einfach dadurch, dass man jeden Summanden mit jedem Summanden multipliziert und gleiche Potenzen aufsummiert. Daher können die Potenzen ${}x^{5},x^{6},$ etc. ignoriert werden und es ist

${}{\begin{aligned}&\,(1+x+x^{2}+x^{3}+x^{4}){\left(1+x+{\frac {1}{2}}x^{2}+{\frac {1}{6}}x^{3}+{\frac {1}{24}}x^{4}\right)}\\&={\left(1+x+{\frac {1}{2}}x^{2}+{\frac {1}{6}}x^{3}+{\frac {1}{24}}x^{4}\right)}+{\left(x+x^{2}+{\frac {1}{2}}x^{3}+{\frac {1}{6}}x^{4}\right)}+{\left(x^{2}+x^{3}+{\frac {1}{2}}x^{4}\right)}+x^{3}+x^{4}+x^{4}+\ldots \\&=1+2x+{\frac {5}{2}}x^{2}+{\frac {8}{3}}x^{3}+{\frac {65}{24}}x^{4}+\ldots .\end{aligned}}$

Das Cauchy-Produkt bis zur vierten Potenz der beiden Reihen ist also

$1+2x+{\frac {5}{2}}x^{2}+{\frac {8}{3}}x^{3}+{\frac {65}{24}}x^{4}.$

Aufgabe (1 Punkt)

Bei einem vollständigen ungerichteten Graphen mit ${}4$ Ecken ist jede Ecke mit jeder (anderen) Ecke verbunden. Zeichne einen solchen Graphen in der Ebene ohne Überschneidungen.

Lösung

Aufgabe (3 Punkte)

Wir betrachten die Felder eines Schachbrettes als Knotenpunktmenge ${}V$ und verbinden zwei Felder, wenn sie durch einen direkten Turmzug miteinander verbunden sind. Bestimme den Grad der Punkte, den Abstand zwischen zwei Punkten und den Durchmesser dieses Graphen.

Lösung

Wir bezeichnen den Knoten in der ${}i$-ten Zeile und ${}j$-ten Spalte mit ${}v_{ij}$. Dann ist

${}d(v_{ij})=14\,,$

da von jedem Feld aus mit dem Turm in einem Zug ${}7$ verschiedene Felder in der gleichen Zeile und ${}7$ verschiedene Felder in der gleichen Spalte erreicht werden können. Zwei nicht identische Felder in der gleichen Zeile bzw. Spalte lassen sich also in einem Zug erreichen, andernfalls benötigt man zwei Züge. Der Abstand zweier Punkte lautet daher

${}d(v_{ij},v_{k\ell })={\begin{cases}0,{\text{ falls }}i=k{\text{ und }}j=\ell \,,\\1,{\text{ falls }}i=k{\text{ und }}j\neq \ell \,,\\1,{\text{ falls }}i\neq k{\text{ und }}j=\ell \,,\\2,{\text{ falls }}i\neq k{\text{ und }}j\neq \ell \,.\end{cases}}\,$

Der Durchmesser beträgt somit ${}2$.

Aufgabe (5 (1+1+1+1+1) Punkte)

Es seien ${}R,S$ endliche kommutative Ringe, es sei ${}\varphi \colon R\rightarrow S$ ein Ringhomomorphismus und es sei ${}G$ der Nullteilergraph zu ${}R$ und ${}H$ der Nullteilergraph zu ${}S$.

1. Zeige, dass ${}\varphi$ einen schwachen Graphhomomorphismus von ${}G$ nach ${}H$ induziert.
2. Es sei ${}\varphi$ injektiv. Zeige, dass ${}\varphi$ einen (echten) Graphhomomorphismus von ${}G$ nach ${}H$ induziert, wodurch ${}G$ zu einem vollen Untergraphen von ${}H$ wird.
3. Man gebe ein Beispiel, dass ${}\varphi$ keinen (echten) Graphhomomorphismus induziert.
4. Es sei nun  ${}R=S$  und ${}\varphi$ ein Ringautomorphismus. Zeige, dass dadurch ein Graphautomorphismus induziert wird.
5. Man gebe ein Beispiel für einen endlichen kommutativen Ring ${}R$ und einen Graphautomorphismus des Nullteilergraphen, der nicht von einem Ringautomorphismus herrührt.

Lösung

1. Es seien  ${}r_{1},r_{2}\in R$.  Aus  ${}r_{1}r_{2}=0$  folgt direkt

   ${}\varphi {\left(r_{1}\right)}\varphi {\left(r_{2}\right)}=\varphi {\left(r_{1}r_{2}\right)}=\varphi {\left(0\right)}=0\,.$

   Deshalb werden im Nullteilergraphen ${}G$ verbundene Knotenpunkte auf einem gemeinsamen Punkt abgebildet oder aber auf ein Punktepaar, das ebenfalls verbunden ist. Dies bedeutet schwacher Homomorphismus.

2. In injektiven Fall ist der Fall, dass zwei Punkte zusammenfallen, ausgeschlossen. Nach (1) liegt also ein injektiver Graphhomomorphismus vor, mit dem wir direkt ${}G$ als einen Untergraphen von ${}H$ auffassen können. Wenn in ${}H$ eine Kante zwishen  ${}r_{1},r_{2}\in R\subseteq S$  vorliegt, so ist  ${}r_{1}r_{2}=0$  in ${}S$, aber dann auch in ${}R$. Deshalb ist ${}G$ ein voller Untergraph.
3. Es sei  ${}S=0$  der Nullring und ${}R$ nicht der Nullring mit der Nullabbildung ${}\varphi \colon R\rightarrow 0$. Dabei wird die Nullteilerkante zwischen ${}0$ und ${}1$ nicht auf eine Kante abgebildet, da die beiden Endpunkte vereinigt werden.
4. Dies folgt direkt aus (2).
5. Es sei  ${}R=\mathbb {Z} /(3)$,  im zugehörigen Nullteilergraphen ist ${}0$ mit ${}1$ und mit ${}2$ verbunden. Die Vertauschung von ${}1$ und ${}2$ ist ein nichttrivialer Graphautomorphismus. Dagegen muss ein Ringautomorphismus die ${}1$ auf die ${}1$ abbilden und muss in diesem Fall bereits die Identität sein.

Aufgabe (5 Punkte)

Es sei ${}H$ ein vollständiger Graph. Zeige, dass es zu einer Kante ${}e$ eines Graphen ${}G$ stets eine natürliche Identifizierung

${}\operatorname {Hom} (G\setminus \{e\},H)=\operatorname {Hom} (G,H)\uplus \operatorname {Hom} (G/e,H)\,$

gibt.

Lösung

Es sei  ${}G=(V,E)$  und  ${}H=(W,F)$,   ${}e=\{u,v\}$.  Wir beschreiben eine explizite Bijektion

$\operatorname {Hom} (G\setminus \{e\},H)\longrightarrow \operatorname {Hom} (G,H)\uplus \operatorname {Hom} (G/e,H).$

Es sei

$f\colon V\longrightarrow W$

ein Graphhomomorphismus von ${}G\setminus \{e\}$ nach ${}H$. Wir unterscheiden die beiden Fälle, ob  ${}f(u)\neq f(v)$  ist oder nicht. Im ersten Fall kann man ${}f$ direkt als einen Graphhomomorphismus von ${}G$ nach ${}H$ auffassen, da ja die einzige zusätzliche Kantenbedingung erfüllt ist, weil ${}H$ vollständig ist. Bei  ${}f(u)=f(v)$  erhält man eine wohldefinierte Abbildung von ${}V/e$ (der Quotientenmenge, bei der ${}u$ und ${}v$ identifiziert werden) nach ${}W$, die ein Graphhomomorphismus von ${}G/e$ nach ${}H$ ist. Diese Gesamtabbildung ist offenbar injektiv. Zur Surjektivität. Wenn ${}f\colon V\rightarrow W$ ein Homomorphismus von ${}G$ nach ${}H$ ist, so ist es direkt auch ein Homomorphismus von ${}G\setminus \{e\}$ nach ${}H$. Wenn ${}f\colon V/e\rightarrow W$ ein Homomorphismus von ${}G/e$ nach ${}H$ ist, so kann man es als eine Abbildung

$V\longrightarrow W$

mit  ${}f(u)=f(v)$  auffassen. Dies ist dannn wiederum ein Homomorphismus von ${}G/e$ nach ${}H$.