Alg.-Problem lösen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich muss ein Effizienzproblem lösen. Und zwar geht es um die Adjazenzmatrix in der Graphentheorie.
Ich muss mit der "totalen Quelle" arbeiten.
Definition: Eine totale Quelle in einem Graphen(gerichtet, keine Schleifen ) G = (V,E) ist Knoten mit Ausgrad |V| - 1 und Ingrad 0.
Also sozusagen die Wurzel ?
Und dieser Graph ist als Matrixdarstellung bezüglich ihrer Adjazenten (mit [mm] |V|^{2} [/mm] Einträgen ) gegeben.
Jetzt ist das Problem folgendes:
Es ist anscheinend möglich , dass man lineare Anfragen ( also |V|) an diese Matrix stellen kann.
Zeichnung:
[Dateianhang nicht öffentlich]
Ich habe mir folgendes überlegt:
Man guckt sich nur die Einsen an.
Wir sind z.B bei Zeile c da greifen wir uns ein Element raus , z.B [mm] \vektor{c \\ d} [/mm] ALso Zeile c Spalte d dort haben wir eine 1.
Jetzt gucken wir links und rechts von dieser 1 nach , ob da wieder ne 1 ist. Wenn das nicht der Fall ist , geht er raus. Sonst guckt er weiter.
Wobei mri grade einfällt , dass man das wieder mit Laufzeit [mm] V^{2} [/mm] macht.
Ich komme da nicht drauf.
Bitte um Hilfe.
Vielen Dank im Voraus.
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
Hi!
Das dürfte dir weiterhelfen:
http://www.inf.fu-berlin.de/lehre/SS11/infb/muster03.pdf
Seite 2.
|
|
|
| |
|
Hallo,
vielen Dank für die Antwort.
Allerdings steht da am Ende ; insgesamt ergebe sich eine Laufzeit von [mm] |V|^{2} [/mm] + |E|. Da ist ja leider wieder das Quadrat drin. Oder bezieht sich das auf das Entfernen der Kanten?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:25 Do 23.01.2014 | | Autor: | pc_doctor |
Hallo,
ich habe das Problem inzwischen selbst gelöst. Einfacher als gedacht.
Danke trotzdem.
|
|
|
| |
|
Ich habe eine ähnliche Aufgabe zu lösen und würde gerne wissen wie du das gemacht hast.
Ich bekomme nämlich auch beim besten Willen keinen linearen Aufwand hin.
Hilfe?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Mi 29.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
