Graphentheorie, Interpretationshilfe

[Marscel]

Ich steck fest und weiß nicht weiter, mit etwas Pech muss ich es erklären können bevor ichs beim Dozenten nochmal nachfragen kann.

Folgender Folienausschnitt:

http://666kb.com/i/c9qp0hiqyudxy6ceh.jpg

Was könnte die Abbildung phi_v sein: Was könnten D und D^gamma(v) sein?

Was ich weiß:

gamma(v) hab ich mir zum Glück notiert als Eingangsgrad von einem Knoten v
D ist nach Buchrecherche eines von: Di-Eder, Diagramm, gerichteter Graph, Distanzmatrix ... fehlt was?


Aber was bildet unter Berücksichtigung eines Eingangsknotengrades eines jeden Vertex auf einen verwandten Raum ab? Die ersten beiden Strukturen sollte irrelevant sein, der Graph ist schon als G beschrieben und Distanzmatrix macht mir keinen Sinn, weil es hier keine Kantengewichtungen gibt. Die Exponentenschreibweise kann ich nur Adjazenzmatrizen zuordnen, wo der Exponent die Anzahl der erlaubten Hops bedeutet. Aber mit dem Eingangsgrad? Ich komm nicht drauf ... habs über Kontextsuche und Symboltabellen probiert. In den Folien werden weder phi noch D jemals wieder verwendet, ich würds trotzdem gerne wissen.


Zweite Sache, wie muss ich das hier lesen?

http://666kb.com/i/c9qpdcn32vtmzhtft.jpg


tau(v) = V -> nat. Zahlen
pi(v) = V -> nat. Zahlen von 0 bis P-1


max(tau(v)) für jedes v ist klar: das v wählen, für den der Funktionswert der größte ist. Es existiert auch nur ein größter Knoten!

Aber der Teil danach, jetzt habe ich das größte v, v_max: Das kleinste Tupel (pi(v_max), tau(v_max)) macht keinen Sinn, weil Ordnung nicht definiert - und nur eines existiert. Ist es als min(pi(v_max), tau(v_max)) zu lesen? Ich frag, weil ich in dem Fall nur semantisch gerade noch nicht durchsteige.

EDIT: zu Teil 2, so ganz können meinen Vorschläge nicht hinhauen. Mit P=1 krieg ich hier in einem Beispiel tau(v_max) = n-1 >> 0, pi(v_max) kann ja nur 0 sein. Aber nach der Lese wär ja T_1 = min(0, n-1) = 0, die Lösung ist aber n-1. Algorithmisch könnte man jetzt sagen "immer anders rum als du denkst", was aber beknackt ist :ugly:

[Trap]

Das Schreibweise mit dem langen Pfeil für Phi gibt Definitions- und Wertebereich der Funktion an. Ich würde das als gerichteter Graph mit Eingangsgrad v wird abgebildet auf gerichteten Graph lesen.

Min und Max bezieht sich beides auf den Wert, die Variable drunter gibt an welche Variable variiert wird. Man sucht das (pi,tau)-minimale v-maximum von tau(v). Dabei ist das v-maximum natürlich keine Konstante, sondern hängt von tau ab, muss also für jede (pi,tau) Kombination neu bestimmt werden.

[Marscel]

Ich hab im vorliegenden Fall immer mit solchen Gestalten zu tun, alle Kanten laufen unidirektional in Richtung eines Senkenknotens. Muss allerdings nicht balanciert sein.

http://666kb.com/i/c9rire2ladjxmgexh.png

Das Schreibweise mit dem langen Pfeil für Phi gibt Definitions- und Wertebereich der Funktion an. Ich würde das als gerichteter Graph mit Eingangsgrad v wird abgebildet auf gerichteten Graph lesen.

Sodass G dann Element von D ist. Meine Frage ist darüber hinaus noch, was könnte diese Abbildung bedeuten? Mir fällt da eigentlich nur ein, dass es eine Konstruktionsvorschrift sein kann, weil ein azyklischer, gerichteter Graph ist ja noch nicht weiter bedingt, dass man ihn als wurzelgerichtet aufzufassen hat.

Min und Max bezieht sich beides auf den Wert, die Variable drunter gibt an welche Variable variiert wird. Man sucht das (pi,tau)-minimale v-maximum von tau(v). Dabei ist das v-maximum natürlich keine Konstante, sondern hängt von tau ab, muss also für jede (pi,tau) Kombination neu bestimmt werden.

Ich kann dir leider nicht ganz folgen, ich hab folgendes Beispiel für P=1:

http://666kb.com/i/c9rj2wq1wjvpvdwnp.png

Angemerkt: für jede Kante v -> v' gilt tau(v') >= tau(v)+1.

Der Vertex, der für tau am größten ist, ist hier ja v_14. Die Senke ist für die Beobachtung das interessante. T_1 soll damit 7 sein.

Ein v-Maximum von tau(v) hab ich damit ja, mehr sollten es hier auch nicht geben. Wie kann man denn "(pi,tau)-minimale v-maximum" zu verstehen? Als Tupel, Vektor? Ich frage, weil sich das nach einer Ordnung anhört, die ich nicht sehe.

[Trap]

Wenn es sowieso nur ein Pi gibt und das Maximum von v nicht auf das jeweilige tau beschränkt ist, versteh ich die Notation auch nicht.

[Marscel]

Wenn es sowieso nur ein Pi gibt und das Maximum von v nicht auf das jeweilige tau beschränkt ist, versteh ich die Notation auch nicht.

Bei P=2 wäre pi alternierend 0,1 usw., mit P als Anzahl von Prozessoren, pi die Belegung einer Operation und tau als vergangene, diskrete Zeit.

Aber danke soweit.