matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieGraphentheorie
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Graphentheorie" - Graphentheorie
Graphentheorie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Graphentheorie: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 15:39 Sa 25.11.2006
Autor: unwanted

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.

        
Bezug
Graphentheorie: Ideen
Status: (Antwort) fertig Status 
Datum: 17:07 Sa 25.11.2006
Autor: Bastiane

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]

Bezug
                
Bezug
Graphentheorie: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Graphentheorie: Antwort
Status: (Antwort) fertig Status 
Datum: 19:35 Sa 25.11.2006
Autor: Bastiane

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
[cap]

Bezug
                
Bezug
Graphentheorie: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 20:05 Sa 25.11.2006
Autor: unwanted

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

Bezug
                
Bezug
Graphentheorie: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 22:34 Mo 27.11.2006
Autor: unwanted

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.

Bezug
                        
Bezug
Graphentheorie: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:20 Mi 29.11.2006
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Graphentheorie: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 13:07 So 26.11.2006
Autor: unwanted

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




Bezug
                
Bezug
Graphentheorie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]