Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon: Erläuterung zu

Nicht-injektive Graphen

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Ist $ G$ ein Graph, der für eine Abbildung von $ A$ nach $ B$ steht, und gilt $ \vert A\vert>\vert B\vert$. Dann gibt es Knoten $ b\in B$ und $ a_1,a_2\in A$, so dass $ \{a_1,b\}$ und $ \{a_2,b\}$ Kanten in $ G$ sind. Der Graph ist dann also nicht injektiv.
Man ordnet jedem Knoten von $ B$ ein Schubfach zu und beschriften den Kasten entsprechend. Ein Knoten aus $ A$ wird in ein Schubfach 'gelegt', wenn er mit dem entsprechendem Knoten von $ B$ eine gemeinsame Kante hat. Da $ G$ eine Abbildung ist, ist dies eindeutig möglich. Da es mehr Knoten aus $ A$ als Schubfächer gibt, ist mindestens ein Schubfach mit mehr als einem Knoten belegt. Dieses Schubfach ist das gesuchte $ b \in B$. Aus den darin enthaltenen Knoten können $ a_1,a_2 \in A$ gewählt werden.
(Aus: Vorkurs Mathematik)
[Zurück zur Aussage]
  automatisch erstellt am 26.  2. 2007