Wenn dies dein erster Besuch hier ist, lese bitte zuerst die Hilfe - Häufig gestellte Fragen durch. Du musst dich registrieren, bevor du Beiträge verfassen kannst. Du kannst auch jetzt schon Beiträge lesen. Suche dir einfach das Forum aus, das dich am meisten interessiert.
Doch noch ne Frage zu Zahlenmengen (wahrscheinlich mega einfach, bin aber grade zu dumm)
Für eine Zahlenmenge M sind die folgenden 3 Eigenschaften bekannt:
M enthält die Zahl 27.
Falls M eine Zahl x enthält, so enthält sie auch die Zahlen x+3 und x−6.
Außer den Zahlen, die gemäß 1. und 2. in M enthalten sind, enthält M keine weiteren Zahlen.
Laut diesem hier komme ich drauf, dass in M ja nur 27,30 und 21 enthalten sind. Laut meiner Lösung sind auch die Zahl -12, jede Zahl 2n wenn n enthalten ist und eine Zahl die durch 125 teilbar ist enhalten. Wie kommt man da drauf? Oder hab ich die Sache mit der Zahl x falsch interpretiert?
Aber eigentlich heißt es ja falls es eine zahl x gibt, die gibt es, die ist 27. Also gibt es auch 30 und 21. Sonst nichts.
das entscheidende markier ich dir mal.
was passiert wenn du jetzt 21 als dein x annimmst? richtig, neue zahlen! (so kannst du das beliebig weit fortsetzen, die menge ist unendlich)
Bei der Lösung mit einem linearen Programm https://de.m.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Formulierung_als_ga nzzahliges_lineares_Programm wird eine Subtour Eliminationsbedingung (SEC) benötigt, im Beispiel [2]. Warum reicht es nicht, wenn diese >=1 gesetzt wird? In Verbindung mit [1] würde dadurch doch automatisch jede Teilmenge eine ausgehende und eingehende Verbindung haben.
Vielleicht kann mir auch jemand anhand einer Skizze erklären, warum die Gleichung >=2 sein muss.
Bei der Lösung mit einem linearen Programm https://de.m.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Formulierung_als_ga nzzahliges_lineares_Programm wird eine Subtour Eliminationsbedingung (SEC) benötigt, im Beispiel [2]. Warum reicht es nicht, wenn diese >=1 gesetzt wird? In Verbindung mit [1] würde dadurch doch automatisch jede Teilmenge eine ausgehende und eingehende Verbindung haben.
Vielleicht kann mir auch jemand anhand einer Skizze erklären, warum die Gleichung >=2 sein muss.
Danke!
Im Falle =1 würdest du von einem Kurzzyklus in den anderen kommen, aber nicht mehr raus. Sonst würdest du eine Kante doppelt gehen.
aber wird nicht gerade das durch bedingung 1 verhindert, dass jeder knoten genau 2x "getroffen" wird. bei genau =1 kann ich es nachvollziehen, aber warum bei >=1
sry für nicht-mathematische sprache
/ok, ich glaub mein denkfehler ist einfach, dass die SEC >=2 sein muss, weil sie sonst nicht alleine stehen kann und bei >=1 nur in verbindung mit gleichung (1) ihren zweck erfüllt
Du darfst das zweite Bild nicht nehmen und da einfach zwei Verbindungen hinzufügen um die SEC Bedingung zu Erfüllen. Das verletzt natürlich Bedingung (1), aber, wenn du das umkonstruierst und in den zwei Kurzzyklen die senkrechte Kante wegnimmst und die zwei Diagonalen hinzufügst die jeweils zum anderen Kurzzyklus gehen hast du eine Tour die beide Bedingungen erfüllt. Das ist dann eine gültige Tour.
Ansonsten mal vielleicht mal ein Beispiel auf, wo du das Problem skizzieren kannst (Paint reicht).
@3Green
Antwort auf deine ursprüngliche Frage(n):
">= 1" reicht in [2] nicht, siehe das zweite skizzierte Beispiel (die zwei Kurzzyklen rechts neben der Bedingung [2]) auf dem verlinkten Artikel der Wikipedia. Das Beispiel ist keine gültige Tour, und falls man S als die Menge der Knoten im linken Zyklus wählt, so verschwindet die rechte Seite der Bedingung [2] zu Null.
Wichtig in der Bedingung [2] ist, dass sie im Gegensatz zu [1] für jede nicht triviale Teilmenge S von V gilt (Bedingung [1] gilt nur für jeden Knoten i in V).
Deshalb sehe ich auch nicht, wie du Gleichung [1] in [2] anwenden möchtest. Die Summe [2] ist komplett anders von [1], falls 2
Ich versuchs mal mit einer Skizze, danke für eure Geduld.
Die Tour in der Skizze ist noch nicht fertig. Da aber Bedingung [1] nur erfüllt wird, wenn jeder Knoten zwei Kanten hat, gibt es doch keine andere Option mehr, als dass Knoten X und Y verbunden werden. Ich verstehe also nicht, wann überhaupt Bedingung 2 >=1 zu einer ungültigen Lösung führen kann, denn sobald eine Kante aus S heraus führt, bleibt ein Knoten zurück, der nur eine Kante hat und somit später noch "angesteuert" werden muss.
Vielleicht könnt ihr mir ein Gegenbeispiel skizzieren?
Es gibt folgende Abbildung:
(G, °) := (ZZ mod 12, +) , (H, *) := (ZZ mod 3, +)
phi : G ê [a] mod 12 ---> [a] mod 3 e H
ich wollte prüfen ob die Abbildung wohldefiniert ist und habe folgendes gerechnet:
[a]mod12 = [b]mod12
a =* b (mod 12)
12|(b-a)
(Ê k e QQ)[12k=b-a]
3|(b-a)
a =* b (mod 3)
[a]mod 3 = [b]mod 3
Spoiler:
ê = e umgedreht
e = Element von
=* kongruent-Gleichzeichen
Ê = existenz-Quantor
ZZ=Menge ganzer Zahlen
QQ= Menge rationaler Zahlen
| = teilt
Wir haben das in der Vorlesung und in den Übungen nicht besprochen aber darf man ein k Element von aller Rationalen Zahlen nehmen anstatt aller ganzen Zahlen?
Wenn nein, wie sonst könnte man zeigen dass die Abbildung wohldefiniert ist (wurde zwar nie so in der Form gefragt ist aber für mich trotzdem interessant).
Also erstmal können das unmöglich alles Äquivalenzumformungen ("") sein. Dein k muss aber aus ZZ sein, sonst wären 2 beliebige ganze Zahlen immer kongruent, und das kann ja nicht gemeint sein.
Die ersten 4 bzw die letzten 3 Aussagen sind jeweils die gleiche Aussage anders formuliert. Zwischen der 4. und der 5. Zeile liegt nur eine Implikation, aber kein Äquivalenz vor.
Kommentar