This post has been edited 1 times, last edit by "Sebastian" (Jul 17th 2010, 11:19am)
This post has been edited 1 times, last edit by "Skuld" (Jul 18th 2010, 1:27pm)
Ich hätte da Interesse.Besteht eigentlich Interesse an Lösungen zu den Klausuraufgaben? Zu einigen könnte ich welche (bzw. Ansätze) beisteuern - natürlich ohne Gewähr.
"Juchu", das hab ich auch :/ Hab da zwei Minuten Zeit dran verloren, weil ich zuerst an Stirlingzahl 1. Art dachte...Dito, wenn ich die Aufgabenstellungen wieder vor mir sehen würde.
Eine Aufgabe ist mir wieder eingefallen (glaube ich). War in Aufgabenteil 3 mit den Fixpunktsachen.
Erläutern Sie kurz die Formel
Lösung: Mit halten wir die Fixpunkte in n fest. Übrig bleiben die Permutationen über n-k ohne Fixpunkte (da wir diese ja gerade festgehalten haben). Dies sind genau bzw. viele (wobei D = Dérangement-Zahlen, Anzahl an fixpunktfreien Permutationen).
This post has been edited 1 times, last edit by "fragenfrager" (Jul 18th 2010, 3:05pm)
Totale Quasiordnung ist ja definiert durch R reflexiv und transitiv. Glaube man sollte auch zeigen dass wenn R eine schwache Ordnung ist, R komplement dann eine totale Quasiordnung ist. Zeigt man meine ich dadurch, dass wenn von der schwachen Ordnung das Komplement gebildet wird, die Irreflexivität zur Reflexivität wird und in der Aufgabenstellung gegeben war, dass R komplement transitiv ist. Damit sind Reflexivität und Transitivität erfüllt und es ist eine totale Quasiordnung.
This post has been edited 1 times, last edit by "Alarion" (Jul 18th 2010, 4:07pm)
Mist, die Totalität hatte ich ganz vergessen. Naja, der Rest stimmt hoffentlich.Naja, um eine totale Quasiordnung zu sein muss sie natürlich auch total sein. Aber das Komplement einer Antisymmetrischen Relation ist dies ja zwangsläufig (denn bei Antisymmetrie ist entweder (x,y) oder (y,x) oder keins von beiden enthalten => im Komplement ist auf jedenfall eins von beiden)
Totale Quasiordnung ist ja definiert durch R reflexiv und transitiv. Glaube man sollte auch zeigen dass wenn R eine schwache Ordnung ist, R komplement dann eine totale Quasiordnung ist. Zeigt man meine ich dadurch, dass wenn von der schwachen Ordnung das Komplement gebildet wird, die Irreflexivität zur Reflexivität wird und in der Aufgabenstellung gegeben war, dass R komplement transitiv ist. Damit sind Reflexivität und Transitivität erfüllt und es ist eine totale Quasiordnung.
Ja, daran erinnere ich mich auch, das Ergebnis hatte ich auch raus.Die Sache mit den Wörtern aus dem Alphabet, das war Multinomialkoeffizient (5040 als Ergebnis?). Ich mein, das war in Aufgabe 2 eine Teilaufgabe.
Ich meine, man sollte zeigen, dass eine schwache Ordnung R (also R ist irreflexiv und antisymmetrisch, das Komplement transitiv) auch transitiv ist.Quoted
Bei Aufgabe 3 kann ich mich an folgendes erinnern:
- zu zeigen: Eine Ordnung ist eine schwache Ordnung gdw transitiv
Da waren vier Relationen? Ich kann mich nur an drei erinnern. Habe ich eine übersehenQuoted
- gegeben sind 4 Relationen S={(x,y)| x/y}, T={(x,y)|x<y}, U={(x,y)|x!=y}. Welche davon sind schwache Ordnung? (bin mir bei T nicht sicher, ob das "kleiner" oder "echt kleiner" war, die letzte Relation fällt mir auch gerade nicht ein...
Die Fallunterscheidung bezog sich auf das Komplement des Graphen - es ging darum, ob das Komplement ein Wald ist. Ich meine, für n = 3 oder n = 4 ja, sonst nein (man erhält dann Zykel).Quoted
Außerdem kann ich noch beisteuern: Aufgabe 4 war das Rad mit n=Anzahl der äußeren Punkte eines Rades, welche ringförmig, sowie paarweise mit einem weiteren Punkt in der Mitte ("Achse") verbunden waren. Eine Frage war nach Eulertour, die andere nach Hamilton (mit Fallunterscheidung), eine weitere Frage war, ob es einen nicht-isomorphen Graphen mit der gleichen Gradfolge gibt und davor glaub ich war noch eine Frage bezüglich der Komplementierung dieses Graphen...
Doch, es gibt nicht-isomorphe Graphen mit gleicher Gradzahl, und zwar für n mindestens 6. Du kannst dann aus den äußeren Knoten mindestens zwei Kreise bilden, von denen jeder Knoten mit dem mittleren verbunden ist. Nimmst du den mittleren Knoten aus den Graphen weg, hast du für W einen Kreis, für W' mindestens zwei, also sind sie nicht isomorph.Wenn ich mich richtig erinnere, hat es keine Eulertour, aber einen Hamiltonpfad und außerdem keinen nicht isomoprhen Graphen mit gleicher Gradfolge. Letzteres begründet, indem ich gezeigt habe, dass wenn man einen neuen Knoten einfügt, er den Grad 3 haben muss, seine Nachbarknoten ebenfalls (also muss man ihn zwischen zweien einfügen), und er eine Kante zur Mitte des Rads haben muss, da diese den Grad n (= Anzahl äußerer Knoten) haben muss. Damit ist der entstehende Graph wieder ein solches Rad.
Meinst du den Weg anzugeben reicht, oder hast du das noch genauer gezeigt? Habe nämlich auch angegeben, dass es diesen Weg gibt, aber nicht weiter ausgeführt.Hamilton: ja, einfach einmal rum und dann in die Mitte.
Quoted from "Nagezahn"
Doch, es gibt nicht-isomorphe Graphen mit gleicher Gradzahl
This post has been edited 1 times, last edit by "Skuld" (Jul 18th 2010, 4:12pm)
This post has been edited 1 times, last edit by "Nagezahn" (Jul 18th 2010, 5:17pm)