Ausfall einer Kante eines Knot < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: ![[]](/images/popup.gif) http://www.uni-protokolle.de/foren/viewt/89008,0.html
Ich sitze nun schon einiger Zeit vor einem Graphentheorietischen Problem.
Dieses Beschäftigt sich mit der Frage: Wenn in einem Graphen ein Knoten oder eine Kante ausfällt, wie wirkt es sich auf die anderen Knote/Kante aus? Und wie kann ich die Auswirkung Math. beschreiben?
Weitere Frage:
Welche Operationen kann ich in der Adjazenzmatrix ausüben und welche Ergebnisse liefern mir diese?
Danke für eure Hilfe und falls Ihr noch fragen habt wie ich das genau meine dann stellt diese.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:12 Di 10.10.2006 | | Autor: | DaMenge |
Hi,
also ich hab mir auch die Sache im anderem Forum durchgelesen, aber verstehe immernoch nicht, was du denn haben willst...
Also gegeben ist ein Graph, ja?
ist er gerichtet/ungerichtet? notwendig zusammenhängend? oder sonstige Sachen wie Kosten vorhanden?
das kann man ja alles nett als Adjazenzmatrix und Kostenmatrix darstellen oder sonst wie
(bei ungerichtetem Graph ersetze jede Kante mit zwei gerichteten in unterschiedlicher Richtung, dann hast du einen gerichteten)
so, jetzt willst du also einen Knoten entfernen, ja?
Also du willst ja bestimmt nicht die Dimension der Matrix verändern, oder doch?
Wenn nicht : dann reicht es ja (für ein Netzwerkproblem), dass der Knoten nicht mehr erreicht wird - also lösche man auch alle Kanten (muss man ja ehh machen, sonst wären diese Kanten ja gar nicht mehr definiert, weil ein beteiligter Knoten aus der Definitionsmenge verschwunden ist)
Was heißt das also für die Adjazenzmatrix? welche Einträge werden dann zu 0 ?
(für die Kosten kann man auf diesen Kanten dann "unendlich" annehmen oder so)
wenn du weißt, was mit der Adjazenzmatrix passiert, kannst du dein ganzes Wissen über Matrixmanipulationen aus LA anwenden um genau das in Abhängigkeit des Index i (das sei unser zu entfernender Knoten) zu machen...
soweit so gut - hoffe ich.
Aber was meinst du jetzt genau mit : "wie weit bemerke ich den Ausfall im Graph"
was willst du denn dort bemerken? also worauf kommt es dir dann an?
(zusammenhängend? irgendwelche Wege ? oder wie ? und was bringt dir eine Matrik auf der Matrix? was soll diese beschreiben?)
viele grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Do 09.11.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
