Verschil tussen isomorfe en gelijke grafen

Hallo,
Ik heb het nu over grafen op school en wat ik niet begrijp is het verschil tussen isomorfe en gelijke grafen.
Wat ik er nu van begrijp is dat als grafen dezelfde buren hebben (als elk punt gelabeld is en tegenover hetzelfde punt staat) en evenveel lijnen erdoor lopen dat ze dan gelijk zijn en dat een graaf isomorf is als ze evenveel lijnen hebben als je de graaf herlabeld. Is dit waar?

Sefanj
Student hbo - vrijdag 15 september 2017

Antwoord

Twee grafen zijn gelijk als ze precies dezelfde punten en dezelfde lijnen hebben.
Ze zijn isomorf als ze er precies hetzelfde uitzien maar niet precies hetzelfde gelabeld zijn.
Bijvoorbeeld: Stel $V=\{1,2,3,4\}$ en $L_1=\{\{1,2\}\}$; dit geeft een graaf met vier punten en één lijn, tussen $1$ en $2$.
Met dezelfde $V$ en $L_2=\{\{3,4\}\}$ krijg je ook zo'n graaf maar nu met het ene lijntje van $3$ naar $4$, deze is niet gelijk aan de eerste.
De herlabeling $1\to3$, $2\to4$, $3\to2$, $4\to1$ laat zien dat deze twee grafen isomorf zijn.

kphart
vrijdag 15 september 2017

©2001-2024 WisFaq