Isomorfismegrafen kan beskrives som en graf der en enkelt graf kan ha mer enn én form. Det betyr at to forskjellige grafer kan ha samme antall kanter, toppunkter og samme kanter tilkobling. Disse typer grafer er kjent som isomorfismegrafer. Eksemplet på en isomorfismegraf er beskrevet som følger:
Grafen ovenfor inneholder følgende ting:
- Den samme grafen er representert i mer enn én form.
- Derfor kan vi si at disse grafene er isomorfismegrafer.
Betingelser for grafisomorfisme
Hvilke som helst to grafer vil bli kjent som isomorfisme hvis de tilfredsstiller følgende fire betingelser:
- Det vil være like mange hjørner i de gitte grafene.
- Det vil være like mange kanter i de gitte grafene.
- Det vil være like mye gradsekvens i de gitte grafene.
- Hvis den første grafen danner en syklus med lengde k ved hjelp av toppunkter {v1, v2, v3, …. vk}, så må en annen graf også danne den samme syklusen med samme lengde k ved hjelp av hjørnene {v1, v2, v3, …. vk}.
Merk: Gradsekvensen til en graf kan beskrives som en gradsekvens for alle toppunktene i stigende rekkefølge.
Viktige poeng
- For at to grafer skal være en isomorfisme, er de nødvendige betingelsene de ovenfor definerte fire betingelsene.
- Det er ikke nødvendig at de ovenfor definerte betingelsene vil være tilstrekkelige til å vise at de gitte grafene er isomorfe.
- Hvis to grafer tilfredsstiller de ovenfor definerte fire betingelsene, selv da, er det ikke nødvendig at grafene sikkert vil isomorfisme.
- Hvis grafen ikke tilfredsstiller noen betingelser, kan vi si at grafene absolutt ikke er en isomorfisme.
Tilstrekkelige betingelser for grafisk isomorfisme
Hvis vi ønsker å bevise at to grafer er isomorfisme, er det noen tilstrekkelige betingelser som vi vil gi oss garanti for at de to grafene helt sikkert er isomorfisme. Når de to grafene er ryddet alle de fire ovennevnte betingelsene, vil vi først kontrollere disse grafene til tilstrekkelige forhold, som er beskrevet som følger:
- Hvis komplementgrafene til begge grafene er isomorfisme, vil disse grafene sikkert være en isomorfisme.
- Hvis de tilstøtende matrisene til begge grafene er de samme, vil disse grafene være en isomorfisme.
- Hvis de tilsvarende grafene til to grafer oppnås ved hjelp av å slette noen toppunkter i en graf, og deres tilsvarende bilder i andre bilder er isomorfisme, vil disse grafene ikke være en isomorfisme.
Når to grafer tilfredsstiller noen av betingelsene ovenfor, kan vi si at disse grafene sikkert er isomorfisme.
Eksempler på grafisk isomorfisme
Det er mange eksempler på grafisomorfisme, som er beskrevet som følger:
Eksempel 1:
I dette eksemplet har vi vist om følgende grafer er isomorfisme.
Løsning: For dette vil vi sjekke alle de fire betingelsene for grafisomorfisme, som er beskrevet som følger:
Tilstand 1:
- I graf 1 er det totalt 4 antall hjørner, dvs. G1 = 4.
- I graf 2 er det totalt 4 antall hjørner, dvs. G2 = 4.
Her,
Det er like mange hjørner i begge grafene G1 og G2. Så disse grafene tilfredsstiller betingelse 1. Nå skal vi sjekke den andre betingelsen.
Tilstand 2:
- I graf 1 er det totalt 5 antall kanter, dvs. G1 = 5.
- I graf 2 er det totalt 6 antall kanter, dvs. G2 = 6.
Her,
Det har ikke like mange kanter i begge grafene G1 og G2. Så disse grafene tilfredsstiller ikke betingelse 2. Nå kan vi ikke sjekke alle de resterende betingelsene.
Siden disse grafene bryter med betingelse 2. Så disse grafene er ikke en isomorfisme.
∴ Graf G1 og graf G2 er ikke isomorfismegrafer.
Eksempel 2:
I dette eksemplet har vi vist om følgende grafer er isomorfisme.
Løsning: For dette vil vi sjekke alle de fire betingelsene for grafisomorfisme, som er beskrevet som følger:
Tilstand 1:
- I graf 1 er det totalt 4 antall hjørner, dvs. G1 = 4.
- I graf 2 er det totalt 4 antall hjørner, dvs. G2 = 4.
- I graf 3 er det totalt 4 antall hjørner, dvs. G3 = 4.
Her,
Det er like mange hjørner i alle grafene G1, G2 og G3. Så disse grafene tilfredsstiller betingelse 1. Nå skal vi sjekke den andre betingelsen.
Tilstand 2:
- I graf 1 er det totalt 5 antall kanter, dvs. G1 = 5.
- I graf 2 er det totalt 5 antall kanter, dvs. G2 = 5.
- I graf 3 er det totalt 4 antall kanter, dvs. G2 = 4.
Her,
- Det er like mange kanter i begge grafene G1 og G2. Så disse grafene tilfredsstiller betingelse 2.
- Men det har ikke like mange kanter i grafene (G1, G2) og G3. Så grafene (G1, G2) og G3 tilfredsstiller ikke betingelse 2.
Siden, grafene (G1, G2) og G3 bryter betingelse 2. Så vi kan si at disse grafene ikke er en isomorfisme.
∴ Graf G3 er verken isomorfisme med graf G1 eller med graf G2.
Siden grafene tilfredsstiller G1 og G2 betingelse 2. Så vi kan si at disse grafene kan være en isomorfisme.
pandas loc
∴ Grafene G1 og G2 kan være en isomorfisme.
Nå skal vi sjekke den tredje betingelsen for grafene G1 og G2.
Tilstand 3:
- I grafen 1 er graden av sekvens s {2, 2, 3, 3}, dvs. G1 = {2, 2, 3, 3}.
- I grafen 2 er graden av sekvens s {2, 2, 3, 3}, dvs. G2 = {2, 2, 3, 3}.
Her
Det er like mange gradsekvenser i begge grafene G1 og G2. Så disse grafene tilfredsstiller betingelse 3. Nå skal vi sjekke den fjerde betingelsen.
Tilstand 4:
Graf G1 danner en syklus med lengde 3 ved hjelp av toppunktene {2, 3, 3}.
Graf G2 danner også en syklus med lengde 3 ved hjelp av toppunktene {2, 3, 3}.
Her,
Den viser at begge grafene inneholder samme syklus fordi begge grafene G1 og G2 danner en syklus med lengde 3 ved hjelp av toppunktene {2, 3, 3}. Så disse grafene tilfredsstiller betingelse 4.
Dermed,
- Grafene G1 og G2 tilfredsstiller alle de fire nødvendige betingelsene ovenfor.
- Så G1 og G2 kan være en isomorfisme.
Nå skal vi sjekke tilstrekkelige forhold til å vise at grafene G1 og G2 er en isomorfisme.
Kontrollere tilstrekkelige betingelser
Som vi har lært at hvis komplementgrafene til begge grafene er isomorfisme, vil de to grafene sikkert være en isomorfisme.
Så vi vil tegne komplementgrafene til G1 og G2, som er beskrevet som følger:
I komplementgrafene ovenfor av G1 og G2 kan vi se at begge grafene er isomorfisme.
∴ Grafene G1 og G2 er isomorfisme.
Eksempel 3:
I dette eksemplet har vi vist om følgende grafer er isomorfisme.
Løsning: For dette vil vi sjekke alle de fire betingelsene for grafisomorfisme, som er beskrevet som følger:
Tilstand 1:
- I graf 1 er det totalt 8 antall hjørner, dvs. G1 = 8.
- I graf 2 er det totalt 8 antall hjørner, dvs. G2 = 8.
Her,
Det er like mange hjørner i begge grafene G1 og G2. Så disse grafene tilfredsstiller betingelse 1. Nå skal vi sjekke den andre betingelsen.
Tilstand 2:
- I graf 1 er det totale antallet kanter 10, dvs. G1 = 10.
- I graf 2 er det totalt antall kanter 10, dvs. G2 = 10.
Her,
Det er like mange kanter i begge grafene G1 og G2. Så disse grafene tilfredsstiller betingelse 2. Nå skal vi sjekke den tredje betingelsen.
java webtjenester
Tilstand 3:
- I grafen 1 er 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 er graden av sekvens s {2, 2, 2, 2, 3, 3, 3, 3}, dvs. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Her
Det er like mange gradsekvenser i begge grafene G1 og G2. Så disse grafene tilfredsstiller betingelse 3. Nå skal vi sjekke den fjerde betingelsen.
Tilstand 4:
- Graf G1 danner en syklus med lengde 4 ved hjelp av grad 3 toppunkter.
- Graf G2 danner ikke en syklus med lengde 4 ved hjelp av toppunkter fordi toppunktene ikke er tilstøtende.
Her,
Både grafene G1 og G2 danner ikke samme syklus med samme lengde. Så disse grafene bryter med betingelse 4.
Siden grafene G1 og G2 bryter med betingelse 4. Så på grunn av bruddet på betingelse 4, vil disse grafene ikke være en isomorfisme.
∴ Grafene G1 og G2 er ikke en isomorfisme.