www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

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
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheoriehamiltonsch?
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - hamiltonsch?
hamiltonsch? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

hamiltonsch?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:29 So 18.01.2009
Autor: MacMath

Aufgabe
Es sei G ein schlichter Graph.Weiter besitze G einen geschlossenen Kantenzug C, so dass
jede Kante, die nicht zu C gehört, mit einer Kante aus C inzidiert. Man zeige, dass L(G) Hamiltonsch ist.

Gibts da einen bestimmten Satz bzw. einen Ansatz bei dem ich starten kann? Habe bisher keine Idee zum beginn eines beweises.

Gruß Daniel

        
Bezug
hamiltonsch?: Antwort
Status: (Antwort) fertig Status 
Datum: 01:56 Mo 19.01.2009
Autor: reverend

Hallo MacMath,

das wird ein recht einfacher Widerspruchsbeweis. Dazu brauchst Du allerdings ein Minimum an Aussagenlogik sowie die Definitionen aller verwendeten Begriffe.

Nimm an, es gebe eine Kante, die weder zu C gehört, noch mit einer Kante aus C inzidiert, und dass der Graph dennoch hamiltonsch ist. Was heißt das für die Knoten, die die betrachtete Kante verbindet? Warum kann der Graph dann nicht hamiltonsch sein? Fertig.

Du musst dafür definieren können:
- schlichter Graph
- Kante
- Knoten (hier nur implizit verwendet)
- inzidieren
- geschlossener Kantenzug
- hamiltonsch

lg,
reverend

Bezug
                
Bezug
hamiltonsch?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:41 Mo 19.01.2009
Autor: MacMath

Habe die Aufgabe nun doch lösen können, allerdings etwas anders (ich vermute es wird kürzer ;)

Ich betrachte einen Ausschnitt von G bestehend aus allen Kanten die zu einer Kante [mm] k_i \in [/mm] C inzident sind (sowie [mm] k_i [/mm] selbst, ausgenommen sind natürlich Kanten die schon vorher betrachtet wurden)

Betrachtet man den gleichen Ausschnitt in L(G) lässt sich leicht ein Hamiltonweg [mm] h_i [/mm] von [mm] k_{i} [/mm] nach [mm] k_{i+1} [/mm] bilden.

Diese Hamiltonwege ergeben "aneinandergehangen" den gesuchten Hamiltonkreis.

Gruß Daniel


Bezug
                        
Bezug
hamiltonsch?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:00 Mo 19.01.2009
Autor: reverend

Hallo MacMath,

das scheint mir nicht richtig zu sein. Damit hättest Du zugleich das []Hamiltonkreisproblem gelöst, was ja höchst beachtlich wäre. ;-) Vielleicht könntest Du so auch noch P=NP nachweisen. Mindestens die Informatiker wären glücklich, und Dir ein hohes Preisgeld sicher.

> Diese Hamiltonwege ergeben "aneinandergehangen" den gesuchten Hamiltonkreis.

Wie willst Du das zeigen? Du musst nachweisen, dass nun keine Kante mehr existiert, die mit keiner Kante des Graphen inzidiert.

Nebenbei ist mein Weg sicher kürzer:
Wenn eine beliebige Kante mit keiner Kante des gegebenen Kantenzuges inzidiert, sind die adjazenten Punkte nicht Teil des Kantenzuges, der somit nicht hamiltonsch ist. Fertig.

lg,
reverend

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


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]