Graphen Symmetrie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Jede Relation auf einer Menge V kann als ein gerichteter Graph (mit erlaubten Schlingen) veranschaulicht werden. |
Hallo Leute,
ich habe ein Frage zum Versaendnis:
Wenn JEDE Relation auf einer Menge V allein mithilfe von gerichteten Kanten und Schlingen "gebildet" werden kann, wie steht es dann um eine Relation die symmetrisch ist?
Bei einer symmetrischen Relation darf der Graph entweder nicht gerichtet sein (ungerichtet) oder es muessen Mehrfachkanten erlaubt sein.
Relationen die
- reflexiv (Schlingen)
- antireflexiv (keine Schlingen)
- antisymmetrisch (es exist. hoechstens eine gerichtete Kante zwischen zwei Punkten)
- transitiv (der Graph muss aus Kreisen bestehen)
symmetrie funktioniert nicht.
Was genau habe ich nicht verstanden?
Gruss
mathlooser
|
|
| |
|
Hi mathlooser,
es gibt doch gar kein Problem. In einem gerichteten Graph ist natürlich nicht ausgeschlossen, dass es eine Kante von $x$ nach $y$ und eine von $y$ nach $x$ (auch beliebig viele) geben kann. Die Relationen auf der dem Graphen zugrunde liegenden Menge stehen in eindeutiger Korrespondenz zu den gerichteten Graphen, sodass von jeder Ecke zu jeder anderen Ecke höchstens eine Kante verläuft. Dann darf aber trotzdem auch eine Kante zurück gehen.
Als Spezialfall stehen übrigens Präordnungen (reflexiv und transitiv) in direkter Korrespondenz zu Kategorien mit Objekten die Elemente der zugrundliegenden Menge und einem eindeutigen Pfeil [mm] $x\to [/mm] y$, falls [mm] $x\le [/mm] y$.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Aufgabe | Jede Relation auf der endlichen Menge V kann als Graph mit folgenden Eigenschaften aufgefasst werden:
Antwortmoeglichkeiten: (Mehrfachantworten erlaubt)
- gerichtet
- mit Schlingen
- mit Mehrfachkanten
- ohne Kreise |
Hallo UniversellesObjekt,
danke fuer deine Antwort.
> In einem gerichteten Graph ist natürlich nicht ausgeschlossen, dass es eine Kante von x nach y und eine von y nach x (auch beliebig viele) geben kann.
Laut Antwort der Aufgabenstellung ist aber genau dies der Fall:
Die richtige Antwort auf die obere Frage lautet:
- gerichtet
- mit Schlingen
Mehrfachkanten ist nicht dabei.
Gruss
mathlooser
|
|
|
| |
|
Hi,
also mit dem Satz, den du von mir zitiert hast, meinte ich, dass in allgemeinen gerichteten Graphen Mehrfachkanten erlaubt sind.
Eine Relation kann man aus einem gerichteten Graphen gewinnen, wenn von jeder Ecke $x$ zu jeder Ecke $y$ höchstens eine Kante (in dieser Richtung!) verläuft. Wenn es eine solche Kante gibt, definiert man dann $xRy$.
Die Richtung ist hierbei aber eben wichtig. Mit keine Mehrfachkanten ist nicht ausgeschlossen, dass in entgegengesetzte Richtungen nicht je eine Kante verlaufen darf.
Hat man umgekehrt eine Relation $R$ auf $V$ gegeben, definiert man die Menge der Kanten von $x$ nach $y$ als [mm] $\{(x,y)\}$, [/mm] falls $xRy$ und [mm] $\emptyset$ [/mm] andernfalls. Über die Menge der Kanten von $y$ nach $x$ ist hiermit aber noch nichts gesagt.
Liebe Grüße,
UniversellesObjekt
P.S.: Die Voraussetzung in der Aufgabe, dass $V$ endlich sein soll, ist übrigens unnötig und lenkt vom Wesentlichen ab. Insbesondere sind auch unendliche gerichtete Graphen von Interesse, und dass Relationen auf unendlichen Mengen interessant sind, dürfte ebenfalls klar sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:27 Mo 10.03.2014 | | Autor: | mathlooser |
Hallo,
> Mit keine Mehrfachkanten ist nicht ausgeschlossen, dass in entgegengesetzte Richtungen nicht je eine Kante verlaufen darf.
Das war mir nicht klar.
Ich dachte Mehrfachkanten bedeutet "mehr als eine Kante" unabhaengig von der Richtung.
Gruss und vielen lieben Dank!
mathlooser
|
|
|
|
