Isomorfigrafen kan beskrives som en graf, hvor en enkelt graf kan have mere end én form. Det betyder, at to forskellige grafer kan have det samme antal kanter, hjørner og samme kanter-forbindelse. Disse typer grafer er kendt som isomorfi-grafer. Eksemplet på en isomorfismegraf er beskrevet som følger:
Ovenstående graf indeholder følgende ting:
- Den samme graf er repræsenteret i mere end én form.
- Derfor kan vi sige, at disse grafer er isomorfigrafer.
Betingelser for grafisomorfi
Enhver to grafer vil blive kendt som isomorfi, hvis de opfylder følgende fire betingelser:
- Der vil være lige mange hjørner i de givne grafer.
- Der vil være lige mange kanter i de givne grafer.
- Der vil være en lige stor grad af sekvens i de givne grafer.
- Hvis den første graf danner en cyklus med længden k ved hjælp af toppunkter {v1, v2, v3, …. vk}, så skal en anden graf også danne den samme cyklus af samme længde k ved hjælp af hjørner {v1, v2, v3, …. vk}.
Bemærk: Gradsekvensen af en graf kan beskrives som en sekvens af grad af alle hjørnerne i stigende rækkefølge.
Vigtige pointer
- For at to grafer skal være en isomorfi, er de nødvendige betingelser de ovenfor definerede fire betingelser.
- Det er ikke nødvendigt, at de ovenfor definerede betingelser vil være tilstrækkelige til at vise, at de givne grafer er isomorfe.
- Hvis to grafer opfylder de ovenfor definerede fire betingelser, selv da, er det ikke nødvendigt, at graferne helt sikkert vil isomorfi.
- Hvis grafen ikke opfylder nogen betingelser, kan vi sige, at graferne bestemt ikke er en isomorfi.
Tilstrækkelige betingelser for grafisk isomorfi
Hvis vi ønsker at bevise, at to grafer er isomorfi, er der nogle tilstrækkelige betingelser, som vi vil give os garanti for, at de to grafer helt sikkert er isomorfi. Når de to grafer er blevet ryddet alle de ovenstående fire betingelser, vil vi først kontrollere disse grafer til tilstrækkelige betingelser, som er beskrevet som følger:
- Hvis komplementgraferne til begge grafer er isomorfi, så vil disse grafer helt sikkert være en isomorfi.
- Hvis de tilstødende matricer af begge grafer er de samme, vil disse grafer være en isomorfi.
- Hvis de tilsvarende grafer af to grafer opnås ved hjælp af at slette nogle hjørner af en graf, og deres tilsvarende billeder i andre billeder er isomorfi, vil disse grafer kun være en isomorfi.
Når to grafer opfylder nogen af ovenstående betingelser, kan vi sige, at disse grafer helt sikkert er isomorfi.
Eksempler på grafisomorfi
Der er en masse eksempler på grafisomorfi, som er beskrevet som følger:
Eksempel 1:
I dette eksempel har vi vist, om følgende grafer er isomorfi.
Løsning: Til dette vil vi kontrollere alle de fire betingelser for grafisomorfi, som er beskrevet som følger:
Betingelse 1:
- I graf 1 er der i alt 4 antal hjørner, dvs. G1 = 4.
- I graf 2 er der i alt 4 antal hjørner, dvs. G2 = 4.
Her,
Der er lige mange hjørner i begge grafer G1 og G2. Så disse grafer opfylder betingelse 1. Nu vil vi kontrollere den anden betingelse.
Tilstand 2:
- I graf 1 er der i alt 5 antal kanter, dvs. G1 = 5.
- I graf 2 er der i alt 6 antal kanter, dvs. G2 = 6.
Her,
Der er ikke lige mange kanter i begge grafer G1 og G2. Så disse grafer opfylder ikke betingelse 2. Nu kan vi ikke kontrollere alle de resterende betingelser.
Da disse grafer overtræder betingelse 2. Så disse grafer er ikke en isomorfi.
∴ Graf G1 og graf G2 er ikke isomorfigrafer.
Eksempel 2:
I dette eksempel har vi vist, om følgende grafer er isomorfi.
Løsning: Til dette vil vi kontrollere alle de fire betingelser for grafisomorfi, som er beskrevet som følger:
Betingelse 1:
- I graf 1 er der i alt 4 antal hjørner, dvs. G1 = 4.
- I graf 2 er der i alt 4 antal hjørner, dvs. G2 = 4.
- I graf 3 er der i alt 4 antal hjørner, dvs. G3 = 4.
Her,
Der er lige mange hjørner i alle grafer G1, G2 og G3. Så disse grafer opfylder betingelse 1. Nu vil vi kontrollere den anden betingelse.
Tilstand 2:
- I graf 1 er der i alt 5 antal kanter, dvs. G1 = 5.
- I graf 2 er der i alt 5 antal kanter, dvs. G2 = 5.
- I graf 3 er der i alt 4 antal kanter, dvs. G2 = 4.
Her,
- Der er lige mange kanter i begge grafer G1 og G2. Så disse grafer opfylder betingelse 2.
- Men der er ikke lige mange kanter i graferne (G1, G2) og G3. Så graferne (G1, G2) og G3 opfylder ikke betingelse 2.
Da graferne (G1, G2) og G3 overtræder betingelse 2. Så vi kan sige, at disse grafer ikke er en isomorfi.
∴ Graf G3 er hverken isomorfi med graf G1 eller med graf G2.
Da graferne opfylder G1 og G2 betingelse 2. Så vi kan sige, at disse grafer kan være en isomorfi.
pandas loc
∴ Graferne G1 og G2 kan være en isomorfi.
Nu vil vi kontrollere den tredje betingelse for graferne G1 og G2.
Tilstand 3:
- I grafen 1 er graden af sekvens s {2, 2, 3, 3}, dvs. G1 = {2, 2, 3, 3}.
- I grafen 2 er graden af sekvens s {2, 2, 3, 3}, dvs. G2 = {2, 2, 3, 3}.
Her
Der er lige mange gradsekvenser i både graferne G1 og G2. Så disse grafer opfylder betingelse 3. Nu vil vi kontrollere den fjerde betingelse.
Tilstand 4:
Graf G1 danner en cyklus med længde 3 ved hjælp af hjørner {2, 3, 3}.
Graf G2 danner også en cyklus med længde 3 ved hjælp af toppunkter {2, 3, 3}.
Her,
Det viser, at begge grafer indeholder den samme cyklus, fordi begge grafer G1 og G2 danner en cyklus med længde 3 ved hjælp af toppunkter {2, 3, 3}. Så disse grafer opfylder betingelse 4.
Dermed,
- Graferne G1 og G2 opfylder alle ovenstående fire nødvendige betingelser.
- Så G1 og G2 kan være en isomorfi.
Nu vil vi kontrollere tilstrækkelige betingelser til at vise, at graferne G1 og G2 er en isomorfi.
Kontrol af tilstrækkelige betingelser
Som vi har lært, at hvis komplementgraferne til begge grafer er isomorfi, vil de to grafer helt sikkert være en isomorfi.
Så vi vil tegne komplementgraferne for G1 og G2, som er beskrevet som følger:
I ovenstående komplementgrafer af G1 og G2 kan vi se, at begge grafer er isomorfi.
∴ Graferne G1 og G2 er isomorfi.
Eksempel 3:
I dette eksempel har vi vist, om følgende grafer er isomorfi.
Løsning: Til dette vil vi kontrollere alle de fire betingelser for grafisomorfi, som er beskrevet som følger:
Betingelse 1:
- I graf 1 er der i alt 8 antal hjørner, dvs. G1 = 8.
- I graf 2 er der i alt 8 antal hjørner, dvs. G2 = 8.
Her,
Der er lige mange hjørner i begge grafer G1 og G2. Så disse grafer opfylder betingelse 1. Nu vil vi kontrollere den anden betingelse.
Tilstand 2:
- I graf 1 er det samlede antal kanter 10, dvs. G1 = 10.
- I graf 2 er det samlede antal kanter 10, dvs. G2 = 10.
Her,
Der er lige mange kanter i begge grafer G1 og G2. Så disse grafer opfylder betingelse 2. Nu vil vi kontrollere den tredje betingelse.
fordele og ulemper ved teknologi
Tilstand 3:
- I grafen 1 er graden af 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 af sekvens s {2, 2, 2, 2, 3, 3, 3, 3}, dvs. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Her
Der er lige mange gradsekvenser i både graferne G1 og G2. Så disse grafer opfylder betingelse 3. Nu vil vi kontrollere den fjerde betingelse.
Tilstand 4:
- Graf G1 danner en cyklus af længde 4 ved hjælp af grad 3 hjørner.
- Graf G2 danner ikke en cyklus med længde 4 ved hjælp af toppunkter, fordi toppunkter ikke støder op til hinanden.
Her,
Både graferne G1 og G2 danner ikke den samme cyklus med samme længde. Så disse grafer overtræder betingelse 4.
Da graferne G1 og G2 overtræder betingelse 4. Så på grund af overtrædelsen af betingelse 4, vil disse grafer ikke være en isomorfi.
∴ Graferne G1 og G2 er ikke en isomorfi.