Kurs:Diskrete Mathematik (Osnabrück 2020)/Forum

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Vista-kmixdocked.png

Neuer Beitrag

Frühere Zulassung[Bearbeiten]

ich habe bereits eine Zulassung für Diskrete Mathematik. Kann ich an den Abgaben teilnehmen ohne das ich meine Zulassung verliere?

Ja, aber bitte nur in einer festen Abgabegruppe mit ca. fünf Leuten, wegen Tutorkapazität.

Frühere Zulassung 2[Bearbeiten]

Kann man mit einer früheren Zulassung an der Klausur mitschreiben?

Ja.

Frühere Zulassung 3[Bearbeiten]

Wie wird eine frühere Zulassung überprüft?

Das wird unmittelbar (ca. eine Woche davor) vor der Klausur mit den früheren Dozenten überprüft. Es besteht kein Handlungsbedarf Ihrerseits.

Erste Abgabe[Bearbeiten]

Umfasst die erste Abgabe am 30.04. die Übungszettel der ersten vier Vorlesungen?

nein, nur die beiden Zettel der ersten Woche. Die erste Woche beginnt morgen (20.04.20), auch wenn es die Videos schon gibt.

Frage zu Aufgabe 19 von Blatt 1[Bearbeiten]

Hallo,

ich hab mal die abzugebenden Aufgaben vom ersten Übungsblatt überflogen. Bei Aufgabe 19 ist mir aufgefallen, dass der Beweis relativ einfach ist, wenn man ein bisschen mit Durchschnitten und Differenzen von Mengen arbeitet (und bemerkt, dass ein paar davon (offensichtlich) disjunkt sind). Ist es erlaubt Aussagen wie "M vereinigt N = M vereinigt (N ohne (M geschnitten N))" oder "M und (N ohne (M geschnitten N)) sind disjunkt" ohne Beweis zu verwenden (in Analysis 1 musste ich zu Beginn ähnlich komplexe Aussagen beweisen; der Beweis ist auch nicht schwierig, nur würde dann die Abgabe sehr lang werden, wenn man diese Aussagen auch noch beweisen müsste)? Ich würde mich über eine Klarstellung freuen um einen (mMn unnötigen) Punktabzug zu vermeiden.

Beste Grüße und Gesundheit wünscht

Jannik Voges

mengentheoretische Grundtatsachen können verwendet werden.

Tutorium & Aufgaben[Bearbeiten]

Für den normalen (analogen) Verlauf des Semesters wurde ein Tutorium geplannt. Wird es jetzt auch so etwas geben?

nein. Die Übungen werden in der Form von Kommentaren zu einzelnen Aufgaben gemacht. Diese werden teilweise auch Hinweise zu Lösungsansätzen enthalten.

Werden nur Lösungen für die Abgabe-Aufgaben veröffentlicht oder auch für die anderen Aufgaben?

es werden keine Lösungen veröffentlicht, es wird aber ein Feedback zu typischen Fehlern geben.

Was bedeutet *? Z.B. Aufgabe 11 wird mit * gekennzeichnet?

das bedeutet, dass es dazu eine Lösung gibt. Diese sieht man, wenn man auf die Aufgabe direkt geht und dann auf den Lösungslink. Es gibt also für manche Aufgaben eine Lösung, für manche einen Kommentar.

Vielen Dank

Übungen Aufzeichnung oder Stream[Bearbeiten]

Werden die Übungen aufgezeichnet oder live gestreamt?

Weder noch. Die Übung findet nur in der Form statt, dass aus den Aufgaben einige (ca. 3 pro Blatt, so viele würden etwa besprochen werden) mit einem ausführlichen Kommentar versehen werden (siehe die ersten beiden Aufgabenblätter), wo die Begriffe, Lösungsansätze etc. anhand der Aufgabe erläutert werden. Dort sollen auch spezifische Fragen zu den besprochenen Aufgaben gestellt werden. Insbesondere werden solche Aufgaben besprochen, die ähnlich auch als Aufgaben zum Abgeben drankommen.

Fehler im Skript[Bearbeiten]

Unter Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 3 ist ein Fehler in der Siebformel für 3 Mengen. Der letzte Teil müsste addiert werden. Ich habe schon gesehen wie man in den eigentlichen Bereich der Siebformel kommt. Ist es im Allgemeinen gewünscht, dass wir Fehler selbst beheben, diese unter Diskussion aufzeigen oder lieber hier im Forum schreiben?

Offensichtliche Fehler können Sie direkt korrigieren, hier im Forum ist immer sehr gut. Jedenfalls unbedingt melden, das gibt auch Allquantorpunkte, Danke.

Aufgabe 1.21[Bearbeiten]

In der Aufgabe steht das wir nur eine bijektive Abbildung definieren sollen, muss das auch bewiesen werden !

bitte Blattnummer mitangeben. Das muss begründet werden, dass es sich um eine Bijektion handelt, wie ja alles begründet werden muss. In diesem Fall liegt aber die Hauptschwierigkeit darin, die Abbildung hinzuschreiben (es kann hilfreich sein, auch die Rückabbildung explizit hinzuschreiben). Siehe auch den Kommentar zu Aufgabe 1.17.

Punkteverteilung pro Aufgabenblatt[Bearbeiten]

Ist es möglich einzusehen bei welcher Aufgabe wie viele Punkte erreicht wurden?

das werden die Tutoren in Zukunft tun.

Abgabe Woche 3[Bearbeiten]

Für die Abgabe in Woche 3 würde eigentlich Blatt 5 und 6 anstehen, aber man kann Blatt 6 noch nicht runterladen und die 6. Vorlesung wäre eigentlich am 1.Mai gewesen. Muss man dies dann trotzdem abgeben?

nein, diese Woche ist Woche 3 und es ist Woche 2 abzugeben (Blatt 3 und 4), nächste Woche ist Blatt 5 und 6 abzugeben, morgen halte ich Vorlesung 6 (wg Feiertag sind die Vorlesungen nur noch eine im Vorsprung)

Aufgabe 4.28[Bearbeiten]

Wir haben jetzt ein Programm geschrieben (Pseudocode), das alle möglichen Abbildungen von S auf S in der Menge M speichert. Welche Verknüpfungstabelle sollen wir jetzt ausgeben, auf welcher Verknüpfung?

die Tabelle für die Verknüpfung auf M, also durch Hintereinanderschaltung; das sollte auch das Programm machen (es ist eine 27+27-Tabele).

Musterlösungen für Aufgaben[Bearbeiten]

Hallo

Besteht die Möglichkeit, Musterlösungen für die Aufgaben nach deren Abgabefrist hochzuladen? Falls dies bisher wegen hohem Arbeitsaufwand seitens der Tutoren / Übungsleiter verworfen wurde, könnte ja die korrekte Lösung von den Teilnehmern (sofern eine Gruppe eine korrekte Lösung zu einer Aufgabe eingereicht hat) hochladen. So in etwa wird es auch bei Zufallsgraphen dieses Semester getan. Oder wir Teilnehmer können es selber hochladen, falls wir zukünftig auch die genauen Punktezahlen zu den einzelnen Aufgaben mitgeteilt kriegen.

die Punkte (siehe oben) werden zukünftig aufgabenweise mitgeteilt. Volle Punktzahl heißt nicht unbedingt Musterlösung. Die Studenten können ihre Lösungen natürlich untereinander vergleichen und austauschen, ich möchte das aber nicht, auch in Hinblick auf zukünftige Durchläufe, auf StudIP organisieren. Generell werden Musterlösungen überschätzt.

Aufgabe 5.30[Bearbeiten]

Wird bei Aufgabe 5.30 mit "(...) der natürlichen (...) Multiplikation von Endomorphismen (...)" quasi die Matrizenmultiplikation der zu den Endomorphismen dazugehörigen Matrizen gemeint?

im Prinzip ja, wenn Sie eine Basis fixieren. Es ist aber einfacher und direkter, mit der (Summe und der) Hintereinanderschaltung der linearen Abbildungen zu arbeiten.

Fehler im Skript?[Bearbeiten]

In Definition 6.1 wird die Faser erklärt. Dort steht, dass n in M liegt. Kann es sein, dass eigentlich n in N liegt?

sehr richtig, Danke, 1 Allquantorpunkt.

Aufgabe 7.30[Bearbeiten]

In Aufgabe 7.30 soll man zunächst zeigen, dass in einer Menge M mit einem einzigen maximalen Element m dieses Element auch das größte Element von M sein muss. Allerdings soll man anschließend eine Menge mit genau einem maximalen Element angeben, dass nicht das größte Element von M ist. Widerspricht sich das nicht?

sehr richtig, im ersten Teil soll die Menge endlich sein!! Schon wieder ein Punkt.

möglicher Fehler im Skript[Bearbeiten]

In Definition 7.13 (Vl 7 S. 4) müsste es doch am Ende F(x)≤2F(x')heißen, anstelle von F(x)≤1F(x').

das ist in der Netzseite schon korrigiert, Pdf-Version folgt morgen.

Aufgabe 5.32[Bearbeiten]

Ist anzunehmen dass die Zeiger sich "teleportieren" wenn sie von einer Stunde zur nächsten / von einer Minute zur nächsten übergehen, oder bewegen sie sich wie bei einer analogen Uhr? bzw ist eine minimale Bewegungsfrequenz vorgegeben?

Beide Zeiger laufen analog und kontinuierlich, beide Zeigerwinkel sollen also proportional zur Zeit sein.

Ordnungen bestimmen[Bearbeiten]

Was genau heißt "Bestimmen Sie Ordnungen"? Wie kann man das machen?

Das bezieht sich wohl auf Aufgabe 7.26 und Aufgabe 7.27. Man hat eine endliche Menge, deshalb gibt es darauf überhaupt nur endlich viele Relationen und damit auch nur endlich viele Ordnungen. Bei einer endlichen Menge kann man eine Relation/Ordnung dadurch beschreiben (bestimmen), dass man explizit alle Paare auflistet, die zur Relation gehören. Dies soll man bei den Aufgaben tun (wobei man den feinen Unterschied in der genauen Formulierung beachten soll). Statt einer Auzählung der zugehörigen Paare pro Ordnung kann man auch mit Pfeildiagrammen arbeiten.

Ist auch eine Darstellung bspw. der Art: möglich?

ja, sagen Sie dann dazu, dass Sie das transitiv meinen. (so meinen Sie das doch, dass Sie nicht explizit auflisten.)

Fehler in Vorlesung und Skript?[Bearbeiten]

In der Vorlesung 7 erklären Sie in Minute 77, mit einem Beispiel über die echten Teiler von 12, den Unterschied zwischen maximalen und größtem Elementen. Dort haben Sie erklärt, dass die Teiler 4, 3 und 6 die größten Elemente sind, bspw. 6, weil es kein Element in der Menge der Teiler (6,4,3,2,1) gibt, dass durch 6 echt geteilt wird. Aber die 3, die Sie als größtes Element genannt haben, hat doch mit der 6 eine Zahl in der Menge die sie teilt. Ist dies ein Fehler in der Vorlesung und die größten Elemente sind eigentlich nur die 4 und die 6 oder habe ich da etwas falsch verstanden?

das soll ich gesagt haben? das ist natürlich Quatsch. Wenn man nur die echten Teiler anschaut, sind 4 und 6 maximal, es gibt kein größtes Element. Bei allen Teilern (mit der 12) ist 12 das größte und das einzige maximale Element.
Oh, jetzt habe ich beim Tippen größtes und maximales verwechselt. Sie sprachen von maximalen Elementen, aber hatten fälschlich die 3 dabei. Danke.

Im Skript in der Definition 7.21 fehlt, glaube ich, die Einschränkung für das minimale Element.

richtig, Danke.

Aufgabe 8.40[Bearbeiten]

Soll angegeben werden, nach wie vielen Schritten insgesamt wieder 0:0:0 erreicht wird, oder soll angegeben werden, wie oft die Sekundenanzeige, wie oft die Minutenanzeige, wie oft die Stundenanzeige jeweils vorangezählt wurden?

die Anzahl der Schritte, also wie oft 11:11:11 dazuaddiert wird. Was mit den einzelnen Teilen passiert, ist egal.

Aufgabennummer[Bearbeiten]

Da ändern sich regelmäßig die Nummer der abzugebenden Aufgaben, nachdem wir sie schon bearbeitet haben. Es ist natürlich kein großes Problem, aber vielleicht wäre es möglich, sie anders zu nummerieren? Normale Aufgaben 1, 2, 3... und die abzugebenden I, II, III, IV... oder A, B, C oder A1, A2, A3...? Dann hätten die normalen und deren Anzahl keinen Einfluss auf die Nummer der aufzugebenden....

es gilt immer die Nummer, wenn das Pdf fertig ist. Danach änder ich eigentlich nix mehr.

Isomorphie von Verbänden[Bearbeiten]

Hallo,

was muss für die Isomorphie von 2 Verbänden gezeigt werden? Irgendwie wird das nie so richtig im Skript erwähnt.

MfG

es geht um Isomorphie von geordneten Mengen, also eine bijektive Abbildung mit genau dann, wenn ist. Das ist ein Spezialfall von Definition 6.17 (hab ich aber zugegebenermaßen erst später formuliert). Man kann auch sagen bijektiv monoton wachsend und Umkehrabbildung ebenfalls monoton wachsend.

Aufgabe 10.28 Springmauspopulationen[Bearbeiten]

Was ist mit Springmauspopulationen gemeint? Ist gemeint wie viele Gruppen von Mäusen es geben kann, die sich nie begegnen können? Also wie in der Grafik des Beispiels 10.15 und jede Farbe ist eine Population?

ja, wenn sie sich begegnen können, ist das eine Population, sonst nicht. (Sagen Sie sicherheitshalber Populationsklassen statt Gruppen, das trifft den Sprachgebrauch zu den Äquivalenzrelationen besser; die angegebenen Sprünge definieren eine Untergruppe, und das ist eine Äquivalenzklasse, die anderen Äquivalenzklassen sind keine Gruppen, diese Begriffe haben wir aber erst in 11 eingeführt). Und ja, wie in 10.15.

Testklausur[Bearbeiten]

Hallo, ich habe gerade zufällig gesehen, dass am Samstag, den 6.6, eine Testklausur bei den Terminen eingetragen ist. Findet diese statt?

nein. Termin und Format einer Klausur ist im Moment unklar, keine Testklausur.

Kleiner Fehler in Aufgabe 14.14 (Nummerierung: Stand 02.06)[Bearbeiten]

Es muss am Ende g = h \circ f heißen, nicht g = f \circ h.

richtig, Danke.

12.39[Bearbeiten]

Kann mir einer sagen was K^X beduete also das mit dem X ist damir K x K x K x .. das Kreuzprodukt geiment ? Gruß

das ist einfach . Für jeden Ring bezeichnet man mit die menge der Einheiten (der invertierbaren Elelmente), bei einem Körper ist nur die 0 nicht invertierbar. Die Bezeichnung hatte ich glaub wirklich nicht eingeführt.

13.23[Bearbeiten]

Wie ist fi genau zu werten: Fi(X^y) = a1a2a3...ak oder fuer jedes monom genau ein a elemnt Z/n also Fi(X^y) = a ?


Es ist , also jede Variable geht auf eine (Restklasse einer) Zahl. Das legt alles fest. Wenn etwa , und geht, muss

auf gehen. Siehe insbesondere auch den Kommentar zu Aufgabe 13.10, ohne das ist die Aufgabe wirklich schwer zu verstehen.

Gibts vllt einen Tipp fuer die Aufgabe, der mich vllt auf die richtigen schienen bringt, weil ich kann mir nicht richtig vorstellen dass es so einen Erzeuger gibt, da ich doch immer prüfen kann ob ein X^t von einem X^v geteilt werden kann und dann entscheiden kann ob im Ideal (fi = 0) oder nicht (fi != 0). Wo mache ich den Fehleer ?

Es gibt nicht einer Erzeuger, sonderen um mehrere Erzeuger eines monomialen Ideals, also ein Ideal wie . Mit einem einzigen Monom können Sie in der Tat kein Beispiel angeben. Es gibt aber schon ein relativ einfaches Beispiel.

Gruß

Aufzeichnung Vorlesung 15[Bearbeiten]

Die Vorlesung vom 05.06.2020 ist noch nicht in studip einsehbar. Gibt es dafür einen bestimmten Grund oder ist möglicherweise an einer Stelle ein Fehler aufgetreten?

keine Ahnung.

Die Vorlesung 15 fehlt weiterhin. Sind Sie in Rücksprache mit dem VirtUOS für die fehlende Vorlesung von Freitag? Oder sollen/müssen wir jetzt mit dem Skript vorlieb nehmen?

gefragt hab ich, die von gestern (16) ist da. Generell empfehle ich, mit beiden Sachen (und mit den Aufgabenblättern und mit ... ) zu arbeiten.
Es gibt wohl (Info von Virtuos) keinen Ton bei der Aufnahme, sie kann also leider nur tonlos zur Verfügung gestellt werden.

Graphhomomorphismus[Bearbeiten]

Für einen Graphhomomorphismus phi muss gelten, dass (phi(v), phi(v')) Element von der Kantenmenge F ist. Warum ist das dann injektiv im wesentlichen das gleiche wie ein Untergraph? Beim Untergraph können doch auch Knoten oder Kanten verloren gehen. Was wäre dann phi(w), wenn w verloren geht? Und wenn im (u, u') Element von E ist, aber im Untergraph nicht mehr, wäre dann (phi(u), phi(u')) nicht kein Element von F?

ich glaub Ihr Problem beruht auf den gewählten Bezeichnungen in Untergraph und Graphhomomorphismus. Zu einem Untergraphen in gehört der injektive Graphhom von nach , es gibt i.A. dazu keine Abb in die umgekehrte Richtung.

Danke!

Möglicher Fehler in Lemma 16.12[Bearbeiten]

Im Beweis vom dritten Teil des Lemmas 16.12 fehlt noch eine Summe nach dem letzten Gleichheitszeichen.

stimmt, Danke

Homomorphismen / Isomorphismen von Graphen[Bearbeiten]

Hallo, ich verstehe die Defintion des Graphhomomorphismus (:= GH.) so (wahrscheinlich falsch): Seien G,H Graphen und Phi: G->H ein GH. Dann hat H gleich viele Kanten wie G

nein, dass stimmt bei einem Homomorphismus nicht. Eine Kante muss zwar auf eine Kante abgebildet werden, aber nicht jede Kante muss erreicht werden. Extremfall ist gleiche Knotenmenge V mit einerseits leeren Kantenmenge und andererseits vollständiger Graph. Die Abbildung

ist ein Homomorphismus.


und demnach kann man auch eine Umkehrabbildung von H nach G angeben (zumindest konnte ich das in jedem Beispiel, das ich mir bisher aufgezeichnet habe: Ich bin dabei wie folgt vorgegangen: Wenn ich a, b, c, d auf e, f, g, h abgebildet habe, so habe ich diese Zuweisung genau wieder umgekehrt gemacht, sprich e, f, g, h auf a, b, c, d abgebildet). Was verstehe ich falsch? Was wäre ein Beispiel für ein GH., der kein Isomorphismus ist? //Edit: Ich habe eventuell doch ein Gegenbeispiel gefunden: Sei G = ({1, 2, 3, 4}, {{1,2},{3,4}}) (also ein Graph, wo 1 mit 2 und 3 mit 4 verbunden ist) und H = ({1, 2}, { {1, 2} }) (also ein Graph, wo nur 1 mit 2 verbunden ist). Ist dann 1 |-> 1, 2|->2, 3|->1, 4|->2 ein Graphhomomorphismus, der nicht bijektiv (kein Isomorphismus) ist? Falls dieses Beispiel valide ist, gibt es denn noch ein Gegenbeispiel, wenn die Knoten- bzw. Kantenanzahl gleich bleibt, oder fallen da dann die Begriffe zusammen?

Möglicher Fehler bei Aufgabe 17.17?[Bearbeiten]

Hallo, wurde bei Aufgabe 17.17 eventuell statt d(u,v) <= 2 gemeint, dass die maximale Länge zwischen u und v <= 2 sein muss? Denn wenn nur d(u,v) <= 2 gefordert wird, kann es auch sein, dass dann G / ~ kein Baum ist, so wie ich das richtig verstanden habe. Denn betrachte z.B. den Graphen G mit V = {u, w_1, w_2, w_3, v}, E = {{u, w_1}, {w_1, w_2}, {w_2, w_3}, {w_3, v}, {w_1, v}}.

das ist kein Baum, da man ja den Kreis hat. Maximale Länge ergibt keinen Sinn, da man ja bei einer Kante beliebig oft hin-und herwechseln kann.
Stimmt, danke!

Dann gilt d(u,v) = 2. Aber (soweit ich G / ~ richtig interpretiert habe) G / ~ ist gegeben durch: V = {[u], [w_1], [w_2], [w_3]}, [u] = {u,v}, [w_i] = {w_i}, E = {{[u], [w_1]}, {[w_1], [w_2]}, {[w_2], [w_3]}, {[w_3], [u]}} und somit ist ({[u], [w_1]}, {[w_1], [w_2]}, {[w_2], [w_3]}, {[w_3], [u]}) ein Kreis, also stimmt die zu zeigende Aussage der Aufgabenstellung nicht.

Zu Aufgabe 18.16[Bearbeiten]

Ist da eine grafische Lösung (wie in Beispiel 18.13) gefragt oder genügt ein Beweis, bei dem Lemma 18.12 benutzt wird? Bei ersterem würde ich nämlich passen, denn der K_5 hat 125 Spannbäume und ich hatte schon bei Aufgabe 18.17 Probleme das ganze relativ übersichtlich auf eine Seite zu zeichnen. Wobei ein alternativer Beweis auch nicht eben trivial ist. Ich glaube, die Aufgabe ist einfach nur meh.

es soll rekursiv argumentiert werden, es muss aber nicht alles in einen Rekursionsbaum gepresst werden. Immerhin gibt es ja auch 5 Punkte.

Danke, habe die Aufgabe jetzt so komprimiert wie möglich gelöst. Mit einer Menge definierter Graphen und wiederholtem Anwenden von Lemma 18.12. Wirklich schön ist das ganze aber nicht.

Zu Aufgabe 17.22[Bearbeiten]

Hallo,

sind zwischen z.B. Odeonsplatz und Universität 2 Kanten oder werden diese zwei Kanten quasi als eine betrachtet?

als eine, wir betrachten U-Bahnen als einfache Kanten.

Klausur und Nachschreibtermin[Bearbeiten]

Steht bereits ein Termin für eine mögliche Nachschreibklausur fest oder bleibt der Termin wie geplant Anfang Oktober?

ist völlig unklar. Präsenzklausuren müssen zur Zeit zentral (Dekanat, Präsidium) beantragt werden, es braucht entsprechende Raumkapazitäten, etc.

Wird es denn (zumindest sehr wahrscheinlich) eine nachklausur geben?

ist unklar, mir ist keine universitätsweite Planung sagen wir für den Zeitraum Ende Semesterferien bekannt.

Wieso ist auf einem Graphen nicht jede bijektive Abbildung G --> G ein Graphenisomorphismus?[Bearbeiten]

Ich verstehe bei Beispiel 16.25 nicht, wieso z.B. die Permutation phi, die den C ganz rechts (nenne ich C_1) mit dem C eins links zu C_1 (nenne ich C_2) vertauscht und sonst alles lässt, kein Isomorphismus ist.

Das ist kein Graphhomomorphismus, da die Kantenbeziehung nicht erhalten bleibt. Wenn mit eine Kante bildet, muss auch mit eine Kante bilden. Im angegebene Beispiele wird auf abgebildet, aber das ganz rechts auf sich selbst. Es ist eine Kante, aber nicht.
Danke, jetzt verstehe ich es!

Denn falls phi(G) der Bildgraph ist (was man hierbei tut, so wie ich das verstanden habe - falls man nicht den Bildgraphen nimmt, können Sie mir sagen, welchen Graph man sonst durch phi erhält?), dann ist es doch einfach nur so, dass man C_1 zu C_2 bzw. C_2 zu C_1 umbenannt hat, aber in der Struktur sich nichts verändert hat, oder?

Richtig ist, dass bei einer bijektiven Abbildung auf eine Menge

(ohne vorgegebene Graphstruktur) der Bildgraph isomorph zum Ausgangsgraphen ist.

Probe-/Altklausuren zum Lernen[Bearbeiten]

Sie haben in der Veranstaltung Mathematik für Anwender 1 im letzten Semester Probe-/Altklausuren auf wikiversity hochgeladen. Werden/können Sie solche für diese Veranstaltung auch zur Verfügung stellen? Danke schonmal im Vorraus!

ja, aber nur eine oder so, bin dabei.
siehe unter Materialien.

18.18[Bearbeiten]

Wie genau ist das bei 18.18 gemeint mit "alle Kanten von G entweder zu F oder zu H gehören."?

also bei jeder Kante beide Knoten entweder zu F oder zu H gehören.


Bei folgendem Graphen G:

o-o
|~|
o o
|~|
o-o

sind doch

o
|
o
|
o

und

o-o
|
o
|
o-o

jeweils volle Untergraphen sodass alle Kanten aus G entweder zu einem der beiden Untergraphen gehören, und sodass der Schnitt der Knoten nicht leer ist. An welcher Stelle habe ich die Aufgabenstellung falsch verstanden?

Wenn ich Ihr Beispiel richtig verstehe, so ist da in der Tat die Kanteneigenschaft erfüllt, aber die beiden Vertexmengen haben nicht nur einen einzigen Punkt gemeinsam. Es geht um die Vereinigung von zwei Graphen an einem einzigen Punkt (man nennt das auch Verpfropfung)

Satz 2.1[Bearbeiten]

in Satz 2.1 heißt es, dass die Kardinalität einer Menge genau gleich der Summe der Kardinalitäten der Urbilder bzgl. einer (beliebigen) Abbildung ist. Müsste hier nicht die Einschränkung gelten, dass Satz 2.1 nur für bijektive Abbildungen gilt? gerade bei rein surjektiven Abbildungen ist doch nicht garantiert, dass jedes Element einer Startmenge genau auf ein Element der Zielmenge abgebildet wird.

der Satz ist so richtig. Jedes Element aus dem Definitionsbereich wird auf genau ein Element abgebidet, das ist Defintion von Abbildung. Dies darf man nur nicht falsch verstehen. Bei einer konstanten Abbildung wird auch jedes Element links auf genau ein Element rechts abgebildet, nur eben immer auf das gleiche. Jeder Fußballfan hat genau einen Lieblingsverein. Das konstituiert eine Abbildung, und die Anzahl der Fußballfans ist gleich der Anzahl der Fußballfans zu den einzelnen Vereinen.

"Corona-Gnaden-Klausur"[Bearbeiten]

Ich kann es zwar nachvollziehen, was Sie schreiben und uns sollte ja kein Vorteil durch das Virus entstehen, anderseits würde ich mich trotzdem freuen, wenn Sie berücksichtigen könnten, dass das Lernen in diesem Semester deutlich schwieriger ist als sonst, besonders durch fehlende direkte Kommunikation in der Vorlesung und fehlende Tutorien und Übungen. Eine Vorlesung war außerdem ohne Ton. Aus diesem Grund würde ich persönlich eine Klausur als "fair" bezeichnen, die doch ein ganz bisschen weniger anspruchsvoll wäre als im normalem Betrieb. Genauso wie kein Vorteil, sollte uns kein Nachteil entstehen.


-- Danke, ich bin vollkommen deiner Meinung und sehe es genauso.

Mit solchen Konstruktionen fangen wir nicht an, mein Bedauern. Ein kleiner Ausgleich liegt ja auch dadrin, dass das Semester 2 Wochen weniger hat, das sind immerhin 1/7 weniger Stoff.


Wenn man mit einem Termin im August rechnet, dieser dann aber um einen Monat vorgezogen wird, hat man nicht so viel Zeit zum lernen.. Vor allem weil wir gerade mal 3 Wochen vorher die Informationen bekommen haben und die Klausur auch noch in der Vorlesungszeit ist. Zudem schreiben wir alle anderen Klausuren auch noch in den folgenden Wochen. Man kann sich jetzt nicht so gut auf die Klausur vorbereiten, wie man es sonst gemacht hätte.

Aufgabe 20.18[Bearbeiten]

Gibt diese Aufgabe keine Punkte?

Doch, Danke.

Kleines Problem mit alternierenden Wegen bzw. dem Satz von Berge[Bearbeiten]

Ich bin gerade dabei Vorlesung 21 zu schauen und habe ein Problem bei alternierenden Wegen bzw. dem Satz von Berge festgestellt.

Ein Weg ist eine Knotenfolge, bei der zwischen allen aufeinanderfolgenden Knotenpaaren eine Kante dazwischen besteht. Hier wird nicht ausgeschlossen, dass der Anfangs- und Endknoten der gleiche Knoten ist. Ein alternierender Weg ist nun ein Weg, bei dem die Kanten abwechselnd aus einer Paarung und nicht aus einer Paarung stammen müssen. Soweit so gut. Beim Satz von Berge heißt es nun, eine Paarung wäre genau dann optimal, wenn es keinen alternierenden Weg im Graphen gibt, bei dem beide Endpunkte nicht abgedeckt sind (+ eine Konstruktionsanweisung um die Paarung hinsichtlich der Kantenanzahl zu verbessern).

Meiner Meinung nach muss zusätzlich gelten, dass Anfangs- und Endknoten des alternierenden Wegs verschiedene Knoten sind (entweder bei der Definition von alternierenden Wegen oder beim Satz von Berge). Ansonsten könnte man einen Kreis mit drei Kanten nehmen, eine Paarung bestehend aus einer dieser Kanten. Dann würde ein Weg von dem unabgedeckten Knoten über eine der Nicht-Paarungskanten über die Kante der Paarung und entlang der letzten Kante bestehen. Der Weg ist alternierend, allerdings ist die Paarung schon optimal und ein vertauschen der Kanten würde auch nicht zu einer Paarung führen.

sehr aufmerksam, ist geändert,+2.

Beweis zum Satz 20.18[Bearbeiten]

Mir ist die Fallunterscheidung innerhalb des Beweises nicht ganz klar. Es wird gesagt, dass einmal nur echte Teilmengen betrachtet werden sollen. Aber meiner Meinung nach wird im Skript in beiden Fällen die leere Menge und die gesamte Menge I ausgeschlossen.

echt ist in dieser Situation als nicht leer und nicht als ganz zu verstehen, was ja auch dasteht.

Ja genau, aber diese beiden Fälle doch werden in beiden Teilen der Fallunterscheidung nicht berücksichtigt.

meinen Sie mit diese beiden Fälle hier die Extremfälle leer oder ganz? Das muss auch nicht berücksichtigt werden durch die genaue Formulierung der Fallunterscheidung.

Beispiel 21.9[Bearbeiten]

Müsste hier nicht die Knotenüberdeckungszahl \lfloor n/2 \rfloor sein? Nach der im Beispiel angegebenen Formel folgt beispielsweise für n=3 eine Knotenüberdeckungszahl von 2, obwohl es doch ausreichen müsste, nur den mittleren Knoten auszuwählen.

Danke, da hab ich wohl die Kanten gezählt.

Aufgabe 12.3)[Bearbeiten]

In Aufgabe 12.3 soll gezeigt werden, dass es sich bei der Exponentialfunktion auf dem gegebenen Körper K, um einen Gruppenhomomorphismus handelt. Zur Veranschaulichung sei f(x) = b^x.

Man muss zeigen, dass f(x * x') = f(x) * f(x') Für alle x, x' aus den ganzen Zahlen. Beim Einsetzen erhält man: b^(x * x') = b^x * b^x' Mithilfe der Potenzgesetze erhält man: b^(x * x') = b^(x + x') Widerspruch.

Wo liegt mein Fehler?

es geht um die Abbildung von Z nach K ohne 0, links haben wir eine additiv geschriebene Gruppe, rechts eine multiplikativ geschriebene Gruppe, Homomorphismus bezieht sich auf die jeweiligen Verknüpfung. Es geht also in der Tat um eine Interpetation der Potenzgesetze, wobei aber die Exponenten auch negativ sein können.

Skript Vorlesung 22[Bearbeiten]

Das PDF-Dokument der Vorlesung 22 ist leider das der Vorlesung 21, sodass es die Vorlesung 22 aktuell nicht als PDF gibt.

das wird repariert.

Blätter 22, 23[Bearbeiten]

Sollen wir beide Arbeitsblätter 22, 23 bearbeiten oder wird es ein gemeinsames Blatt geben?

beide, sind ja beide kurz, also 21-23.

Sie haben eigentlich gesagt, dass diese Woche die letzte Abgabe sei. Dürfen wird trotzdem 21/22/23 abgeben und würden wir die Bewertung bekommen?

es soll noch korrigiert werden, haben Sie die 100 Punkte noch nicht zusammen?

100 Punkte haben wir (glaube ich), um Punkte geht es mir nicht, sonder um Klausurvorbereitung

wie gesagt, das wird noch korrigiert.

Aufgabe 23.6[Bearbeiten]

Zählt andere Richtung als anderer Kantenzug?

ja.

Also ist a-b-c-a der selbe Kantenzug als a-c-b-a?

Skript Def 21.6 und 21.7[Bearbeiten]

wo genau liegt der Unterschied zwischen den beiden Definitionen ? Bei beiden hat man die geringste Anzahl an Knoten für eine Knotenüberdeckung.

nein! siehe die Beispiele 21.9 und 10. Der Unterschied ist wie bei maximaler Paarung und optimaler Paarung.

Frage zu 22.3 Satz von Ore[Bearbeiten]

Die Bedingung in dem Satz bezieht sich ja auf je zwei nicht adjazente Knoten. In dem Beweis wird zunächst aber von einem vollständigen Graphen ausgegangen, bei dem es doch gar keine nicht adjazenten Knoten gibt. Wieso darf im ersten Schritt gesagt werden, dass die Aussage des Satzes von Ore dann für diesen Fall richtig ist? Eigentlich wäre der Satz für einen vollständigen Graphen doch gar nicht anwendbar?

Die Voraussetzung im Satz ist eine numerische Bedingung an nichtadjazente Punktepaare. Wenn es solche Paare aber gar nicht gibt, so ist die Voraussetzung des Satzes erfüllt (Allaussage über leere Menge). Der vollständige Graph erfüllt also die Voraussetzung des Satzes, aber eben auch die Folgerung, da es dort Hamiltonkreise gibt, wie man sich direkt klarmacht.

Bspklausur 2 , Nr.8[Bearbeiten]

Könntet ihr vielleicht eine mögliche Lösung beschreiben? Unsere Lösung würde für alle Operationen (Addition, Subtraktion etc) gleich aussehen..

das ist bei der Addition eine schräge Ebene, bei der Multiplikation eine Sattelfläche.

Zu Beispiel 15.11[Bearbeiten]

Hallo, was bedeutet die Schreibweise (+-,...,+-) für den Wüfelgraphen?

alle Kombinationen aus diesen zwei Möglichkeiten, man könnte auch schreiben, dann ist klar, wie der Würfel im liegt.

Könnten Sie mal beispielsweise diese Schreibweise für den Würfelgraphen im N² oder N³ angeben?

Das wäre dann einfach als abkürzende Schreibweise für die vier Punkte .

Danke!

Beispielklausur 1 - Aufgabe 7.3[Bearbeiten]

Vielleicht habe ich einen Denkfehler, aber wenn ich Stein, Brunnen und Papier habe (wie in der Lösung), wie kann das transitiv sein?

Stein schlägt Papier --> Papier schlägt Brunnen daraus würde bei Transitivität resultieren:

Stein schlägt Brunnen

Das stimmt jedoch nicht

Papier schlägt doch Stein (wickelt ein)!

Ups, da hatte ich einen Dreher. Danke

Beispielklausur 7 Aufgabe 10[Bearbeiten]

Zur Lösung von 4) Ist das nächste Paar nach (n,1) nicht (n-1,1) und somit die Abbruchbedinung dann (1,1)?

richtig, Danke.

(Nur theoretisch wäre nach (1,1) -> (1-1,1) also (0,1) -> (0, 1-0) also wieder (0,1).Dann würde der Algorithmus ja nie enden.) Oder habe ich den Algorithmus falsch verstanden?

Zu Lemma 13.9, 14.11 und 14.12[Bearbeiten]

Einerseits gilt Sur(n+1,k) = k*Sur(n,k) + k*Sur(n,k-1) = k!*k*S(n,k) + k!*k*S(n,k-1) nach Anwendung von 13.9 und dann 14.11.

hier muss rechts (k-1)! statt k! stehen.

Andererseits gilt auch Sur(n+1,k) = k!*S(n+1,k) = k!*(k*S(n,k) + S(n,k-1)) = k!*k*S(n,k)+ k!*S(n,k-1) nach Lemma 14.11 und dann 14.12. Daraus würde sich ein Widerspruch ergeben. Oder habe ich etwas übersehen?

Bspklausur 2, Aufgabe 16, Teil 2[Bearbeiten]

Wieso ist der in der Lösung beschriebene Weg ein Kreis, wenn es laut der Definition eines Kreises keine Wiederholungen geben darf ? Wenn man das mittlere Feld als A und die anderen vier Felder als B sieht und somit ein bipartiter Graph gebildet wird  ?

Meinen Sie Klausur 3? Der Zug nach links unten ist direkt. Der Läufer kann ja beliebig weit diagonal ziehen.

Beispielklausur 1 Aufgabe 13[Bearbeiten]

Bei Aufgabe 13 der ersten Beispielklausur wird die Automorphismengruppe in der Lösung allgemein angegeben. Wäre es hier in Ordnung die Permutationen innerhalb der Gruppe explizit aufzuzählen, oder würde das zu Punktabzug führen?

es muss schon begründet werden, warum gewisse Permutationen kein Graphautomorphismus sind. Die erlaubten Permutationen können dann aufgelistet werden, man muss nicht den Isomorphietyp der Gruppe angeben.

Beispielklausur 1 Aufgabe 16.4[Bearbeiten]

Wäre es in der Klausur erlaubt die Knotenüberdeckungszahl für den Graphen direkt anzugeben, oder ist hier die Formel gefordert, welche in der Lösung zu der Aufgabe angegeben wird?

direkt ist schwierig, es hängt ja von den ab.

Fehler im Beweis von Lemma 9.11[Bearbeiten]

In dem Beweis steht:

ist x >= x Dach y und ebenso y >= x Dach y, es ist also

x Dach y >= x, y

Bei dem unteren Teil müsste es aber dann ja umgedreht werden.

richtig, ist korrigiert.

Beispielklausur 2 - Aufgabe 7[Bearbeiten]

Die Aufgabe ist zwar mit einem * versehen, leider ist aber keine Lösung gegeben. Könnte ein Lösung eingefügt werden oder hat jemand eine Lösung dieser Aufgabe?

ist jetzt drin.

Beispielklausur 7, Aufgabe 17[Bearbeiten]

bitte Änderung in Lösung beachten.

Satz 26.1[Bearbeiten]

Ich glaube im Beweis von Satz 26.1 müsste stehen, dass es nach Induktionsvoraussetzung eine zulässige Färbung mit sechs Farben und nicht mit fünf Farben gibt.

richtig, geändert, Danke.

Frage zu Lemma 9.16 (i)[Bearbeiten]

Hallo, ich wollte einmal fragen ob das auch ein valider Beweis für 9.16 (i) wäre: Seien y,z Komplemente von x (ich schreibe inf (Infimum) und sup (Supremum) statt den Zeichen, da ich nicht weiß wie man diese hier eintippt), dann ist y = sup(y,0) =


sup(y,inf(x,z)) = inf(sup(y,x),z)


dieser Schritt stimmt nicht, eine solche Regel gibt es nicht (mengentheoretisch wäre das . )


= inf(1,z) = z oder darf man irgendeinen von diesen Schritten nicht anwenden? MfG

Lemma 24.12[Bearbeiten]

Beim Beweis von Lemma 24.12 wird ja der surjektive schwache Graphhomomorphismus phi: G -> G/e definiert und um aus einer Färbung von G/e eine Färbung auf G zu erhalten bei der der Wert von u und v übereinstimmt. Müsste hier der schwache Graphhomomorphismus nicht von G\{e} nach G/e gehen um eine Färbung auf G\{e} zu erhalten?

ist etwas umformuliert. In der Tat können sie direkt mit dem (echten!) Graphhomomorphismus von G\{e} nach G/e arbeiten.

Automorphismengruppe von Graphen (Klausur 1 Aufgabe 13)[Bearbeiten]

Ich bin mir bei der Notation der Automorphismengruppe nicht ganz sicher. Muss das \mathbb{Z} /(2) X \mathbb{Z} /(2) in der Antwort auftauchen? Oder genügt der vorangehende Teil der Antwort zur vollen Punktzahl?

da wir Gruppen nur kurz angerissen haben, würde wohl das davor genügen. Allerdings würde so was wie es gibt vier Automorphismen nicht die volle Punktezahl geben, es muss schon die Struktur der Gruppe deutlich werden.

Frage zu den ersten Aufgaben in Klausuren[Bearbeiten]

Hallo, muss für die Aufgabe 1 in Ihren Klausuren alles "runterdefiniert" werden, oder nicht? Muss z.B. für die Definition eines Waldes gesagt werden "Ein Wald ist ein Graph ohne Kreis" oder muss dann hier auch noch gesagt werden, was ein Kreis ist?

nur die eigentliche Definition, nicht weiter aufdröseln.

Untergraph ist injektiver Graphhomomorphismus?[Bearbeiten]

Sie haben in VL 16 gesagt dass ein Untergraph H=(W,F) eines Graphen G=(V,E) immer auch ein injektiver Graphhomomorphismus von G nach H ist. Jetzt meine Frage: auf welche Punkte werden diejenigen Punkte aus V abgebildet die nicht in W vorkommen? Ich bin gerade etwas verwirrt und würde mich über eine Antwort freuen, danke schonmal im Vorraus.

nein, es ist einer von H nach G.

Beispielklausur 9 Aufgabe 9[Bearbeiten]

Hallo,

ich habe zwei Fragen zur Aufgabe https://de.wikiversity.org/wiki/Nat%C3%BCrliche_Zahlen/Primfaktoren/%C3%84quivalenzrelation/Aufgabe bzw. zur Lösung: 1. Müsste nicht auch 50 ~ 10 etc. sein?

richtig 500 ist zu 10,100,1000 äquivalent.

2. Ich verstehe nicht, warum die Abbildung nicht surjektiv ist. Ich zu einer beliebigen Mengen <math>{p_1,...,p_k} \in P(\P) <\math> ist doch <math> p_1 * ... * p_n <\math> im Urbild der Menge.

Es werden zwar alle endlichen Teilmengen erreicht, aber nicht die unendlichen Teilmengen! Es gibt keine Zahl, in deren Primfaktorzerlegung alle Primzahlen vorkommen. In der Potenzmengen geht es aber um alle Teilmengen.


Vielen Dank.

0^0[Bearbeiten]

Weshalb kann man zur Potenz 0^0 keine eindeutige Lösung festlegen?

das kann man schon, das Problem ist, dass es schwer ist, sich zu einigen. Insgesamt ist aber besser (als ). Beispiel:wie viele Abbildungen gibt es von der leeren Menge in die leere Menge?

Klausurergebnisse[Bearbeiten]

Gibt es eine Tendenz, wann wir ungefähr Ergebnisse erwarten können? Und werden sie veröffentlicht bevor wir sie im Opium sehen können oder wie ist das vorgesehen?

über Opium, heute oder morgen.

Klausureinsicht[Bearbeiten]

Wird es noch eine Möglichkeit der Klausureinsicht geben?

das ist ziemlich schwierig. Für die Bestimmungen siehe die Prüfungsordnung. Um diesem formal-bürokratischen Aufwand zu entgehen wird im Fachbereich in normalen Zeiten eine direkte Einsicht angeboten. Die Zeiten sind aber nicht normal, einen Präsenztermin wird es erst mal nicht geben, erst wieder, wenn man dafür keinen Antrag mehr einreichen muss. Ich kann eine 'Einsicht' über BigBlueButton anbieten, dabei denke ich aber hauptsächlich an Leute, die bspw. unmittelbar vor einem Abschluss stehen oder die Uni wechslen wollen oder dergleichen (die andern kriegen ihre Einsicht später). In solchen Fällen begründete Anfrage an mich. Eine weitere Bemerkung: bei den Leuten, die punktemäßig zwischen 10 und 16 waren, wird geguckt, ob man irgendwo noch was machen kann (und konnte man auch in einigen Fällen). Von daher ist es äußerst unwahrscheinlich, dass jemand, der durchgefallen ist, durch eine Einsicht bestehen könnte.

Meine Intention zur Einsicht wäre eine andere, ich möchte meine Fehler wissen. Die APO erlaubt ja eine Fotokopie, wäre es möglich auf Wunsch einfach eine Fotokopie / einen Scan der korrigierten Klausur zu bekommen? Ich weiß, das ist aufwendig. Aber ein offizieller Termin zur Einsicht wäre noch deutlich aufwendiger und ist wahrscheinlich in absehbarer Zeit nicht zu bekommen, oder?

bei den üblichen Einsichtsterminen erlaube ich grundsätzlich keine Kopien. Die Prüfungsordnung ermöglicht dies, aber nur im Rahmen eines über den Prüfungsausschuss laufenden Einzelantrags zur Einsicht. Bei einem offiziell beantragten Einsichtstermin können Sie auch einen Rechtsbeistand mitbringen, das würde ich bei einem sonst üblichen Termin aber auch nicht erlauben. Solche Sachen heben m.E. den Prozess auf eine juristisch-dokumentarische Ebene, die ich in der normalen didaktischen Kommunikation nicht haben möchte. Deshalb werde ich keine Scans ausgeben. Wenn Sie die Lösungen studiert haben, sollten Sie eigentlich Ihre Fehler abschätzen können. Grundsätzlich gibt es auch die Sprechstunde (über Bluebutton).

Lemma 5.4[Bearbeiten]

Im Beweis zu Lemma 5.4 muss es in der ersten Zeile "Verknüpfung" statt "Multiplikation" heißen.

beim Symbol spricht man oft abstrakt von Multiplikation, das hab ich jetzt in Vorlesung 4 erwähnt, Danke.

Lemma 9.11[Bearbeiten]

Im Beweis zu Lemma 9.11 müsste es in der vorletzten Zeile statt "x \sqcup (x \sqcup y)" "x \sqcap (x \sqcup y)" heißen.

Danke, ist geändert.

Bemerkung 11.14[Bearbeiten]

Es müsste hier doch eigentlich (wenn man die Bezeichnungen aus dem vorstehenden Lemma 11.13 übernimmt) statt "f = ψ &circ p" "f = ψ &circ q" heißen.

stimmt, q passt besser.

Lemma 13.2[Bearbeiten]

Im Beweis zu diesem Lemma müsste es bei den letzten beiden Brüchen statt r_1! jeweils r_k! heißen.

sehr richtig, Danke.

Satz 14.13[Bearbeiten]

Im Beweis zu Teil 3 dieses Satzes steht in der letzten Zeile "... für t zwischen ausschließlich ...", es sollte aber wahrscheinlich eher "... für t =1,...,n-k ..." heißen, oder vertue ich mich da?

das stimmt so. Jedes t liegt liegt zwischen einer der angegebenen Summen.

Lemma 19.6[Bearbeiten]

Im Beweis müsste es unter dem letzten Summenzeichen "w \in V" statt "x \in W" heißen.

stimmt, Danke

Satz 3.1[Bearbeiten]

Im Beweis ist nach dem fünften Gleichheitszeichen im Index der ersten Summe ein kleiner Tippfehler. "{1,...,n,n+1,n+1 \notin J}" statt "{1,...,n,n+1}, n+1 \notin J"

Stimmt, Danke.

Erste Klausur[Bearbeiten]

Wäre es möglich die erste Klausur bzw. die Aufgaben der ersten Klausur noch einmal einzusehen?

das war die Klausur 13.

Fünf-Farben-Satz[Bearbeiten]

Es mag vielleicht etwas zu kleinlich sein, aber müsste es im Beweis nicht eher "Wenn die Nachbarn von u nur höchstens vier Farben verwenden, was insbesondere dann der Fall ist, wenn u nur höchstens vier Nachbarn besitzt,..." heißen?

ist geändert, wir sind kleinlich.

Beispielklausur 5 Aufgabe 12[Bearbeiten]

Hier steht in der Lösung, dass die Automorphismengruppe (bzw. der Typ der Automorphismengruppe) Z/(2)xZ/(2) ist. Müsste diese aber nicht eigentlich nur Z/(2) sein, da die Vertauschung der oberen beiden Knoten nicht unabhängig von der Vertauschung der beiden Knoten darunter ist?

Sie haben recht, die Lösung war auch nicht von mir.

Satz 13.7[Bearbeiten]

Es müsste hier eigentlich noch angemerkt werden, dass wir oBdA B = {1,...,k} annehmen, oder?

Stimmt.

Beispielklausur 4 Aufgabe 7[Bearbeiten]

In der sechsten Zeile der Lösung müsste es ((n(n-1)*...*(n-k+1))/k!)*n^(n-k) heißen.

stimmt, Danke.