[MaLo] Übung 6, Aufgabe 2

[FoSAP] Formale Systeme, Automaten, Prozesse
[BuK] Berechenbarkeit und Komplexität
[MaLo] Mathematische Logik

Übung 6, Aufgabe 2

Beitragvon Sieben » 29.11.06 19:40

Hat irgendjmd. ne Ahnung bei der Aufgabe? Ich steh völlig aufem Schlauch :)
Sieben
 
Beiträge: 94
Registriert: 23.03.06 16:34
Wohnort: Aachen / Willich
Studiengang: Informatik (Dipl.)
Studiert seit: WS 06/07
Anwendungsfach: BWL

Beitragvon p0llux » 29.11.06 20:01

1 und 2 sind bei mir äquivalent, 3 halt nicht. Bei 1->2 und 2->1 hab ich mich halt an die Definitionen geklammert und danach für 3->1 ein gegenbeispiel gebracht.

Wenn ich dir mehr verrate weißt du schon alles ;)
Frag' mich nicht, ich putz' hier nur...
Benutzeravatar
p0llux
Matt Eicheln
 
Beiträge: 841
Registriert: 07.12.05 17:03
Wohnort: Aachen

Beitragvon Sieben » 29.11.06 20:21

Jo, danke trotzdem....
Sieben
 
Beiträge: 94
Registriert: 23.03.06 16:34
Wohnort: Aachen / Willich
Studiengang: Informatik (Dipl.)
Studiert seit: WS 06/07
Anwendungsfach: BWL

Beitragvon Mindlessinc » 29.11.06 21:10

@Pollux

Gegenbeispiel bei 3->1?
Bei mir sind alle drei äqui. hhmmm...
Mindlessinc
 
Beiträge: 24
Registriert: 11.03.06 00:20

Beitragvon fw » 29.11.06 21:11

ein gegenbeispiel ist jeder graph der einen hamiltonkreis enthält aber selber kein kreis ist, dann gilt naemlich die geforderte äquivalent der kantenrelation nur in eine richtung
Benutzeravatar
fw
 
Beiträge: 1356
Registriert: 17.05.06 19:37
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: Mathe

Beitragvon p0llux » 29.11.06 21:32

Mindlessinc hat geschrieben:@Pollux

Gegenbeispiel bei 3->1?
Bei mir sind alle drei äqui. hhmmm...


Also. V={1,2,3,4}

Kreis K sei der Graph mit Kanten (1,2) (2,3) (3,4) (4,1) - also im kreis ;)

Graph G habe auch V knoten und die Kanten (1,3) (3,1).

Bilde ich jetzt 1,3 auch 1 und 2,4 auf 3 ab, dann hab ich nen starken homomorphismus vom Kreis zum Graphen. Graph enthält keinen Hamiltonkreis.
Frag' mich nicht, ich putz' hier nur...
Benutzeravatar
p0llux
Matt Eicheln
 
Beiträge: 841
Registriert: 07.12.05 17:03
Wohnort: Aachen

Beitragvon Nomar » 29.11.06 22:28

p0llux hat geschrieben:1 und 2 sind bei mir äquivalent, 3 halt nicht. Bei 1->2 und 2->1 hab ich mich halt an die Definitionen geklammert und danach für 3->1 ein gegenbeispiel gebracht.

Vorsicht! 1 -> 2 ist Trivial, aber 2 -> 1 gilt nur, wenn der Kreis schon ein Hamiltonkreis ist. Gegenbeispiel: Nimm den Kantenzug 1->2->3->4->5->3->1 in einem Graph mit 5 Ecken (sieht aus wie 'ne Schleife) und versuch' das zu einem Hamiltonkreis zu verbiegen - geht nicht, zumindestens nicht mit der Bedingung das das bijektiv sein muss.
Do not worry about your difficulties in mathematics, I assure you that mine are greater.
\;\;\;\;-- Einstein
Benutzeravatar
Nomar
 
Beiträge: 107
Registriert: 15.09.06 14:12

Beitragvon fw » 29.11.06 22:32

jeder kreis enthält einen hamiltonkreis.. was willst du sagen?

die aussage ist: es gibt einen homomorphismus VON EINEM KREIS in G.. nicht "von einem graphen der einen kreis enthält"! sondern ein graph der ein kreis IST!
Benutzeravatar
fw
 
Beiträge: 1356
Registriert: 17.05.06 19:37
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: Mathe

Beitragvon Nomar » 29.11.06 22:35

fw hat geschrieben:jeder kreis enthält einen hamiltonkreis.. was willst du sagen?

die aussage ist: es gibt einen homomorphismus VON EINEM KREIS in G.. nicht "von einem graphen der einen kreis enthält"! sondern ein graph der ein kreis IST!


Hmm... guter Einwand. Ich nehme alles zurück und behaupte das Gegenteil.
Do not worry about your difficulties in mathematics, I assure you that mine are greater.
\;\;\;\;-- Einstein
Benutzeravatar
Nomar
 
Beiträge: 107
Registriert: 15.09.06 14:12

Beitragvon sHaddN » 29.11.06 22:53

pollux:
damit könntest du probleme kriegen.
die formulierung sagt nur es existiert ein kreis bla bla...
wenn du nun einen bestimmten Kreis angibst für den es nicht geht ist das kein korrekter beweis.
sHaddN
 
Beiträge: 124
Registriert: 13.01.06 19:46

Beitragvon kb » 29.11.06 23:32

doch, genau das ist es. er zeigt damit, dass folgendes nicht gilt:
"es gibt einen starken..." => "G ist ein Hamiltonkreis".
Diese Aussage ist falsch, weil es nicht immer zutrifft. Ganz einfach =]

--edit--
btw, hab die gleiche Lösungen wie Pollux und auch die gleiche Methode für (1 !<=> 3) genommen, allerdings ein anderes Beispiel.
Benutzeravatar
kb
 
Beiträge: 1237
Registriert: 06.04.06 21:20
Wohnort: Aachen / Köln


Zurück zu Theoretische Informatik