View Full Version : [LÖSUNG] - 518, 523, 544, 548, 557
Paulchen
07-06-2005, 10:54
hm, vielleicht ist mir ja wirklich ein wenig fad... :devil:
518:
K1 besteht aus den knoten 2,3,4 und den dazugehörigen kanten
K2 besteht aus den knoten 1,6,7 und den dazugehörigen kanten
K3 besteht aus knoten 5
G3R=({K1, K2, K3}, {<K1, K2>,<K2, K3>}
523: Menge der Knotenbasen von G3: {{2}, {3}, {4}}
544: linke Komponente hat 8 gerüste, rechte komponente hat 3 gerüste, macht insgesamt 24 gerüste.
548: wie schon in algodat:
es gilt in einem ungerichteten schlichten graphen: die summe über die grade aller knoten eines graphen ist gleich der doppelten kantenanzahl in dem graphen.
da die doppelte kantenanzahl gerade ist, muss die summe über die grade aller knoten auch gerade sein. in der summe darf ich beliebig klammern setzen, also auch einmal um alle geraden summanden (diese summe ist auf jeden fall gerade), und dann einmal um alle ungeraden summanden; damit die zweite summe gerade ist, muss die anzahl deren summanden gerade sein. nun ist aber jeder summand grad eines knotens; diese knoten haben alle ungeraden grad; d.h. die anzahl der knoten mit ungeradem grad ist gerade.
557: zur zeit noch keine ahnung...
wenn eine matrix dreiecksgestalt hat was heißt das jetzt genau?
dass zb oberhalb der diagonale lauter 0 stehen?
Eine quadratische (n,n)-Matrix heißt obere (bzw. untere) Dreiecksmatrix, wenn alle Elemente unterhalb (bzw. oberhalb) der Hauptdiagonalen Null sind, d.h. aij = 0 falls i > j (bzw. aij = 0, falls i<j)wir sollen azyklische, gerichtete graphen betrachten, da gibt es keine schlingen, also besteht hauptdiagonale aus 0-en
bzgl. umindizierung gibt es einen math. weg (http://www.emath.de/Mathe-Board/messages/8/15301.html?1113663066) bzw. einen anschaulichen algorithmus (http://www.computerbase.de/lexikon/Topologisches_Sortieren#Algorithmus)
einen graphen zum testen gibt es hier (http://wwwai.wu-wien.ac.at/inf_wirt/gif/21adjaz.gif)
wie ich das jetzt mathematisch allgemein/korrekt formuliere/beweise - da bitte ich einen mathe-profi um einen tipp (paulchen *g*??)
Paulchen
10-06-2005, 14:17
wie ich das jetzt mathematisch allgemein/korrekt formuliere/beweise - da bitte ich einen mathe-profi um einen tipp (paulchen *g*??)ich? mathe profi? ich hab ja selber keine ahnung... :shinner:
Paulchen
11-06-2005, 20:08
hab mir da mal ein paar gedanken gemacht...
wenn G ein azyklischer graph ist, dann kann ich darauf den markierungsalgorithmus zur bestimmung der azyklität anwenden, und dieser markiert alle knoten des graphen. ich nummeriere nun die knoten in jener reihenfolge, in der sie von dem algorithmus markiert werden. werden dabei in einem schritt des algorithmus mehrere knoten markiert, so ist die nummerierung der betroffenen knoten beliebig wählbar.
im entstehenden graphen G' hat jeder knoten vi in V(G') nur kanten zu Knoten vj aus V(G') mit j<i. das liegt daran, dass ein knoten v aus V(G) nur kanten zu bereits markierten knoten vj haben darf, um vom markierungsalgorithmus markiert zu werden; die bereits markierten knoten vj haben natürlich niedrigere nummern zugewiesen bekommen als ein neu markierter knoten bekommen würde. d. h. in G' können vom knoten vi nur kanten zu knoten vj gehen.
für die adjazenzmatrix A'=(aij') des graphen G' bedeutet das nun, dass aij' nur dann 1 sein kann, wenn j<i ist. D. h. alle aij mit j>=i müssen 0 sein, d.s. die Diagonale sowie alle Elemente oberhalb der diagonale. die matrix erfüllt also die gewünschte eigenschaft.
analog funktioniert das, wenn man genau die umgekehrte markierung wählt; dann hat jeder knoten vi aus V(G'') nur kanten zu knoten vj aus V(G'') mit j>i. D. h. aij'' der adjazenzmatrix kann nur für j>i 1 sein, alle aij'' mit j<=i müssen 0 sein, d.s. die diagonale sowie alle elemente oberhalb der diagonale. wieder erfüllt also die matrix die gewünschte eigenschaft.
Die Lösung für 557 klingt absolut logisch. Dass es um einen azyklischen Graphen geht, deutet ja schon darauf hin, dass er irgendwie auf den Markierungsalgorithmus hinauswollte.
Dürfte auf jeden Fall so stimmen!
Paulchen
13-06-2005, 14:45
mir ist da gerade aufgefallen, dass ja da nichts steht von einem ungerichteten graphen
ich hab allerdings nur den fall des ungerichteten graphen untersucht; was ist mit dem fall des gerichteten graphen
mein problem dabei allerdings: was ist der knotengrad im gerichteten graphen? wir haben den knotengrad nur für ungerichtete graphen definiert, im gerichteten fall gibt es nur hingrad und weggrad eines knotens.
*nixversteh*
oder muss man eh nur den ungerichteten graphen untersuchen?
glubschi
13-06-2005, 16:59
wie war das da nochmal mit den knotenbasen?! (bsp 523)? ist das nicht einfach so, dass ich aus jeder zusammenhansgkomponente einen knoten nehme (egal welchen):
somit hätte ich folgende basen:
ach ja.. passt schon.. da bleibt dann nur k1 übrig (da ja d^minus null sein muss --> der hingrad..) und dann hab i die drei einzelnen knoten als knotenbasis.
was sagt die knotenbasis jetzt aus??
@544: wie bilde ich nochmal die det(4x4Matrix)? sarrus darf ja hier laut buch nicht so angewendet werden...:confused:
Paulchen
13-06-2005, 18:55
wie war das da nochmal mit den knotenbasen?! (bsp 523)? ist das nicht einfach so, dass ich aus jeder zusammenhansgkomponente einen knoten nehme (egal welchen):
somit hätte ich folgende basen:
ach ja.. passt schon.. da bleibt dann nur k1 übrig (da ja d^minus null sein muss --> der hingrad..) und dann hab i die drei einzelnen knoten als knotenbasis.
was sagt die knotenbasis jetzt aus??frei formuliert (kA, wie der großmeister das ausdrückt): eine knotenbasis ist eine minimale menge von knoten, von denen ich jeden anderen knoten des graphen erreichen kann
@544: wie bilde ich nochmal die det(4x4Matrix)? sarrus darf ja hier laut buch nicht so angewendet werden...:confused:
zwei möglichkeiten:
gauss'sches eliminationsverfahren: matrix auf halbdiagonalform bringen, determinante ist produkt der elemente in der hauptdiagonale
entwicklung nach elementen einer zeile/spalte:
A=(aij); A aus Lm
entwicklung nach elementen der i-ten zeile:
det A = summe[1<=j<=m] (aij*(-1)i+j*Uij)
entwicklung nach elementen der j-ten spalte:
det A = summe[1<=i<=m] (aij*(-1)i+j*Uij)
wobei Uij die determinante jener untermatrix von A ist, der die i-te zeile und die j-te spalte fehlen
hoffe, das ist einigermaßen verständlich
mir ist da gerade aufgefallen, dass ja da nichts steht von einem ungerichteten graphen
ich hab allerdings nur den fall des ungerichteten graphen untersucht; was ist mit dem fall des gerichteten graphen
mein problem dabei allerdings: was ist der knotengrad im gerichteten graphen? wir haben den knotengrad nur für ungerichtete graphen definiert, im gerichteten fall gibt es nur hingrad und weggrad eines knotens.
*nixversteh*
oder muss man eh nur den ungerichteten graphen untersuchen?
Stimmt, in gerichteten Graphen ist der einfache "Knotengrad" nicht definiert. Folglich können wir annehmen, dass sich das Beispiel auf ungerichtete Graphen beziehen muss.
Und angenommen, es gäbe auch einen Knotengrad in gerichteten Graphen: Der wäre dann wohl definiert als Hingrad+Weggrad. Man sieht leicht, dass dann für jeden Knoten der gleiche Grad wie im ungerichteten Fall herauskommt. Folglich gilt der Beweis analog.
Ich hab das Beispiel Montags bereits Übungen gehabt, und will euch mitteilen, dass (zumindest bei unserem Übungsleiter) dass wir angenommen haben, dass ungerichtete Graphen gemeint sind, da, wie ihr bereits erwähnt habt, man bei gerichteten Graphen zwischen Hin- und Weggrad unterscheiden müsste. :D
TheWhiteRabbit
14-06-2005, 11:53
@ irgendwen
bei 518 steht blablö G3 was ist G3? war vorige woche ned da? wie wird das bsp genau gerechnet?
Paulchen
14-06-2005, 12:51
@ irgendwen
bei 518 steht blablö G3 was ist G3?
G3 ist auf seite 31 zu finden (ganz unten auf seite 28 steht sogar ein hinweis :distur: )
war vorige woche ned da?schlecht.
wie wird das bsp genau gerechnet?eine starke zusammenhangskomponente eines gerichteten graphen ist jener teilgraph der stark zusammenhängend ist. ein gerichteter graph G ist stark zusammenhängend, wenn für alle knoten u,v aus V(G) gilt: es existiert ein pfad von u nach v.
bei der bestimmung der reduktion wird jede zusammenhangskomponente kn des graphen G auf einen knoten Kn in der reduktion GR von G "reduziert"; zwei solche knoten Ki und Kj der reduktion GR sind dann durch eine kante miteinander verbunden (es existiert also eine kante <Ki, Kj> aus E(GR) ), wenn es einen knoten u aus V(ki) und einen knoten v aus V(kj) gibt, für die <u,v> aus E(G) gilt.
Die Antwort wird dir wohl nicht weiterhelfen, aber du dürftest dich verrechnet haben, ich hab die Determinanten, um Zeit zu sparen mit Derive ausgewertet, schau in den Threadhttp://www.informatik-forum.at/showthread.php?t=32182, da hab ich anhand einer Determinante, wie man die Determinante soweit vereinfacht, sodass ihr Wert sich leicht berechnen lässt. Hab jetzt leider keine Zeit es dir nach Spalten oder Zeilenentwicklung zu zeigen, sodass du deinen Fehler leichter finden kannst.
Paulchen
14-06-2005, 20:38
Die Antwort wird dir wohl nicht weiterhelfen, aber du dürftest dich verrechnet haben, ich hab die Determinanten, um Zeit zu sparen mit Derive ausgewertet, schau in den Threadhttp://www.informatik-forum.at/showthread.php?t=32182, da hab ich anhand einer Determinante, wie man die Determinante soweit vereinfacht, sodass ihr Wert sich leicht berechnen lässt. Hab jetzt leider keine Zeit es dir nach Spalten oder Zeilenentwicklung zu zeigen, sodass du deinen Fehler leichter finden kannst.aus deinem posting werd ich nicht schlau
mein Derive spuckt nach der eingabe
DET([3, -1, -1, 0; -1, 1, 0, 0; -1, 0, 3, -1; 0, 0, -1, 2])
das ergebnis "8" aus (d.i. die unterdeterminante M1,1, also jener matrix, der ich die erste zeile und die erste spalte "gestohlen" habe); also da siehts nicht so aus, als wäre da was falsch
die eingabe
DET([2, -1; -1, 2])
liefert "3", also da ist auch nichts falsch
aus der volksschule wissen wir: 3*8=24
und zu guter letzt: das steht auch in dem von dir erwähnten thread...
könntest du bitte etwas konkreter werden, wo ich mich angeblich verrechnet haben soll?
derive hin oder her - ich habe die determinanten 'zu fuss' gerechnet: 3*8=24
Ich hab das Beispiel Montags bereits Übungen gehabt, und will euch mitteilen, dass (zumindest bei unserem Übungsleiter) dass wir angenommen haben, dass ungerichtete Graphen gemeint sind, da, wie ihr bereits erwähnt habt, man bei gerichteten Graphen zwischen Hin- und Weggrad unterscheiden müsste. :D
Bei ungerichteten Graphen ist die Adjazenzmatrix immer symmetrisch, d.h. hier ist die Nullmatrix ist die einzige Matrix in Dreiecksform.
wie wurde das in deiner übung gelöst?
oooops, dachte er spricht von bsp 557
aus deinem posting werd ich nicht schlau
mein Derive spuckt nach der eingabe
DET([3, -1, -1, 0; -1, 1, 0, 0; -1, 0, 3, -1; 0, 0, -1, 2])
das ergebnis "8" aus (d.i. die unterdeterminante M1,1, also jener matrix, der ich die erste zeile und die erste spalte "gestohlen" habe); also da siehts nicht so aus, als wäre da was falsch
die eingabe
DET([2, -1; -1, 2])
liefert "3", also da ist auch nichts falsch
aus der volksschule wissen wir: 3*8=24
und zu guter letzt: das steht auch in dem von dir erwähnten thread...
könntest du bitte etwas konkreter werden, wo ich mich angeblich verrechnet haben soll?
Sorry, Paulchen, ich habe nicht dich gemeint, ich hab nämlich einer anderen Person im Forum geantwortet. Schlimmer noch: ich hab in den falschen Thread reingepostet :shinner: . Du wirst dich nun fragen, wie man "versehentlich" in den falschen Thread reinposten kann:
Um ein Posting zu schreiben, und gleichzeitig den Fragethread im Bild zu haben, öffne ich ein eigenes Fenster mit Frage, und ein anderes, um meinen Text zu editieren (wo zwar auch die anderen Postings zu finden sind, aber nicht so übersichtlich, wie ichs gern hätte). Dabei hab ich mich in einem der beiden Fenster in den falschen Thread geklickt ... weis nicht mehr genau wie das war, ist auch uninterressant. Ich hab euch halt auf diesen Fehler nicht aufmerksam gemacht, weil ich gehofft hab ihr seid mir nicht böse deswegen. So ein Fehler (so hoffe ich) ist mir sonst noch nie passiert. - PS: wie kann man eigene Postings wieder Löschen?(Ich meine vollkommen entfernen, und nicht nur editieren und dabei Text löschen)
Übrigens, was deine Mathematischen Kenntnisse anbelangt, Paulchen, hast du meinen
http://forum.riedls.net/images/smileys/respect.gif*Respekt*
Paulchen
15-06-2005, 17:50
PS: wie kann man eigene Postings wieder Löschen?(Ich meine vollkommen entfernen, und nicht nur editieren und dabei Text löschen)mail/pm an admin/moderator
vBulletin® v3.7.1, Copyright ©2000-2008, Jelsoft Enterprises Ltd.