Frage zu allg. Definitionen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:31 Mo 20.06.2011 | | Autor: | DieNase |
| Aufgabe | Ubung ¨ 161. Die Gradfolge eines Graphen ist die Folge der Grade der einzelnen Knoten,
z.B. haben die Graphen aus Beispiel 159 alle die Gradfolge (3, 3, 3, 3, 3, 3, 3, 3). Ist es
moglich, Graphen (ohne Schleifen und Mehrfachkanten) mit de ¨ n folgenden Gradfolgen zu
konstruieren?
(a) (3, 3, 3, 3) (b) (1, 2, 3, 4)
(c) (3, 3, 3, 2, 1) (d) (1, 1, 1, 1, 1) |
1. Frage:
Also da steht ohne mehrfachkanten. Was mehrfachkanten mit ungerichteten Kanten ist. Ist mir klar. Aber Was ist bei gerichteten Kanten?
Also was wenn ich z.b. eine gerichtete Kante von x nach y habe und eine gerichtete Kante von y nach x ist das schon eine Mehrfachkante? Oder wäre erst eine weitere Gerichtete Kante von x nach y eine Mehfrachkante.
Bzw. Wie schauts mit einer Mischung aus.
Ich habe eine ungerichtete kante von x nach y und eine gerichtete Kante von y nach x.
2. Frage:
Wenn ich von knoten a nach knoten b eine gerichtete kante lege die von a nach b geht und von b eine gerichtete kante nach c lege. ist dann die Gradfolge (1,1,1) oder ist sie (1,2,1). Wird also die Kante wenn sie gerichtet ist bei Beiden Knoten gerechnet oder nur bei der wo sie weggeht.
Ich weiß das meine Fragen jetzt nicht umbedingt was mit einer Lösungsdiskussion zu tun haben.
Bloß bei Punkt D sind mir halt paar fragen aufgekommen und google bot mir eigentlich nur eine unzureichende antwort auf diese. Drum hoffe ich das diese fragen hier erlaubt sind.
mfg
Christoph
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:45 Mo 20.06.2011 | | Autor: | DieNase |
| Aufgabe | Ubung ¨ 160. Bestimme alle nicht-isomorphen Graphen mit n = 2, 3, oder 4 Knoten
(nicht-zusammenhangende Graphen miteingeschlossen) |
Also mir ist gerade aufgefallen das ich wieder Etwas nicht verstehe.
Ich hab mir zu isomorphie mir folgende Wiki Artikel durchgelesen und habe ihn denke ich auch so halbwegs verstanden. Für jeden Knoten in Graph 1 gibt es äquivalenten knoten in Graph 2 mit den gleichen eigenschaften. Doch was genau beschreibt nun diese eigentschaften. Sind es die Anzahl der Kanten in einem Knoten?
http://de.wikipedia.org/wiki/Isomorphie_von_Graphen
|
|
|
| |
|
> Ubung ¨ 160. Bestimme alle nicht-isomorphen Graphen mit n
> = 2, 3, oder 4 Knoten
> (nicht-zusammenhängende Graphen miteingeschlossen)
> Also mir ist gerade aufgefallen das ich wieder Etwas nicht
> verstehe.
>
> Ich hab mir zu isomorphie mir folgende Wiki Artikel
> durchgelesen und habe ihn denke ich auch so halbwegs
> verstanden. Für jeden Knoten in Graph 1 gibt es
> äquivalenten knoten in Graph 2 mit den gleichen
> eigenschaften. Doch was genau beschreibt nun diese
> eigentschaften. Sind es die Anzahl der Kanten in einem
> Knoten?
>
> http://de.wikipedia.org/wiki/Isomorphie_von_Graphen
In diesem Artikel wird doch eine genaue Definition
der Isomorphie angegeben. Es geht nicht nur um die
Anzahlen der Kanten bei jedem Knoten, sondern es
müssen die gesamten "Verwandtschaftsbeziehungen"
isomorph abgebildet werden. Realisiert man zwei
Graphen durch verknotete elastische Schnüre, so
sind sie nur dann isomorph, wenn man das eine "Netz"
durch eine topologische Abbildung exakt und voll-
ständig mit dem anderen zur Übereinstimmung brin-
gen kann.
Damit die Aufgabe Sinn macht, müsste man sich wohl
auf Graphen ohne Mehrfachkanten beschränken, denn sonst
gäbe es ja unendlich viele nicht-isomorphe Graphen.
Ich gehe auch davon aus, dass in der Aufgabe wieder
ungerichtete Graphen gemeint sind. Wenn du magst,
kannst du ja die Aufgabe zuerst für ungerichtete
Graphen und dann für gerichtete behandeln.
Ob Schleifen erlaubt sind oder nicht, wird auch
nicht gesagt. Wenn ja, gibt es natürlich deutlich
mehr mögliche nicht-isomorphe Graphen als ohne.
LG Al-Chw.
|
|
|
| |
|
> Ubung ¨ 161. Die Gradfolge eines Graphen ist die Folge der
> Grade der einzelnen Knoten,
> z.B. haben die Graphen aus Beispiel 159 alle die Gradfolge
> (3, 3, 3, 3, 3, 3, 3, 3). Ist es
> moglich, Graphen (ohne Schleifen und Mehrfachkanten) mit
> de ¨ n folgenden Gradfolgen zu
> konstruieren?
> (a) (3, 3, 3, 3) (b) (1, 2, 3, 4)
> (c) (3, 3, 3, 2, 1) (d) (1, 1, 1, 1, 1)
> 1. Frage:
> Also da steht ohne mehrfachkanten. Was mehrfachkanten mit
> ungerichteten Kanten ist. Ist mir klar. Aber Was ist bei
> gerichteten Kanten?
Ich denke, dass die Aufgabe sich nicht auf gerichtete Graphen
bezieht. Bei solchen sollte man die Begriffe "Ausgangsgrad"
und "Eingangsgrad" benützen, wenn man wirklich den Unter-
schied machen will.
> Also was wenn ich z.b. eine gerichtete Kante von x nach y
> habe und eine gerichtete Kante von y nach x ist das schon
> eine Mehrfachkante? Oder wäre erst eine weitere Gerichtete
> Kante von x nach y eine Mehfrachkante.
> Bzw. Wie schauts mit einer Mischung aus.
> Ich habe eine ungerichtete kante von x nach y und eine
> gerichtete Kante von y nach x.
Einen bestimmten Graph betrachtet man doch entweder
als gerichteten oder als ungerichteten Graph (entweder
nur Pfeile oder aber gar keine Pfeile). Sind in einem
gerichteten Graph zwei Knoten A und B, zwischen denen
man "pendeln" kann, so braucht es eben die Pfeile AB und
BA.
> 2. Frage:
> Wenn ich von knoten a nach knoten b eine gerichtete kante
> lege die von a nach b geht und von b eine gerichtete kante
> nach c lege. ist dann die Gradfolge (1,1,1) oder ist sie
> (1,2,1). Wird also die Kante wenn sie gerichtet ist bei
> Beiden Knoten gerechnet oder nur bei der wo sie weggeht.
>
> Ich weiß das meine Fragen jetzt nicht umbedingt was mit
> einer Lösungsdiskussion zu tun haben.
Ja, wie gesagt - die Aufgabe bezieht sich auf ungerichtete
Graphen. Eine analoge Aufgabe für gerichtete Graphen
müsste anders formuliert werden.
> Bloß bei Punkt D sind mir halt paar fragen aufgekommen und
> google bot mir eigentlich nur eine unzureichende antwort
> auf diese. Drum hoffe ich das diese fragen hier erlaubt
> sind.
Klar sind hier Fragen erlaubt. Nur kann ich im vorliegenden
Fall auch nicht groß weiterhelfen ...
LG Al-Chw.
|
|
|
|
