Graphentheorie: Erklärung Nachbarschaftsmatrix?

Question

Aufgabe 43:

Wir definieren die folgenden drei Graphen:

$$\begin{array}{l} {V\left(G_{1}\right):=\left\{P_{1}, P_{2}, P_{3}, P_{4}, P_{5}\right\}} \\ {E\left(G_{1}\right):=\left\{\left(P_{1}, P_{2}\right),\left(P_{2}, P_{3}\right),\left(P_{3}, P_{4}\right),\left(P_{4}, P_{5}\right),\left(P_{5}, P_{1}\right)\right\}} \\ {V\left(G_{2}\right):=\left\{P_{1}, P_{2}, P_{3}\right\}} \\ {E\left(G_{2}\right):=\left\{\left(P_{1}, P_{2}\right),\left(P_{1}, P_{3}\right)\right\}} \\ {V\left(G_{3}\right):=\left\{P_{1}, P_{2}, P_{3}\right\}} \\ {E\left(G_{3}\right):=\left\{\left(P_{1}, P_{2}\right),\left(P_{2}, P_{3}\right)\right\}} \end{array}$$

a) Geben Sie die drei Nachbarschaftsmatrizen der obigen Graphen an.

b) Die Graphen $G_{2}$ und $G_{3}$ sind isomorph. Geben Sie einen Isomorphismus an.

c) Erläutern Sie wie man anhand der Nachbarschaftsmatrizen von $G_{2}$ und $G_{3}$ hätte sehen können, dass $G_{2}$ und $G_{3}$ isomorph sind.

Hinweis: Was hat das Vertauschen von Punkten der Graphen mit dem Vertauschen von Zeilen bzw. Spalten der Matrizen zu tun?

Aufgabe 44:

Gegeben seien folgende beiden Matrizen:

$$M_{1}:=\left(\begin{array}{llll} {0} & {1} & {1} & {1} \\ {1} & {0} & {1} & {1} \\ {1} & {1} & {0} & {1} \\ {1} & {1} & {1} & {0} \end{array}\right), M_{2}:=\left(\begin{array}{llll} {0} & {1} & {0} & {1} \\ {1} & {0} & {1} & {0} \\ {0} & {1} & {0} & {1} \\ {1} & {0} & {1} & {0} \end{array}\right)$$

a) Zeichnen Sie die beiden Graphen mit den Nachbarschaftsmatrizen $M_{1}$ bzw. $M_{2}$
-Sei nun $G$ ein Graph mit Nachbarschaftsmatrix $M .$ Ferner seien $v, w \in V(G)$ und $k \in \mathbb{N}$

b) Wie können Sie mit Hilfe von $M$ bestimmen ob es einen Weg der länge kleiner gleich $k$ bzw. gleich $k$ von $v$ nach $w$ gibt?

c) Wie können Sie $d(v)$ mit Hilfe von $M$ bestimmen?

Comments

Lies dir mal folgendes bei Wikipedia durch

--> https://de.wikipedia.org/wiki/Adjazenzmatrix

Es wäre günstig, wenn du immer die komplette Aufgabenstellung hier reinstellst. Ich kann nicht beurteilen worauf sich M1 und M2 beziehen oder ob sie einfach nur so gegeben sind.

---

Nur zum Verständnis: Für die drei Graphen bei Aufgabe 43 möchtest du die Nachbarschaftsmatrizen bilden?

---

Das steht unter dem Link bei Wikipedia drin

Beim Graph G1 haben wir 5 Punkte P1 bis P5 und die Kanten (P1,P2),(P2,P3),...

Ich würde die Nachbarschaftsmatrix also wie folgt aufstellen:

	P1	P2	P3	P4	P5
P1	0	1	0	0	1
P2	1	0	1	0	0
P3	0	1	0	1	0
P4	0	0	1	0	1
P5	1	0	0	1	0

---

ja könnte hinkommen, obgleich ich die Matrix in vertauschter Form in Erinnerung hatte...

.. und wenn man sich die Matrix M1 anschaut, erkennt man, dass diese 4 Knoten haben muss und jeder Knoten es mit den anderen gegenseitig "treibt" .)

---

Hier ein ausführlicheres Beispiel, was ich im Internet gefunden habe.

---

Zu Aufgabe 43 genau ich muss die Nachbarschaftsmatrix der Graphen bestimmen.

Graph 1 habe ich verstanden.

Stimmen meine annahmen zu Graph 2 und 3?

Graph 2

	p_{1}	p_{2}	p_{3}
p_{1}	0	0	0
p_{2}	1	0	0
p_{3}	1	0	0

Graph 3

	p_{1}	p_{2}	p_{3}
p_{1}	0	0	0
p_{2}	1	0	0
p_{3}	0	1	0

---

Ich hatte noch ein Fehler in meiner Matrix. Es waren ja keine gerichteten Kanten oder? Wenn sie ungerichtet sind (also nicht wie bei Bepprich) dann muss die Matrix symmetrisch sein.
Also eine Kante von P1 nach P2 ins automatisch auch eine Kante von P2 nach P1.

---

Ja, in der Tat, ob die Graphen in 43 gerichtet sind oder nicht, das ist hier die Frage .-)

---

Nach längere Überlegung vermute ich mal, das die Graphen ungerichtet sind, denn sonst hätte man beispielsweise für G2 geschrieben:

E(G2) = {(P1,P2), (P2,P1), (P1,P3), (P3,P1)}

Es war E(G2) = {(P1,P2), (P1,P3)}

Veranschaulicht: Knoten 1 hat mit Knoten 2 eine gemeinsame Kante und Knoten 1 hat mit Knoten 2 ebenfalls eine gemeinsame Kante.

Nachbarschaftsmatrix	1. Knoten	2. Knoten	3. Knoten
1. Knoten (mit welchen Knoten hat er Verbindungen ?) ->	0	1	1
2. Knoten (mit welchen Knoten hat er Verbindungen ?) ->	1	0	0
3. Knoten (mit welchen Knoten hat er Verbindungen ?) ->	1	0	0

---

 

ok dann müsste es ja so richtig sein?

Wie kann ich denn in der Klausur erkennen ob der Graph gerichtet ist oder nicht?

Kann mir jemand noch helfen wie man die 44a berechnen bzw. zeichnen kann?

Vielen vielen dank schon mal für die super Erklärungen :)

---

Wie du eurem Skript entnehmen kannst sollte bei gerichteten Graphen es eigentlich dabeistehen. Bei ungerichteten steht dann auch eventuell schlichte Graphen dabei.

---

Der Graph zu M1 und die Graphen (Respekt Mathecoach .-)) zu M2 stimmen.

Es gilt laut M2:

- Knoten 1 will was mit Knoten 2 und Knoten 4 anfangen.

- Knoten 2 scheint es auf die Knoten 1 (beruht auf Gegenseitigkeit) und 3 abzusehen.

- Knoten 3 hat sich Knoten 2 und Knoten 4  ausgeguckt.

- Knoten 4 giert auf Knoten 1 (beruht auf Gegenseitigkeit) und auf Knoten 3 (beruht auf Gegenseitigkeit).

Answer 1

In den Kommentaren sind jetzt schon alle Fragen beantwortet, die der Fragesteller hatte.

Ich denke damit ist die Frage erledigt.

Comments

Ich soll zeigen wie ich d(v) mit M bestimmen kann. M ist meine Nachbarschaftsmatrix. Ich hab auch noch gegeben

Soweit ich das richtig mitbekommen habe bestimmt man mit d(v) Anzahl Pfade, die am Knoten ankommen.

Damit müsstest du in der Nachbarschaftsmatrix nur die Summe der v. Zeile oder der v. Spalte nehmen.

---

Ok und wie kann ich das allgemein formulieren?

Bedeutet das, dass ich von beiden Matrizen die Summe nehmen soll oder von jeder einzeln?

---

M ist allgemein eine Matrix und weder M1 noch M2. Du sollst nur erklären wie man aus der Nachbarschaftsmatrix auf den Grad eines Knotens kommt. Und das geht über die Spalten oder Zeilensumme des Entsprechenden Knotens.

---

Ok also hätte ich bei knoten1,2,3,4 die spalten und zeilensumme von 3 ist das richtig?

---

Ja bei M1. Und dann schaust du dir jeden Knoten an und schaust wie viele Kanten immer wegführen. Sind das 3, dann hast du alles richtig gemacht.

---

Ok super vielen dank für die Erklärung :)