Durchmesser isomorpher Graphen

Question

Müssen zwei isomorphe Graphen den gleichen Durchmesser haben? Soweit ich weiß, muss ihre Adjazenzmatrix beibehalten werden, und wenn sie dieselbe Adjazenzmatrixdarstellung haben, bedeutet dies, dass sie auch denselben Durchmesser haben sollten?

Answer 1

Eine Graph-Eigenschaft ist eine Isomorphismus-invariante Eigenschaft von Graphen. Das ist,$P$ ist eine Diagrammeigenschaft, wenn $P(G_1) \leftrightarrow P(G_2)$ wann immer $G_1$ und $G_2$ sind isomorph.

Jede Eigenschaft von Diagrammen, die sich nicht auf bestimmte Namen von Scheitelpunkten bezieht, ist eine Diagrammeigenschaft. Dies schließt alle üblichen Eigenschaften von Graphen ein: Konnektivität, Durchmesser (dh die Eigenschaft, Durchmesser zu haben$D$), chromatische Zahl (dh die Eigenschaft, eine chromatische Zahl zu haben $\chi$), und so weiter. Eine Eigenschaft von Graphen, die keine Grapheneigenschaft ist, lautet: "Die Eckpunkte 1 und 2 sind verbunden".

Lassen Sie uns zeigen, dass Konnektivität eine Diagrammeigenschaft ist. Auf die gleiche Weise können Sie zeigen, dass der Durchmesser eins ist. Lassen$G_1=(V_1,E_1)$ und $G_2=(V_2,E_2)$seien zwei isomorphe Graphen. Dies bedeutet, dass es eine Bijektion gibt$\phi\colon V_1 \to V_2$ so dass $(x,y) \in E_1$ iff $(\phi(x),\phi(y)) \in E_2$. Wir werden das zeigen, wenn$G_1$ ist dann verbunden $G_2$ist auch verbunden. Das gleiche Argument (mit$\phi^{-1}$) zeigt das Gegenteil und vervollständigt den Beweis.

Nehme an, dass $G_1$ ist verbunden und lassen $a,b \in V_2$. Schon seit$G_1$ verbunden ist, gibt es einen Pfad in $G_1$ zwischen $\phi^{-1}(a)$ und $\phi^{-1}(b)$, sagen $\phi^{-1}(a),v_1,\ldots,v_\ell,\phi^{-1}(b)$. Dann$a,\phi(v_1),\ldots,\phi(v_\ell),b$ ist ein Weg in $G_2$ Anschließen $a$ und $b$.