[LÖSUNG] - 506, 512, 513, 533, 540 [Archive]

fortySix&2

03-06-2005, 13:34

hey,

ich wollte nur anmerken, dass deine lösung bei 513 nicht ganz korrekt ist: die von dir aufgezählten teilgraphen haben die gleiche struktur wie G2, wenn man die bedingung für einen aufgespannten teilgraphen weglässt, d.h. nach der definition eines aufgespannten teilgraphen (baron-buch band 3 s. 151 ganz unten) - G=(V, E), G'=(V', E') Teilgraph von G - müssen ALLE kanten, die in G zwischen den Knoten aus V' existieren auch in E' aufgenommen werden, damit G' ein aufgespannter teilgraph ist.

also bei diesem bsp wären das dann: (5, 1, 7, 2) und (5, 1, 2, 7), die anderen graphen wären zwar richtige teilgraphen, jedoch keine aufgespannten teilgraphen, d.h. durch die bedingen, dass alle kanten die auch in G zwischen den knoten aus V' in E' aufgenommen werden müssen, haben sie dann nicht mehr die gleiche struktur wie G2

feli

04-06-2005, 12:34

@ Paulchen:
Frage, hast du bei der Vereinigung von E(G1) und E(G2) bei Bsp. 512 nicht die Kanten <2,6> und <2,8> vergessen, weil in meiner Kantenmenge E(G2) stehen die schon drin (hab mich aber vielleicht auch irgendwo geirrt)

Ach ja, und bei 533 hast du dich glaube ich geirrt im Graphen, es sind die Zyklen im Graph G5 gefragt, ich glaube aber das du G3 betrachtet hast

johnny the boy

04-06-2005, 16:10

also bei diesem bsp wären das dann: (5, 1, 7, 2) und (5, 1, 2, 7), die anderen graphen wären zwar richtige teilgraphen, jedoch keine aufgespannten teilgraphen, d.h. durch die bedingen, dass alle kanten die auch in G zwischen den knoten aus V' in E' aufgenommen werden müssen, haben sie dann nicht mehr die gleiche struktur wie G2

sind nicht <4, 1, 7, 2> bzw. <3, 4, 1, 2> auch korrekte Teilgraphen?

Paulchen

04-06-2005, 16:20

@ Paulchen:
Frage, hast du bei der Vereinigung von E(G1) und E(G2) bei Bsp. 512 nicht die Kanten <2,6> und <2,8> vergessenstimmt, hab ich vergessen
Ach ja, und bei 533 hast du dich glaube ich geirrt im Graphen, es sind die Zyklen im Graph G5 gefragt, ich glaube aber das du G3 betrachtet hastverdammt noch mal (vielleicht sollt ich die angaben doch in einer höheren auflösung ausdrucken... :distur: )
ich wollte nur anmerken, dass deine lösung bei 513 nicht ganz korrekt iststimmt natürlich auch; hab alles jetzt ausgebessert.
sind nicht <4, 1, 7, 2> bzw. <3, 4, 1, 2> auch korrekte Teilgraphen?<4,1,7,2> ist wegen der kante <4,2> keine zulässige lösung, und <3,4,1,2> nicht wegen der kanten <3,2> und <2,1> und weil die kante <4,2> in die falsche richtung zeigt

klausi

05-06-2005, 15:19

könnte vielleicht bei 512 bei der Vereinigung der Kantenmenge nicht auch z.B. <6,8> dabeisein?
weil 6<8<6+2=10; ich weiß 10 ist nicht Element der Knotenmenge, aber es steht ja auch nich da, dass x+2 Element der Knotenmenge sein muss (hingegen x und y allein schon, damit die Kante überhaupt existieren kann).

EDIT: ok, denkirrtum, wir dürfen ja keine neuen Kanten erfinden, sondern nur die existenten von G1 und G2 hernehmen. dann müssen wir allerdings die definition der vereinigungsmenge der kanten ändern.
(x teilt y, x<y) oder (x<y<=x+2|y<=7)

mfg klausi

hm?

05-06-2005, 18:48

supersonnig

05-06-2005, 19:42

Frage zu 506)

mach grad 505) und mir ist aufgefallen, dass du, paulchen,
die beziehung zw. 3 und 5 nicht in deinem graphen eingezeichnet hast.
und dann wollt ich noch fragen, warum du bei jedem knoten eine kante, die auf ihn selbst verweist, gezeichnet hast. Denn bei 506) steht nicht, so wie bei 505) in der Angabe m=n.

die ist auch nicht wegen m=n da, sonder weil

2n mit n € natürl. Zahlen

immer gerade ist, also jede zahl zu sich selber addiert gerade ist.
deshalb ist jeder Knoten mit sich selbst in beziehung.

Paulchen

05-06-2005, 20:53

(x teilt y, x<y) oder (x<y<=x+2|y<=7)drum schreib ich ja (gut, vielleicht nicht allzugut lesbar :shinner: ): (x teilt y, x<y) oder (x<y<=x+2<=7).Frage zu 506)

mach grad 505) und mir ist aufgefallen, dass du, paulchen,
die beziehung zw. 3 und 5 nicht in deinem graphen eingezeichnet hast.hm, die hab ich in dem wirrwarr doch glatt vergessen...
und dann wollt ich noch fragen, warum du bei jedem knoten eine kante, die auf ihn selbst verweist, gezeichnet hast. Denn bei 506) steht nicht, so wie bei 505) in der Angabe m=n.die relation mRn <=> m+n gerade ist reflexiv, also f.a. m aus der gegebenen menge gilt: mRm, da m+m=2m gerade ist. daher die kanten von jedem knoten zu sich selbst.

(hat supersonnig eh schon beantwortet)

Noir

05-06-2005, 21:00

@Paulchen:
zu 506: bei dir sind die Knoten 11 und 4 verbunden, aber die Summe ist ungerade.

@540: Angabe: "Man untersuche G8...." wo ist auf dem Zettel G8? Auf Seite 31 ist der nicht zu finden (oder ich bin blind).

Paulchen

05-06-2005, 21:09

@Paulchen:
zu 506: bei dir sind die Knoten 11 und 4 verbunden, aber die Summe ist ungerade.verdammt, dieses gewirr an kanten is so unüberschaubar *grummel*
@540: Angabe: "Man untersuche G8...." wo ist auf dem Zettel G8? Auf Seite 31 ist der nicht zu finden (oder ich bin blind).nimm einfach H1. wenn wer keppelt? da hat niemand zu keppeln... :D

klausi

06-06-2005, 00:20

zu 512) ok mein fehler, hab dein gekrakel überlesen ;).

zu 540):

beim ersten mal bei punkt 2)b) markierst du nur Knoten 5. Warum?
Wir haben doch in der vo aufgeschreiben: "markiere alle Knoten, von denen Kanten zu bereits markierten Knoten existieren."
Das heißt in unserem fall: Knoten die einen Pfeil zu 1 haben. und das sind 2, 4 und 5.
Oder hab ich da was falsch verstanden oder aufgeschreiben?
Jedenfalls kommt im Endeffekt das selbe raus, G8 (bzw. H1) ist azyklisch (was augenscheinlich auch stimmt).

mfg klausi

Stephe

06-06-2005, 11:59

@ klausi:
ausserdem is 6+2=8, und nicht 10 ;):D

im algorithmus heissts (glaub ich zumindest): "markiere alle Knoten, von denen NUR Kanten zu bereits markierten Knoten existieren." Dh. hat ein Knoten auch Kanten zu nicht markierten Knoten, darf man den vorerst NICHT markieren, deswegen anfangs nur der Knoten 5.

klausi

06-06-2005, 12:49

jaja, das ist einer der gründe warum ich mathe 1 immer noch nicht geschafft habe.:(
aber danke, meine überlegungen waren eh nicht relevant.

mfg klausi

Noir

06-06-2005, 13:21

zu 540):

beim ersten mal bei punkt 2)b) markierst du nur Knoten 5. Warum?
Wir haben doch in der vo aufgeschreiben: "markiere alle Knoten, von denen Kanten zu bereits markierten Knoten existieren."
Das heißt in unserem fall: Knoten die einen Pfeil zu 1 haben. und das sind 2, 4 und 5.
Oder hab ich da was falsch verstanden oder aufgeschreiben?
Jedenfalls kommt im Endeffekt das selbe raus, G8 (bzw. H1) ist azyklisch (was augenscheinlich auch stimmt).

mfg klausi

so hab ichs auch verstanden.

maxi

06-06-2005, 23:47

frage zu 512)
woher stammt bei der Vereinigung <6,7> ?
das ist weder x<y<=x+2
noch x teilt y, x<y

?? oder habe ich da einen denkfehler?

Paulchen

07-06-2005, 01:13

frage zu 512)
woher stammt bei der Vereinigung <6,7> ?
das ist weder x<y<=x+2
noch x teilt y, x<y

?? oder habe ich da einen denkfehler?
ist x=6 und ist y=7, dann gilt doch:

x=6 < y=7 < x+2=8

oder?

maxi

07-06-2005, 09:54

@paulchen
stimmt, hab ich glatt übersehen *g*
thx

maxi

07-06-2005, 11:32

@540 - markierungsalgorithmus
ich habe eine etwas andere reihenfolge als paulchen:
1. runde: 1
2. runde: 5
3. runde: 2,4
4. runde: 3,7
5. runde: 6

also 6 erst eine runde danach, weil von 6 kanten zu 3,7 führen, die ja bei runde 4 noch nicht markiert sind

Paulchen

07-06-2005, 19:19

@540 - markierungsalgorithmus
ich habe eine etwas andere reihenfolge als paulchen:
[...]
6 erst eine runde danach, weil von 6 kanten zu 3,7 führen, die ja bei runde 4 noch nicht markiert sind
stimmt natürlich

Quimby

07-06-2005, 21:45

--------------------------edited

maxi

08-06-2005, 10:53

bsp 533)
ist hier die adjazenzmatrix gefragt ??? ich fürchte ja, denn ansonsten ist die lösung wohl zu banal ...

glubschi

08-06-2005, 14:03

wenn ich die adjazenzmatrix aufzeichne, is das wohl auch banal.. oder nicht?? eine 8x8 matrix wo einfachn 1er ist, wenns eine verbindung gibt und 0 wenn nicht.
gibts ein verfahren, mit dem ich aus der adjazenzmatrix die zyklen der länge drei auf denen 4 liegt, rauslesen kann oder muss i das auch durc h schauen bzw. probieren machne?!

RubyX

08-06-2005, 14:27

gibts ein verfahren, mit dem ich aus der adjazenzmatrix die zyklen der länge drei auf denen 4 liegt, rauslesen kann oder muss i das auch durc h schauen bzw. probieren machne?!

Ja, gibt es. Schau dir Bsp 531 aus dem Montagsforum an. Gleiche Aufgabe, nur statt Wegen von 4 bis 6 mit Länge 3 suchen wir Wege von 4 bis 4 mit Länge 3. Also statt 6 einfach 4 einsetzen, der Rest ist identisch. Und das Ergebnis lautet 2.