Graphentheorie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Der Graph G bestehe aus zwei Zusammenhangskomponenten [mm] G_{1}, G_{2}, [/mm] wobei G1 ein vollständiger Graph mit n Knoten und G2 ein Baum mit ebenfalls n Knoten ist (mit n [mm] \ge [/mm] 1). Der Graph H entstehe aus G dadurch, dass man weitere Kanten folgendermaÿen zu G hinzufügt: Man verbinde jeden Knoten von G1 mit jedem Knoten von G2 durch eine Kante.
a)Man zeige, dass H genau [mm] \bruch{3n^{2}+n-2}{2} [/mm] Kanten hat.
b) Man zeige, dass H keine Eulersche Linie besitzt.
c) Man zeige, dass H im Fall n [mm] \ge [/mm] 2 immer einen Hamiltonschen Kreis besitzt. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
nun hänge ich schon wider an der nächsten Aufgabe fest.
zu a) Ich weiss, dass ein vollständiger Graph [mm] \bruch{n(n-1)}{2} [/mm] Kanten hat.
Und ein Baum hat m = n-1 Kanten.
Wie bringe ich diese beiden Graphen nun zusammen und wie komme ich dann auf [mm] \bruch{3n^{2}+n-2}{2} [/mm] ? Meine Versuche sind nie u diesem Ergebnis gekommen.
zu b) und c) Ich weiss die Formeln die ich brauch um dies zu berechnen, aber es fällt mir schwer dies ohne konkrete Zahlen zu tun und nur mit Variablen.
|
|
| |
|
Hallo unwanted!
> Der Graph G bestehe aus zwei Zusammenhangskomponenten
> [mm]G_{1}, G_{2},[/mm] wobei G1 ein vollständiger Graph mit n Knoten
> und G2 ein Baum mit ebenfalls n Knoten ist (mit n [mm]\ge[/mm] 1).
> Der Graph H entstehe aus G dadurch, dass man weitere Kanten
> folgendermaÿen zu G hinzufügt: Man verbinde jeden Knoten
> von G1 mit jedem Knoten von G2 durch eine Kante.
>
> a)Man zeige, dass H genau [mm]\bruch{3n^{2}+n-2}{2}[/mm] Kanten
> hat.
>
> b) Man zeige, dass H keine Eulersche Linie besitzt.
>
> c) Man zeige, dass H im Fall n [mm]\ge[/mm] 2 immer einen
> Hamiltonschen Kreis besitzt.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> nun hänge ich schon wider an der nächsten Aufgabe fest.
>
> zu a) Ich weiss, dass ein vollständiger Graph
> [mm]\bruch{n(n-1)}{2}[/mm] Kanten hat.
>
> Und ein Baum hat m = n-1 Kanten.
>
> Wie bringe ich diese beiden Graphen nun zusammen und wie
> komme ich dann auf [mm]\bruch{3n^{2}+n-2}{2}[/mm] ? Meine Versuche
> sind nie u diesem Ergebnis gekommen.
Eigentlich ist es ganz einfach, aber ich hatte auch zuerst einen falschen Ansatz...  Du hast doch in jeder Komponente von G jeweils n Knoten. Nun wird jeder Knoten mit jedem verbunden, es kommen also insgesamt [mm] n*n=n^2 [/mm] Kanten hinzu. Wenn du jetzt alle Kanten addierst und auf den gleichen Nenner bringst, bekommst du genau das, was du suchst.
> zu b) und c) Ich weiss die Formeln die ich brauch um dies
> zu berechnen, aber es fällt mir schwer dies ohne konkrete
> Zahlen zu tun und nur mit Variablen.
Dazu hab' ich noch keine Lösung, aber evtl. ein paar Ansätze. Ich vermute mal, dass Euler Linie das gleiche wie Euler-Weg (oder auch Euler-Spaziergang ) ist, also dass jede Kante genau einmal durchlaufen werden soll. Da würde ich damit ansetzen, dass das ja genau dann der Fall ist, wenn jeder Knoten geraden Grad hat. Evtl. funktioniert das nun über eine Fallunterscheidung, wenn n gerade ist und wenn n ungerade ist. Wenn n ungerade ist, hat ja jeder Knoten in der vollständigen Komponente erstmal geraden Grad, durch das Verbinden kommt dann eine ungerade Anzahl an Kanten hinzu, also hat dann jeder Knoten davon ungeraden Grad. Und wenn n gerade ist, dann ergibt sich der Widerspruch wohl in den Blättern, denn Blätter haben immer Grad 1, wenn diese "Baum-Komponente" jetzt mit der anderen verbunden wird, bekommt ja jeder Knoten eine gerade Anzahl an Kanten hinzu, also ist insgesamt der Grad zumindest der Blätter ungerade. Und das müsste doch eigentlich schon reichen. (Hab' das jetzt hier nur mal so schnell hingeschrieben, evtl. ist das noch nicht ganz so gut formuliert oder enthält vllt auch einen Flüchtigkeitsfehler oder so...).
Für die c) habe ich auch nur ein paar Ideen: ich würde es konstruktiv machen.
Evtl. könnte man z. B. bei der Wurzel anfangen und von dort rüber zu der anderen Komponente laufen. Und von dort dann z. B. zu dem Sohn des Wurzelknotens, dann zurück zu einem beliebigen der anderen Komponente, wieder zum nächsten Sohn usw.. Weiß nicht, ob das so hinkommt (die Richtigkeit müsste dann wohl auch noch gezeigt werden...). Oder du läufst im Baum einmal von der Wurzel runter bis zu einem Blatt, von dort dann in die andere Komponente, dann z. B. in den nächsten Zweig des Baumes, wieder in die andere Komponente usw..
Das mal als Ideen, vielleicht fällt dir ja noch was besseres (oder evtl. richtigeres ) ein. Und du kannst das Ganze natürlich auch mal mit Zahlbeispielen ausprobieren, dann merkst du auch unter Umständen, dass evtl. eine Idee nicht funktioniert.
Viel Spaß beim Rumknobeln, und meld dich ruhig mit weiteren Ideen oder so. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:52 Sa 25.11.2006 | | Autor: | unwanted |
danke für die ideen. nun hab ich wieder ein problem mit aufgabe a)
ich rechne also [mm] \bruch{n(n-1)}{2} [/mm] + n-1 + [mm] n^{2}... [/mm] dann bekomme ich aber
[mm] \bruch{3n^{2}+n+2}{2} [/mm] und nicht [mm] \bruch{3n^{2}+n-2}{2} [/mm] herraus?
was mache ich falsch?
|
|
|
| |
|
Hallo unwanted!
> danke für die ideen. nun hab ich wieder ein problem mit
> aufgabe a)
>
> ich rechne also [mm]\bruch{n(n-1)}{2}[/mm] + n-1 + [mm]n^{2}...[/mm] dann
> bekomme ich aber
>
> [mm]\bruch{3n^{2}+n+2}{2}[/mm] und nicht [mm]\bruch{3n^{2}+n-2}{2}[/mm]
> herraus?
>
> was mache ich falsch?
Also ich erhalte da:
[mm] \bruch{n^2-n+2n-2+2n^2}{2}=\bruch{3n^2+n-2}{2}
[/mm]
Keine Ahnung, was du falsch gemacht hast.
Viele Grüße
Bastiane
|
|
|
| |
|
danke für deine antwort. hab da wohl was mit plus und minus verwechselt. für die anderen beiden aufgaben komm ich aber auch auf kein ergebnis
|
|
|
| |
|
ist es nicht richtig das beim eulerkreisproblem jeder knoten einen geraden grad haben muss? ich konnte nichts zu knotengraden bei bäumen finden, aber ein baum kann ja auch knoten mit geraden grad haben und somit wäre diese dann nach der verbindung ungerade. aber können wir überhaupt wissen oder ausschließen welche grade er hat?
die aufageb ist ja, man zeige dass der graph KEINE eulersche linie besitzt. kann man das nur mit der knotengradzahl machen? und wie zeige ich es dann. denn mit zeige ist sicherlich eine rechnung und kein antwortsatz gemeint?
und bei c) bin ich auch noch nicht weiter, man muss sicher ein bisschen mit den formeln rumspielen. ich hätte mir lieber aufgaben mit zahlenbeispielen gewünscht. nun hänge ich an den formaln fest.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Mi 29.11.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Aufgabe | Der Graph G bestehe aus zwei Zusammenhangskomponenten $ [mm] G_{1}, G_{2}, [/mm] $ wobei [mm] G_{1} [/mm] ein vollständiger Graph mit n Knoten und [mm] G_{2} [/mm] ein Baum mit ebenfalls n Knoten ist (mit n $ [mm] \ge [/mm] $ 1). Der Graph H entstehe aus G dadurch, dass man weitere Kanten folgendermaÿen zu G hinzufügt: Man verbinde jeden Knoten von [mm] G_{1} [/mm] mit jedem Knoten von [mm] G_{2} [/mm] durch eine Kante.
a)Man zeige, dass H genau $ [mm] \bruch{3n^{2}+n-2}{2} [/mm] $ Kanten hat.
b) Man zeige, dass H keine Eulersche Linie besitzt.
c) Man zeige, dass H im Fall n $ [mm] \ge [/mm] $ 2 immer einen Hamiltonschen Kreis besitzt. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo alle zusammen :) ich hatte diese Aufgabe schon in "Diskrete Mathematik" geposted. Und die erste Aufgabe konnten wir schon lösen. Nun habe ich aber gesehen das es ein extra Forum für Graphentheorie gibt und vieleicht ist meine Frage hier besser aufgehoben. Deshalb habe ich mir gedacht mal hier zu fragen ob jemand mir Hilfestellung zu b) und c) geben kann.
Hier ist der link zu dieser Aufgabe.
https://matheraum.de/read?t=202343
Ich habe schon ein paar gute Ansätze bekommen, ich komme aber nicht weiter. Vieleicht hat jemand an diesem schönen Sonntag noch ein paar Ideen für mich.
Vielen Dank schonmal
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:11 Mo 27.11.2006 | | Autor: | DaMenge |
Hi,
hab die zwei Threads mal zusammen in die Graphentheorie gepackt und in Zukunft bitte einfach um verschiebung bitten statt einem Doppelpost.
inhaltlich würde ich empfehlen mal aufzuschreiben, wo du denn bei den Ideen von Bastiane nicht weiter kommst, denn Ansätze wurden doch schon geliefert.
viele Grüße
DaMenge
|
|
|
|
