Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Graphentheorie Adjazenzmatrix
Gehe zu Seite 1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Graphentheorie Adjazenzmatrix
 
Autor Nachricht
Rdata1983
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 09.10.2006
Beiträge: 34

BeitragVerfasst am: 09 Okt 2006 - 14:54:46    Titel: Graphentheorie Adjazenzmatrix

Hi Leute, ich lese schon einige Zeit hier im Forum mit nun habe ich selbst mal eine Frage.

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 Kanteausfällt, wie wirkt es sich auf die anderen Knote/Kante aus? Und wie kann ich die Auswirkung Math. beschreiben?

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.

Grüße Jörg
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 09 Okt 2006 - 15:04:50    Titel:

hm also wenn in einem graph nen knoten ausfällt bzw ne kante , dann kann er

- geteilt werden in 2 Graphen
- er kann Kreisfrei werden
- Pfade können verschwinden

mehr fällt mir hier nicht ein, da meine Graphentheroie ne Weile zurück liegt.

Ach und wenn ein Knoten ausfällt, verschwinden automatisch alle Kanten die zum Knoten hin bzw weg gingen.
Rdata1983
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 09.10.2006
Beiträge: 34

BeitragVerfasst am: 09 Okt 2006 - 15:19:28    Titel:

Genauere Problembeschreibung:

Also wenn in einem Graphen mit min 100 Knoten und sagen wir mal 500 Kanten ein Knoten ausfällt, fallen ... Kanten aus das ist so weit klar.
Schauen wir uns einmal die Adjazenzmatrix an, was passiert hier... gehen wir davon aus alle a ij=1 ( nicht alle Kreisfrei/ diagonale ja dann 0)dann währe alle punkte mit allen verbunden. Wenn einer sagen wir 50 ausfallen wie kann ich die alte und die neue matrix miteinander vergleichen? gibts da ne matrix Operation?

Und wenn ich jetzt an gewisse Wege denke, fallen hier auch einige weg, wie weit bemerke ich den Ausfall im Graph.
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 09 Okt 2006 - 15:26:06    Titel:

das is schon etwas arg lang her, aber ich denke so gross vergleichen kannst du da nix... da steht ja auch nur, dass jeder knoten mit allen anderen ausser sich selbst ( diagonale 0 ) verbunden ist.... der rest ist mit 1 gefüllt und wenn dann 50 wegfallen dann fehlen wir 50 1en..

was ich mir vorstellen könnte ist, dass man dann vergleichen kann, ob es gewisse pfade noch gibt oder halt nicht, bzw wird er durch die 50 fehlden knoten evtl planar? aber operationen gibt es meines wissens nach nicht
Rdata1983
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 09.10.2006
Beiträge: 34

BeitragVerfasst am: 09 Okt 2006 - 15:43:52    Titel:

Es muss doch eine Matrix Operation geben, denn wenn die die Determinante ausrechne bekomme ich ja die Anzahl der möglichen Wege und die ist bei der einen ja weniger als bei der anderen!

Meine Idee währe: Man stelle sich eine Ebene vor, von der Seite schaut sie aus wie Wasser (wenn man verschiedene Metriken hat) und von oben sieht man den Graphen mit den verschiedenen wegen! (so weit klar)

Fällt nun ein Knoten aus dann sieht man in der Ebene ein Loch da wo der knoten war! wie bekommen die anderen knoten das mit? Wird die last an einzelnen Punkten erhöht?
Zusammen fassung: Adjazenzmatrik mit Metriken in Ebene vorstellen. Vielleicht ist das ein Ansatz?
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 09 Okt 2006 - 15:50:04    Titel:

Wikipedia:

Zitat:
Eine Adjazenzmatrix ist eine binäre Matrix, die alle Knoten beinhaltet und jeweils die Erreichbarkeit zum direkten Nachfolger markiert. Addiert mit der Einheitsmatrix ergibt sich die Erreichbarkeitsmatrix im ersten Schritt.


ansonsten sehe ich eine adjazenten matrix mehr als eine weiter art an, ungerichtete graphen darzustellen. eine weitaus schönere, wenn es sich um graphen mit vielen knoten&kanten handelt und auch eine schönere, wenn man graphen mit dem pc ver- bearbeiten will

EDIT:

Zitat:
Die Erreichbarkeitsmatrix ist eine binäre Matrix und gibt im n-ten Schritt die gesamte Erreichbarkeit der Knoten untereinander an.
Der 1. Schritt entsteht durch die Addition der Einheitsmatrix mit der Adjazenzmatrix. Der nächste Schritt ist immer die Anfangsmatrix multipliziert mit der vorherigen Matrix oder zum Beispiel der 3. Schritt multipliziert mit dem 2. Schritt ergibt den 5. Schritt. Tritt keine Veränderung zum jeweiligen nächsten Schritt ein, bricht der Algorithmus ab.
Rdata1983
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 09.10.2006
Beiträge: 34

BeitragVerfasst am: 09 Okt 2006 - 16:08:59    Titel:

OK das ist schonmal ganz gut, kann man was aus drei matrizen basteln 1 Adjazenzmatrix und zweites Ereichbarkeitsmatrix und 3 Metrikmatrix -> so das ich aus diesen dreien ein aussage treffen kann was in meinem Graph/Netzwerk passiert? Wenn Knoten ausfallen oder Kanten überlastet sind?

Und super vielen dank das es hier so schnell geht!
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 09 Okt 2006 - 16:17:10    Titel:

das ist mehr glück das ich heut ganzen tag lerne und hier chain f5 drücke wenn ich ne denkpause brauch Very Happy
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 10 Okt 2006 - 13:09:49    Titel:

Hm *nachdenk* Adjazentenmatrix is eine n x n matrix.... n ist anzahl der Knoten. Für jede Kante wird ein 1 eingetragen zw zwei Knoten. In einem Gerichteten.
Ich denke, du machst ihn " ungerichtet " in dem du einfach sowohl bei x1-> x3 also auch bei x3->x1 eine 1 einträgst. Dadurch wird die Matrix symmetrisch entlang der Hauptdiagonalen.
BBB
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 28.10.2005
Beiträge: 303

BeitragVerfasst am: 10 Okt 2006 - 13:19:10    Titel:

Rdata1983 hat folgendes geschrieben:
in der Adjazenzmatrix kann ich doch nur gerichtete Graphen eintragen oder?

Ne, wieso? Du hast bei einem ungerichteten dann eine symmetrische Adjazenzmatrix.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Graphentheorie Adjazenzmatrix
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2, 3  Weiter
Seite 1 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum