Adjazenzmatrix, Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Bedeutung von Diagonaleintraegen von [mm] A^3, [/mm] wobei A Adjazenzmatrix eines beliebigen Graphen |
Hallo,
bin auf folgende Frage gestossen: nimmt man von der Adjazenzmatrix A eines beliebigen Graphen die Potenz [mm] A^3, [/mm] was bedeuten dann die Diagonaleintraege von [mm] A^3?
[/mm]
Bei [mm] A^2 [/mm] waere ja das z.B der Grad jedes Knotens des Graphen. Ich vermute, es gibt auch fuer [mm] A^3 [/mm] eine analoge Aussage.
Weiss zufaellig hier jemand was dazu? Waere sehr dankbar!!
|
|
| |
|
Hallo Margarita,
> Ich vermute, es gibt auch fuer [mm]A^3[/mm] eine analoge
> Aussage.
Hm, ich sehe nicht, was die Diagonaleinträge von [mm] A^3 [/mm] besagen sollten, finde auch nichts dazu. Meines Erachtens jagst Du da eine Chimäre.
Ich lasse die Frage halboffen, vielleicht mag mir ja noch jemand widersprechen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:11 Mo 03.10.2011 | | Autor: | felixf |
Moin!
> Bedeutung von Diagonaleintraegen von [mm]A^3,[/mm] wobei A
> Adjazenzmatrix eines beliebigen Graphen
>
> bin auf folgende Frage gestossen: nimmt man von der
> Adjazenzmatrix A eines beliebigen Graphen die Potenz [mm]A^3,[/mm]
> was bedeuten dann die Diagonaleintraege von [mm]A^3?[/mm]
> Bei [mm]A^2[/mm] waere ja das z.B der Grad jedes Knotens des
> Graphen. Ich vermute, es gibt auch fuer [mm]A^3[/mm] eine analoge
> Aussage.
> Weiss zufaellig hier jemand was dazu? Waere sehr dankbar!!
Der $(i, j)$-Eintrag von [mm] $A^n$ [/mm] sagt, wieviele Moeglichkeiten es gibt, von der Ecke $i$ zur Ecke $j$ in genau $n$ Schritten zu gehen.
Fuer $i = j$ und $n = 2$ erhaelt man also die Anzahl der Wege, die in $i$ anfangen und enden und wo es genau einen Schritt dazwischen gibt. Das ist also genau die Anzahl der Kanten, die inzident zu $i$ sind, d.h. es ist der Grad von $i$.
Bei $i = j$ und $n = 3$ erhaelst du zwei Mal die Anzahl der Dreiecke im Graphen, die $i$ als Eckpunkt haben. (Weil es zwei Moeglichkeiten gibt, so ein Dreieck abzuschreiten: einmal "links" rum und einmal "rechts" rum.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:59 Mo 03.10.2011 | | Autor: | reverend |
Hallo Felix,
> Der [mm](i, j)[/mm]-Eintrag von [mm]A^n[/mm] sagt, wieviele Moeglichkeiten es
> gibt, von der Ecke [mm]i[/mm] zur Ecke [mm]j[/mm] in genau [mm]n[/mm] Schritten zu
> gehen.
Ah ja, das wars. Meine Graphentheorie ist doch zu lang her. Sorry.
> Fuer [mm]i = j[/mm] und [mm]n = 2[/mm] erhaelt man also die Anzahl der Wege,
> die in [mm]i[/mm] anfangen und enden und wo es genau einen Schritt
> dazwischen gibt. Das ist also genau die Anzahl der Kanten,
> die inzident zu [mm]i[/mm] sind, d.h. es ist der Grad von [mm]i[/mm].
>
> Bei [mm]i = j[/mm] und [mm]n = 3[/mm] erhaelst du zwei Mal die Anzahl der
> Dreiecke im Graphen, die [mm]i[/mm] als Eckpunkt haben. (Weil es
> zwei Moeglichkeiten gibt, so ein Dreieck abzuschreiten:
> einmal "links" rum und einmal "rechts" rum.)
Die Frage war doch für die Adjazenzmatrix eines beliebigen Graphen gestellt, also auch eines mit Schleifen oder - besonders - auch gerichteten Graphen. Der Faktor 2 kann also nicht allgemeingültig sein. Nur: wie ist die Lage dann? Das überblicke ich nicht.
Ansonsten gehe ich mal wieder Kochen. Das kann ich hoffentlich besser.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:38 Mo 03.10.2011 | | Autor: | felixf |
Moin rev,
> > Der [mm](i, j)[/mm]-Eintrag von [mm]A^n[/mm] sagt, wieviele Moeglichkeiten es
> > gibt, von der Ecke [mm]i[/mm] zur Ecke [mm]j[/mm] in genau [mm]n[/mm] Schritten zu
> > gehen.
>
> Ah ja, das wars. Meine Graphentheorie ist doch zu lang her.
> Sorry.
kein Problem 
> > Fuer [mm]i = j[/mm] und [mm]n = 2[/mm] erhaelt man also die Anzahl der Wege,
> > die in [mm]i[/mm] anfangen und enden und wo es genau einen Schritt
> > dazwischen gibt. Das ist also genau die Anzahl der Kanten,
> > die inzident zu [mm]i[/mm] sind, d.h. es ist der Grad von [mm]i[/mm].
> >
> > Bei [mm]i = j[/mm] und [mm]n = 3[/mm] erhaelst du zwei Mal die Anzahl der
> > Dreiecke im Graphen, die [mm]i[/mm] als Eckpunkt haben. (Weil es
> > zwei Moeglichkeiten gibt, so ein Dreieck abzuschreiten:
> > einmal "links" rum und einmal "rechts" rum.)
>
> Die Frage war doch für die Adjazenzmatrix eines beliebigen
> Graphen gestellt, also auch eines mit Schleifen oder -
> besonders - auch gerichteten Graphen. Der Faktor 2 kann
> also nicht allgemeingültig sein. Nur: wie ist die Lage
> dann? Das überblicke ich nicht.
Da hast du Recht. Allerdings: die Interpretation der Diagonaleintraege von [mm] $A^2$ [/mm] wie im Post von margarita geht ebenfalls nur bei solch schoenen Graphen. Falls der Graph Schlaufen hat oder gerichtet ist, muss man sich sehr genau ueberlegen was passiert.
Die Interpretation ueber die Anzahl der Wege gilt uebrigens auch bei Schlaufen und gerichteten Graphen (solange alle Eintraege von $A$ entweder 0 oder 1 sind).
> Ansonsten gehe ich mal wieder Kochen. Das kann ich
> hoffentlich besser.
Viel Spass und guten Appetit :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:39 Mo 03.10.2011 | | Autor: | margarita |
Hallo!!
Vielen Dank erst mal fuer die Antworten.
Haette ich noch dazu schreiben sollen: es handelt sich bei dem Graphen um einen beliebigen ungerichteten Graphen.
> Bei [mm]i = j[/mm] und [mm]n = 3[/mm] erhaelst du zwei Mal die Anzahl der
> Dreiecke im Graphen, die [mm]i[/mm] als Eckpunkt haben. (Weil es
> zwei Moeglichkeiten gibt, so ein Dreieck abzuschreiten:
> einmal "links" rum und einmal "rechts" rum.)
>
Das hilft mir schon mal weiter.
Ich werde nun mit den geposteten Informationen weiterarbeiten.
Danke nochmals.
Tschau, * margarita
|
|
|
|
