Isomorfismgrafen kan beskrivas som en graf där en enda graf kan ha mer än en form. Det betyder att två olika grafer kan ha samma antal kanter, hörn och samma kanter. Dessa typer av grafer kallas isomorfismgrafer. Exemplet på en isomorfismgraf beskrivs enligt följande:
textstorlek latex
Grafen ovan innehåller följande saker:
- Samma graf representeras i mer än en form.
- Därför kan vi säga att dessa grafer är isomorfismgrafer.
Villkor för grafisomorfism
Alla två grafer kommer att kallas isomorfism om de uppfyller följande fyra villkor:
- Det kommer att finnas lika många hörn i de givna graferna.
- Det kommer att finnas lika många kanter i de givna graferna.
- Det kommer att finnas en lika stor gradsekvens i de givna graferna.
- Om den första grafen bildar en cykel med längden k med hjälp av hörn {v1, v2, v3, …. vk}, då måste en annan graf också bilda samma cykel av samma längd k med hjälp av hörn {v1, v2, v3, …. vk}.
Obs: Gradsekvensen för en graf kan beskrivas som en sekvens av grad av alla hörn i stigande ordning.
Viktiga punkter
- För att två grafer ska vara en isomorfism är de nödvändiga villkoren de ovan definierade fyra villkoren.
- Det är inte nödvändigt att de ovan definierade villkoren är tillräckliga för att visa att de givna graferna är isomorfa.
- Om två grafer uppfyller de ovan definierade fyra villkoren, är det inte ens då nödvändigt att graferna säkert kommer att vara isomorfism.
- Om grafen inte uppfyller några villkor kan vi säga att graferna verkligen inte är en isomorfism.
Tillräckliga villkor för grafisomorfism
Om vi vill bevisa att två grafer är isomorfism, finns det några tillräckliga villkor som vi kommer att ge oss garantera att de två graferna säkert är isomorfism. När de två graferna har rensats framgångsrikt från alla ovanstående fyra villkor, först då kommer vi att kontrollera dessa grafer till tillräckliga förhållanden, som beskrivs enligt följande:
- Om komplementgraferna för båda graferna är isomorfism, kommer dessa grafer säkert att vara en isomorfism.
- Om de intilliggande matriserna för båda graferna är desamma, kommer dessa grafer att vara en isomorfism.
- Om motsvarande grafer för två grafer erhålls med hjälp av att radera några hörn i en graf, och deras motsvarande bilder i andra bilder är isomorfism, bara då kommer dessa grafer inte att vara en isomorfism.
När två grafer uppfyller något av ovanstående villkor kan vi säga att dessa grafer säkert är isomorfism.
Exempel på grafisomorfism
Det finns många exempel på grafisomorfism, som beskrivs enligt följande:
Exempel 1:
I det här exemplet har vi visat om följande grafer är isomorfism.
Lösning: För detta kommer vi att kontrollera alla fyra villkoren för grafisomorfism, som beskrivs enligt följande:
Villkor 1:
- I graf 1 finns det totalt 4 antal hörn, dvs G1 = 4.
- I diagram 2 finns det totalt 4 antal hörn, dvs G2 = 4.
Här,
Det finns lika många hörn i båda graferna G1 och G2. Så dessa grafer uppfyller villkor 1. Nu ska vi kontrollera det andra villkoret.
Villkor 2:
- I diagram 1 finns det totalt 5 antal kanter, dvs G1 = 5.
- I diagram 2 finns det totalt 6 antal kanter, dvs G2 = 6.
Här,
Det finns inte lika många kanter i båda graferna G1 och G2. Så dessa grafer uppfyller inte villkor 2. Nu kan vi inte kontrollera alla återstående villkor.
Eftersom dessa grafer bryter mot villkor 2. Så dessa grafer är inte en isomorfism.
∴ Graf G1 och graf G2 är inte isomorfismgrafer.
Exempel 2:
I det här exemplet har vi visat om följande grafer är isomorfism.
Lösning: För detta kommer vi att kontrollera alla fyra villkoren för grafisomorfism, som beskrivs enligt följande:
Villkor 1:
- I graf 1 finns det totalt 4 antal hörn, dvs G1 = 4.
- I diagram 2 finns det totalt 4 antal hörn, dvs G2 = 4.
- I diagram 3 finns det totalt 4 antal hörn, dvs G3 = 4.
Här,
Det finns lika många hörn i alla grafer G1, G2 och G3. Så dessa grafer uppfyller villkor 1. Nu ska vi kontrollera det andra villkoret.
Villkor 2:
- I diagram 1 finns det totalt 5 antal kanter, dvs G1 = 5.
- I diagram 2 finns det totalt 5 antal kanter, dvs G2 = 5.
- I diagram 3 finns det totalt 4 antal kanter, dvs G2 = 4.
Här,
- Det finns lika många kanter i båda graferna G1 och G2. Så dessa grafer uppfyller villkor 2.
- Men det finns inte lika många kanter i graferna (G1, G2) och G3. Så graferna (G1, G2) och G3 uppfyller inte villkor 2.
Eftersom graferna (G1, G2) och G3 bryter mot villkor 2. Så vi kan säga att dessa grafer inte är en isomorfism.
∴ Graf G3 är varken isomorfism med graf G1 eller med graf G2.
Eftersom graferna uppfyller G1 och G2 villkor 2. Så vi kan säga att dessa grafer kan vara en isomorfism.
∴ Graferna G1 och G2 kan vara en isomorfism.
Nu ska vi kontrollera det tredje villkoret för graferna G1 och G2.
sträng till json-objekt
Villkor 3:
- I grafen 1 är graden av sekvens s {2, 2, 3, 3}, dvs G1 = {2, 2, 3, 3}.
- I grafen 2 är graden av sekvens s {2, 2, 3, 3}, dvs. G2 = {2, 2, 3, 3}.
Här
Det finns lika många gradsekvenser i båda graferna G1 och G2. Så dessa grafer uppfyller villkor 3. Nu ska vi kontrollera det fjärde villkoret.
Villkor 4:
Graf G1 bildar en cykel med längd 3 med hjälp av hörn {2, 3, 3}.
Graf G2 bildar också en cykel med längd 3 med hjälp av hörn {2, 3, 3}.
Här,
Den visar att båda graferna innehåller samma cykel eftersom båda graferna G1 och G2 bildar en cykel med längd 3 med hjälp av hörn {2, 3, 3}. Så dessa grafer uppfyller villkor 4.
Således,
- Graferna G1 och G2 uppfyller alla ovanstående fyra nödvändiga villkor.
- Så G1 och G2 kan vara en isomorfism.
Nu ska vi kontrollera tillräckliga förhållanden för att visa att graferna G1 och G2 är en isomorfism.
hitta blockerade nummer på Android
Kontrollerar tillräckliga förhållanden
Som vi har lärt oss att om komplementgraferna för båda graferna är isomorfism, kommer de två graferna säkert att vara en isomorfism.
Så vi kommer att rita komplementgraferna för G1 och G2, som beskrivs enligt följande:
I ovanstående komplementgrafer av G1 och G2 kan vi se att båda graferna är isomorfism.
∴ Graferna G1 och G2 är isomorfism.
Exempel 3:
I det här exemplet har vi visat om följande grafer är isomorfism.
Lösning: För detta kommer vi att kontrollera alla fyra villkoren för grafisomorfism, som beskrivs enligt följande:
Villkor 1:
- I graf 1 finns det totalt 8 antal hörn, dvs G1 = 8.
- I diagram 2 finns det totalt 8 antal hörn, dvs G2 = 8.
Här,
Det finns lika många hörn i båda graferna G1 och G2. Så dessa grafer uppfyller villkor 1. Nu ska vi kontrollera det andra villkoret.
Villkor 2:
- I diagram 1 är det totala antalet kanter 10, dvs G1 = 10.
- I diagram 2 är det totala antalet kanter 10, dvs G2 = 10.
Här,
vad är alfabetsnummer
Det finns lika många kanter i båda graferna G1 och G2. Så dessa grafer uppfyller villkor 2. Nu ska vi kontrollera det tredje villkoret.
Villkor 3:
- I grafen 1 är graden av sekvens s {2, 2, 2, 2, 3, 3, 3, 3}, dvs G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- I grafen 2 är graden av sekvens s {2, 2, 2, 2, 3, 3, 3, 3}, dvs. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Här
Det finns lika många gradsekvenser i båda graferna G1 och G2. Så dessa grafer uppfyller villkor 3. Nu ska vi kontrollera det fjärde villkoret.
Villkor 4:
- Graf G1 bildar en cykel av längd 4 med hjälp av grad 3 hörn.
- Graf G2 bildar inte en cykel av längd 4 med hjälp av hörn eftersom hörn inte är intill varandra.
Här,
Både graferna G1 och G2 bildar inte samma cykel med samma längd. Så dessa grafer bryter mot villkor 4.
Eftersom graferna G1 och G2 bryter mot villkor 4. Så på grund av överträdelsen av villkor 4 kommer dessa grafer inte att vara en isomorfism.
∴ Graferna G1 och G2 är inte en isomorfism.