matematikk.net

Sitter med en oppgave jeg ikke helt får starta på.

Avgjør om grafene under er parvis isomorfe eller ikke. Hvis de er det, gi
en eksplisitt isomorfi, og hvis de ikke er det, forklar hvorfor.



Jeg er innledende kjent med hva isomorfi er, men er usikker på hvordan man går frem for å finne en isomorfi som man ikke vet finnes.

Det jeg tenker er at jeg kunne begynt med å lage en funksjon [tex]f \ : \ M_1 \right M_2[/tex] der jeg bare starter med et par hjørner, men er det nødvendig å kjøre slik trial & error-fremgang? Slik jeg ser det så må jeg kanskje gjennom 4 eller flere forskjellige funksjoner som må defineres hjørne for hjørne.

Noen som har en grei strategi på slike?

Som alltid, på forhånd takk!

Sånne oppgaver er generelt vanskelige, men en start er å spørre seg selv "tror jeg disse grafene er isomorfe eller ikke?". Mener man at svaret er ja må man typisk finne en isomorfi, mens om man mener svaret er nei må man finne en måte å bevise dette på. Den typiske måten man gjør det på er å finne en egenskap som bevares under isomorfi, men som ikke deles av de to grafene. Om for eksempel M_2 bare hadde hatt fem noder eller hatt en node av grad fem kunne vi umiddelbart slått fast at grafene ikke var isomorfe.

Om du vil prøve å konstruere en isomorfi f er det lettest å 'bare begynne' et sted. M_1 er ganske symmetrisk, så sannsynligvis er det trygt å begynne med å si at f(1)=a. Det må da være kanter mellom a og f(3), f(4), f(5), så i en eller annen rekkefølge er disse b, c, e. Mellom b og c er det en kant, og mellom hvilke to av 3, 4, 5 er det en kant? Fortsett sånn, så ender du fort opp med isomorfi eller kanskje et greit utgangspunkt for et motsigelsesbevis.

Skjønner! Men det virker veldig brute force. Jeg gjorde et forsøk som tok forholdsvis lang tid og viste seg å gå i grus. Ser ut som det er mange kombinasjoner å prøve.

Virker litt som en IQ-test. Kanskje jeg skulle kunne sett et mønster og bevise/motbevise det derfra?

Er ganske brute force, men her er det ganske små grafer det er snakk om, så umulig er det ikke. Et mønster du kan legge merke til er at M_2 består av to trekanter - (a, b, c) og (e,f,d) - med kanter mellom a og e, b og f og mellom c og d. Prøver du å finne en tilsvarende 'dekomposisjon' av M_1 kan det være en måte å finne en isomorfi av.

Ja, det var det mønsteret som var lettest å bite seg merke i, selv om jeg så det i M_1 i første omgang.

Ser dette greit ut?

http://i.imgur.com/6qEgf.png

Ser bra ut!

Hmm, kan man sjekke isomorfi ved å bruke nabomatriser? Jeg synes det er ufattelig kjedelig å sjekke ved å brute-force alle tenkelige bijeksjoner.