Graficul izomorfismului poate fi descris ca un grafic în care un singur grafic poate avea mai multe forme. Asta înseamnă că două grafice diferite pot avea același număr de muchii, vârfuri și conectivitate cu aceleași muchii. Aceste tipuri de grafice sunt cunoscute sub denumirea de grafice de izomorfism. Exemplul unui grafic de izomorfism este descris după cum urmează:
Graficul de mai sus conține următoarele lucruri:
- Același grafic este reprezentat în mai multe forme.
- Prin urmare, putem spune că aceste grafice sunt grafice de izomorfism.
Condiții pentru izomorfismul graficului
Oricare două grafice vor fi cunoscute ca izomorfism dacă îndeplinesc următoarele patru condiții:
- Va exista un număr egal de vârfuri în graficele date.
- Va exista un număr egal de muchii în graficele date.
- Va exista o cantitate egală de secvență de grade în graficele date.
- Dacă primul grafic formează un ciclu de lungime k cu ajutorul vârfurilor {v1, v2, v3, …. vk}, atunci un alt grafic trebuie să formeze și el același ciclu de aceeași lungime k cu ajutorul vârfurilor {v1, v2, v3, …. vk}.
Notă: Secvența de grade a unui grafic poate fi descrisă ca o secvență de grade a tuturor nodurilor în ordine crescătoare.
Puncte importante
- Pentru ca oricare două grafice să fie izomorfism, condițiile necesare sunt cele patru condiții definite mai sus.
- Nu este necesar ca condițiile definite mai sus să fie suficiente pentru a arăta că graficele date sunt izomorfe.
- Dacă două grafice îndeplinesc cele patru condiții definite mai sus, chiar și atunci, nu este necesar ca graficele să aibă cu siguranță izomorfism.
- Dacă graficul nu îndeplinește nicio condiție, atunci putem spune că graficele nu sunt cu siguranță un izomorfism.
Condiții suficiente pentru izomorfismul graficului
Dacă vrem să demonstrăm că oricare două grafuri sunt izomorfism, există câteva condiții suficiente pe care ni le vom oferi garantând că cele două grafuri sunt cu siguranță izomorfism. Când cele două grafice sunt șters cu succes toate cele patru condiții de mai sus, numai atunci vom verifica acele grafice în condiții suficiente, care sunt descrise după cum urmează:
- Dacă graficele complement ale ambelor grafice sunt izomorfism, atunci aceste grafice vor fi cu siguranță un izomorfism.
- Dacă matricele adiacente ale ambelor grafice sunt aceleași, atunci aceste grafice vor fi un izomorfism.
- Dacă graficele corespunzătoare a două grafice sunt obținute cu ajutorul ștergerii unor vârfuri ale unui grafic, iar imaginile lor corespunzătoare din alte imagini sunt izomorfism, numai atunci aceste grafice nu vor fi un izomorfism.
Când două grafice îndeplinesc oricare dintre condițiile de mai sus, atunci putem spune că acele grafice sunt cu siguranță izomorfism.
Exemple de izomorfism grafic
Există o mulțime de exemple de izomorfism grafic, care sunt descrise după cum urmează:
Exemplul 1:
În acest exemplu, am arătat dacă următoarele grafice sunt izomorfism.
Soluţie: Pentru aceasta, vom verifica toate cele patru condiții ale izomorfismului grafic, care sunt descrise după cum urmează:
Condiția 1:
- În graficul 1, există un număr total de 4 vârfuri, adică G1 = 4.
- În graficul 2, există un număr total de 4 vârfuri, adică G2 = 4.
Aici,
Există un număr egal de vârfuri în ambele grafice G1 și G2. Deci aceste grafice satisfac condiția 1. Acum vom verifica a doua condiție.
Condiția 2:
- În graficul 1, există un număr total de 5 muchii, adică G1 = 5.
- În graficul 2, există un număr total de 6 muchii, adică G2 = 6.
Aici,
Nu există un număr egal de muchii în ambele grafice G1 și G2. Deci aceste grafice nu satisfac condiția 2. Acum nu putem verifica toate condițiile rămase.
Deoarece, aceste grafice încalcă condiția 2. Deci aceste grafice nu sunt un izomorfism.
∴ Graficul G1 și graficul G2 nu sunt grafice de izomorfism.
Exemplul 2:
În acest exemplu, am arătat dacă următoarele grafice sunt izomorfism.
Soluţie: Pentru aceasta, vom verifica toate cele patru condiții ale izomorfismului grafic, care sunt descrise după cum urmează:
Condiția 1:
- În graficul 1, există un număr total de 4 vârfuri, adică G1 = 4.
- În graficul 2, există un număr total de 4 vârfuri, adică G2 = 4.
- În graficul 3, există un număr total de 4 vârfuri, adică G3 = 4.
Aici,
Există un număr egal de vârfuri în toate graficele G1, G2 și G3. Deci aceste grafice satisfac condiția 1. Acum vom verifica a doua condiție.
Condiția 2:
- În graficul 1, există un număr total de 5 muchii, adică G1 = 5.
- În graficul 2, există un număr total de 5 muchii, adică G2 = 5.
- În graficul 3, există un număr total de 4 muchii, adică G2 = 4.
Aici,
- Există un număr egal de muchii în ambele grafice G1 și G2. Deci aceste grafice satisfac condiția 2.
- Dar nu există un număr egal de muchii în graficele (G1, G2) și G3. Deci graficele (G1, G2) și G3 nu îndeplinesc condiția 2.
Deoarece, graficele (G1, G2) și G3 încalcă condiția 2. Deci putem spune că aceste grafice nu sunt un izomorfism.
∴ Graficul G3 nu este nici izomorfism cu graficul G1, nici cu graficul G2.
Deoarece graficele, G1 și G2 îndeplinesc condiția 2. Deci putem spune că aceste grafice pot fi un izomorfism.
∴ Graficele G1 și G2 pot fi un izomorfism.
Acum vom verifica a treia condiție pentru graficele G1 și G2.
Condiția 3:
- În graficul 1, gradul secvenței s este {2, 2, 3, 3}, adică G1 = {2, 2, 3, 3}.
- În graficul 2, gradul secvenței s este {2, 2, 3, 3}, adică G2 = {2, 2, 3, 3}.
Aici
Există un număr egal de secvențe de grade în ambele grafice G1 și G2. Deci aceste grafice satisfac condiția 3. Acum vom verifica a patra condiție.
Condiția 4:
Graficul G1 formează un ciclu de lungime 3 cu ajutorul vârfurilor {2, 3, 3}.
Graficul G2 formează și un ciclu de lungime 3 cu ajutorul vârfurilor {2, 3, 3}.
Aici,
Arată că ambele grafice conțin același ciclu deoarece ambele grafice G1 și G2 formează un ciclu de lungime 3 cu ajutorul vârfurilor {2, 3, 3}. Deci aceste grafice satisfac condiția 4.
structură de date
Prin urmare,
- Graficele G1 și G2 îndeplinesc toate cele patru condiții necesare de mai sus.
- Deci G1 și G2 pot fi un izomorfism.
Acum vom verifica condiții suficiente pentru a arăta că graficele G1 și G2 sunt un izomorfism.
Verificarea condițiilor suficiente
După cum am aflat că, dacă graficele complement ale ambelor grafice sunt izomorfism, cele două grafice vor fi cu siguranță un izomorfism.
Deci vom desena graficele complementului G1 și G2, care sunt descrise după cum urmează:
În graficele complementare de mai sus ale G1 și G2, putem vedea că ambele grafice sunt izomorfism.
∴ Graficele G1 și G2 sunt izomorfisme.
Exemplul 3:
În acest exemplu, am arătat dacă următoarele grafice sunt izomorfism.
Soluţie: Pentru aceasta, vom verifica toate cele patru condiții ale izomorfismului grafic, care sunt descrise după cum urmează:
Condiția 1:
- În graficul 1, există un număr total de 8 vârfuri, adică G1 = 8.
- În graficul 2, există un număr total de 8 vârfuri, adică G2 = 8.
Aici,
Există un număr egal de vârfuri în ambele grafice G1 și G2. Deci aceste grafice satisfac condiția 1. Acum vom verifica a doua condiție.
Condiția 2:
- În graficul 1, există numărul total de muchii este 10, adică G1 = 10.
- În graficul 2, numărul total de muchii este 10, adică G2 = 10.
Aici,
Există un număr egal de muchii în ambele grafice G1 și G2. Deci aceste grafice satisfac condiția 2. Acum vom verifica a treia condiție.
Condiția 3:
- În graficul 1, gradul secvenței s este {2, 2, 2, 2, 3, 3, 3, 3}, adică G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- În graficul 2, gradul secvenței s este {2, 2, 2, 2, 3, 3, 3, 3}, adică G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Aici
Există un număr egal de secvențe de grade în ambele grafice G1 și G2. Deci aceste grafice satisfac condiția 3. Acum vom verifica a patra condiție.
Condiția 4:
- Graficul G1 formează un ciclu de lungime 4 cu ajutorul vârfurilor de gradul 3.
- Graficul G2 nu formează un ciclu de lungime 4 cu ajutorul vârfurilor, deoarece vârfurile nu sunt adiacente.
Aici,
Ambele grafice G1 și G2 nu formează același ciclu cu aceeași lungime. Deci aceste grafice încalcă condiția 4.
Deoarece, graficele G1 și G2 încalcă condiția 4. Deci, din cauza încălcării condiției 4, aceste grafice nu vor fi un izomorfism.
∴ Graficele G1 și G2 nu sunt un izomorfism.