Teilgraph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:25 Sa 12.09.2009 | | Autor: | Pacapear |
Hallo zusammen!
Ich habe hier einen Satz, bei dem ich ein paar Probleme mit den Begriffen Teilgraph und isomorpher Teilgraph habe.
Hier der Satz:
Ist $T$ ein Baum und $G$ ein Graph mit Minimalgrad [mm] $\delta(G) \ge [/mm] |T|-1$, so gilt $T [mm] \subseteq [/mm] G$, d.h. $G$ hat einen zu $T$ isomorphen Teilgraphen.
So, ähm, ich hab ein Problem mit dem Teilgraphen $T$.
Ich erkenne nicht, was der Graph $G$ nun genau enthält.
Enthält $G$ einen Teilgraphen $T$, weil da steht ja "Wenn ... so gilt $T [mm] \subseteq [/mm] G$"?
Oder enthält $G$ einen zu $T$ isomorphen Teilgraphen, weil da steht "d.h. $G$ hat einen zu $T$ isomorphen Teilgraphen.
Irgendwie klingt das so, als ob der Graph $T$ gleich einem ihn isomorphen Graphen ist...
Aber wenn ich mir die Definition eines isomorphen Teilgraphen angucke, dann ist doch ein isomorpher Teilgraph eines Graphen $H$ ein anderer Graph als der Graph $H$ und nicht wieder der Graph $H$ selbst ![[haee]](/images/smileys/haee.gif "[haee]")
Kann mir da jemand weiterhelfen?
LG, Nadine
|
|
| |
|
Hallo Pacapear!
> Hallo zusammen!
>
>
>
> Ich habe hier einen Satz, bei dem ich ein paar Probleme mit
> den Begriffen Teilgraph und isomorpher Teilgraph habe.
>
> Hier der Satz:
>
> Ist [mm]T[/mm] ein Baum und [mm]G[/mm] ein Graph mit Minimalgrad [mm]\delta(G) \ge |T|-1[/mm],
> so gilt [mm]T \subseteq G[/mm], d.h. [mm]G[/mm] hat einen zu [mm]T[/mm] isomorphen
> Teilgraphen.
Was ist denn nochmal |T|?
> So, ähm, ich hab ein Problem mit dem Teilgraphen [mm]T[/mm].
>
> Ich erkenne nicht, was der Graph [mm]G[/mm] nun genau enthält.
>
> Enthält [mm]G[/mm] einen Teilgraphen [mm]T[/mm], weil da steht ja "Wenn ...
> so gilt [mm]T \subseteq G[/mm]"?
>
> Oder enthält [mm]G[/mm] einen zu [mm]T[/mm] isomorphen Teilgraphen, weil da
> steht "d.h. [mm]G[/mm] hat einen zu [mm]T[/mm] isomorphen Teilgraphen.
>
>
>
> Irgendwie klingt das so, als ob der Graph [mm]T[/mm] gleich einem
> ihn isomorphen Graphen ist...
>
> Aber wenn ich mir die Definition eines isomorphen
> Teilgraphen angucke, dann ist doch ein isomorpher Teilgraph
> eines Graphen [mm]H[/mm] ein anderer Graph als der Graph [mm]H[/mm] und nicht
> wieder der Graph [mm]H[/mm] selbst
Also wenn ich mich recht erinnere, dann bedeutet doch Isomorphie einfach nur, dass die Graphen genauso aussehen, egal ob du die Knoten jetzt mit a,b,c bezeichnest oder mit 1,2,3. Das heißt, es ist ungefähr so wie mit "derselbe" und "dergleiche" - hier ist der Graph, der in G enthalten ist, nicht derselbe wie der Baum T, aber dergleiche. Hilft dir das?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:44 Sa 12.09.2009 | | Autor: | Pacapear |
Hallo Bastiane.
> Was ist denn nochmal |T|?
$|T|$ ist die Anzahl der Knoten im Graphen $T$.
> Also wenn ich mich recht erinnere, dann bedeutet doch
> Isomorphie einfach nur, dass die Graphen genauso aussehen,
> egal ob du die Knoten jetzt mit a,b,c bezeichnest oder mit
> 1,2,3. Das heißt, es ist ungefähr so wie mit "derselbe"
> und "dergleiche" - hier ist der Graph, der in G enthalten
> ist, nicht derselbe wie der Baum T, aber dergleiche. Hilft
> dir das?
Hmm, ich denke, ich verstehe ein bisschen, was du meinst.
Also wenn ich die Isomorphie bei uns richtig verstanden habe, dann sehen die Graphen schon im Prinzip gleich aus. Man bildet quasi die gegeben Knoten auf neue Knoten ab und die Kanten, die zwischen den gegebenen Knoten sind, sind dann zwischen den neuen Bildern der Knoten.
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:23 Sa 03.10.2009 | | Autor: | felixf |
Hallo Nadine!
> Ich habe hier einen Satz, bei dem ich ein paar Probleme mit
> den Begriffen Teilgraph und isomorpher Teilgraph habe.
>
> Hier der Satz:
>
> Ist [mm]T[/mm] ein Baum und [mm]G[/mm] ein Graph mit Minimalgrad [mm]\delta(G) \ge |T|-1[/mm],
> so gilt [mm]T \subseteq G[/mm], d.h. [mm]G[/mm] hat einen zu [mm]T[/mm] isomorphen
> Teilgraphen.
>
>
>
> So, ähm, ich hab ein Problem mit dem Teilgraphen [mm]T[/mm].
>
> Ich erkenne nicht, was der Graph [mm]G[/mm] nun genau enthält.
>
> Enthält [mm]G[/mm] einen Teilgraphen [mm]T[/mm], weil da steht ja "Wenn ...
> so gilt [mm]T \subseteq G[/mm]"?
Das $T [mm] \subseteq [/mm] G$ ist eine sehr saloppe Schreibweise. Sie bedeutet nichts anders, als das $G$ einen Teilgraphen $H$ hat (fuer den wirklich $H [mm] \subseteq [/mm] G$ gilt) mit $H [mm] \cong [/mm] T$.
Man identifiziert manchmal gerne $T$ mit $H$ (vermoege des Isormophismus') und schreibt dann $T [mm] \subseteq [/mm] G$ anstelle $T [mm] \cong [/mm] H [mm] \subseteq [/mm] G$.
LG Felix
|
|
|
|
