isomorfi

[gjest trenger hjelp!]

Er det noen som kan hjelpe meg med hvordan man kan definere isomorfi for grafer som ikke er enkle?

[Markus]

Definisjonen på en grafisomorfi er så vidt jeg vet helt uavhengig om grafen er enkel eller ikke. La $G$ og $H$ være to grafer med hjørnemengde (vertex set på engelsk, jeg vet ikke en bedre oversettelse) $V(G)$ og $V(H)$ og kant-mengder (edge set) $E(G)$ og $E(H)$. Hvis det finnes bijektive funksjoner $$\theta : V(G) \to V(H) \\ \phi: E(G) \to E(H)$$ slik at $\psi_G(e)=uv$ hvis og bare hvis $\psi_H(\phi(e)) = \theta(u)\theta(v)$, så sies $G$ og $H$ å være isomorfe. Her denoterer $\psi_G(e)$ incidence function (igjen jeg kan ikke noe bra ord for dette på norsk), som sier oss endepunktene til kanten $e$ i grafen $G$.