De isomorfismegrafiek kan worden omschreven als een grafiek waarin een enkele grafiek meer dan één vorm kan hebben. Dat betekent dat twee verschillende grafieken hetzelfde aantal randen, hoekpunten en dezelfde randenconnectiviteit kunnen hebben. Dit soort grafieken staan bekend als isomorfismegrafieken. Het voorbeeld van een isomorfismegrafiek wordt als volgt beschreven:
In de bovenstaande grafiek zijn de volgende zaken opgenomen:
- Dezelfde grafiek wordt in meer dan één vorm weergegeven.
- Daarom kunnen we zeggen dat deze grafieken isomorfismegrafieken zijn.
Voorwaarden voor grafiekisomorfisme
Elke twee grafieken worden isomorfisme genoemd als ze aan de volgende vier voorwaarden voldoen:
- Er zullen een gelijk aantal hoekpunten in de gegeven grafieken zijn.
- Er zullen een gelijk aantal randen zijn in de gegeven grafieken.
- Er zal een gelijke hoeveelheid gradenreeks in de gegeven grafieken voorkomen.
- Als de eerste grafiek een cyclus met lengte k vormt met behulp van hoekpunten {v1, v2, v3, …. vk}, dan moet een andere graaf ook dezelfde cyclus van dezelfde lengte k vormen met behulp van hoekpunten {v1, v2, v3, …. vk}.
Opmerking: de gradenreeks van een grafiek kan worden beschreven als een reeks graden van alle hoekpunten in oplopende volgorde.
Belangrijke punten
- Om ervoor te zorgen dat twee grafieken een isomorfisme zijn, zijn de noodzakelijke voorwaarden de hierboven gedefinieerde vier voorwaarden.
- Het is niet nodig dat de hierboven gedefinieerde omstandigheden voldoende zullen zijn om aan te tonen dat de gegeven grafieken isomorf zijn.
- Als twee grafieken aan de hierboven gedefinieerde vier voorwaarden voldoen, is het zelfs dan niet noodzakelijk dat de grafieken zeker isomorf zijn.
- Als de grafiek niet aan alle voorwaarden voldoet, kunnen we zeggen dat de grafieken zeker geen isomorfisme zijn.
Voldoende voorwaarden voor grafiekisomorfisme
Als we willen bewijzen dat twee willekeurige grafieken isomorfisme zijn, zijn er enkele voldoende voorwaarden die we ons zullen bieden om te garanderen dat de twee grafieken zeker isomorfisme zijn. Wanneer de twee grafieken met succes aan alle bovenstaande vier voorwaarden zijn voldaan, zullen we alleen die grafieken controleren op voldoende voorwaarden, die als volgt worden beschreven:
- Als de complementgrafieken van beide grafieken isomorfisme zijn, dan zullen deze grafieken zeker een isomorfisme zijn.
- Als de aangrenzende matrices van beide grafieken hetzelfde zijn, zullen deze grafieken een isomorfisme zijn.
- Als de corresponderende grafieken van twee grafieken worden verkregen met behulp van het verwijderen van enkele hoekpunten van één grafiek, en de overeenkomstige afbeeldingen in andere afbeeldingen isomorfisme zijn, alleen dan zullen deze grafieken geen isomorfisme zijn.
Als twee grafieken aan een van de bovenstaande voorwaarden voldoen, kunnen we zeggen dat die grafieken zeker isomorfisme zijn.
Voorbeelden van grafiekisomorfisme
Er zijn veel voorbeelden van grafiekisomorfisme, die als volgt worden beschreven:
Voorbeeld 1:
In dit voorbeeld hebben we laten zien of de volgende grafieken isomorfisme zijn.
Oplossing: Hiervoor zullen we alle vier voorwaarden van grafiekisomorfisme controleren, die als volgt worden beschreven:
Conditie 1:
git-status
- In grafiek 1 zijn er in totaal 4 hoekpunten, d.w.z. G1 = 4.
- In grafiek 2 zijn er in totaal 4 hoekpunten, d.w.z. G2 = 4.
Hier,
Er zijn een gelijk aantal hoekpunten in beide grafieken G1 en G2. Deze grafieken voldoen dus aan voorwaarde 1. Nu gaan we de tweede voorwaarde controleren.
Conditie 2:
- In grafiek 1 zijn er in totaal 5 randen, d.w.z. G1 = 5.
- In grafiek 2 zijn er in totaal 6 randen, d.w.z. G2 = 6.
Hier,
Er is geen gelijk aantal randen in beide grafieken G1 en G2. Deze grafieken voldoen dus niet aan voorwaarde 2. Nu kunnen we niet alle overige voorwaarden controleren.
Omdat deze grafieken voorwaarde 2 schenden. Deze grafieken zijn dus geen isomorfisme.
∴ Grafiek G1 en grafiek G2 zijn geen isomorfismegrafieken.
Voorbeeld 2:
In dit voorbeeld hebben we laten zien of de volgende grafieken isomorfisme zijn.
Oplossing: Hiervoor zullen we alle vier voorwaarden van grafiekisomorfisme controleren, die als volgt worden beschreven:
Conditie 1:
- In grafiek 1 zijn er in totaal 4 hoekpunten, d.w.z. G1 = 4.
- In grafiek 2 zijn er in totaal 4 hoekpunten, d.w.z. G2 = 4.
- In grafiek 3 zijn er in totaal 4 hoekpunten, d.w.z. G3 = 4.
Hier,
Er zijn een gelijk aantal hoekpunten in alle grafieken G1, G2 en G3. Deze grafieken voldoen dus aan voorwaarde 1. Nu gaan we de tweede voorwaarde controleren.
Conditie 2:
- In grafiek 1 zijn er in totaal 5 randen, d.w.z. G1 = 5.
- In grafiek 2 zijn er in totaal 5 randen, d.w.z. G2 = 5.
- In grafiek 3 zijn er in totaal 4 randen, d.w.z. G2 = 4.
Hier,
- Er zijn een gelijk aantal randen in beide grafieken G1 en G2. Deze grafieken voldoen dus aan voorwaarde 2.
- Maar er zijn niet evenveel randen in de grafieken (G1, G2) als in G3. De grafieken (G1, G2) en G3 voldoen dus niet aan voorwaarde 2.
Omdat de grafieken (G1, G2) en G3 voorwaarde 2 schenden. We kunnen dus zeggen dat deze grafieken geen isomorfisme zijn.
shreya ghoshal
∴ Grafiek G3 is noch isomorfisme met grafiek G1, noch met grafiek G2.
Omdat de grafieken G1 en G2 voldoen aan voorwaarde 2. We kunnen dus zeggen dat deze grafieken een isomorfisme kunnen zijn.
∴ Grafieken G1 en G2 kunnen een isomorfisme zijn.
Nu gaan we de derde voorwaarde voor de grafieken G1 en G2 controleren.
Conditie 3:
- In grafiek 1 is de mate van reeks s {2, 2, 3, 3}, d.w.z. G1 = {2, 2, 3, 3}.
- In grafiek 2 is de mate van reeks s {2, 2, 3, 3}, d.w.z. G2 = {2, 2, 3, 3}.
Hier
Er zijn een gelijk aantal gradenreeksen in beide grafieken G1 en G2. Deze grafieken voldoen dus aan voorwaarde 3. Nu gaan we de vierde voorwaarde controleren.
Voorwaarde 4:
Grafiek G1 vormt een cyclus met lengte 3 met behulp van hoekpunten {2, 3, 3}.
Grafiek G2 vormt ook een cyclus met lengte 3 met behulp van hoekpunten {2, 3, 3}.
Hier,
Het laat zien dat beide grafieken dezelfde cyclus bevatten, omdat beide grafieken G1 en G2 een cyclus met lengte 3 vormen met behulp van hoekpunten {2, 3, 3}. Deze grafieken voldoen dus aan voorwaarde 4.
Dus,
- De grafieken G1 en G2 voldoen aan alle bovengenoemde vier noodzakelijke voorwaarden.
- Dus G1 en G2 kunnen een isomorfisme zijn.
Nu zullen we voldoende omstandigheden controleren om aan te tonen dat de grafieken G1 en G2 een isomorfisme zijn.
lijst versus set in Java
Voldoende omstandigheden controleren
We hebben geleerd dat als de complementaire grafieken van beide grafieken isomorfisme zijn, de twee grafieken zeker een isomorfisme zullen zijn.
We zullen dus de complementgrafieken van G1 en G2 tekenen, die als volgt worden beschreven:
In de bovenstaande complementgrafieken van G1 en G2 kunnen we zien dat beide grafieken isomorfisme zijn.
∴ Grafieken G1 en G2 zijn isomorfisme.
Voorbeeld 3:
In dit voorbeeld hebben we laten zien of de volgende grafieken isomorfisme zijn.
Oplossing: Hiervoor zullen we alle vier voorwaarden van grafiekisomorfisme controleren, die als volgt worden beschreven:
Conditie 1:
- In grafiek 1 zijn er in totaal 8 hoekpunten, d.w.z. G1 = 8.
- In grafiek 2 zijn er in totaal 8 hoekpunten, d.w.z. G2 = 8.
Hier,
Er zijn een gelijk aantal hoekpunten in beide grafieken G1 en G2. Deze grafieken voldoen dus aan voorwaarde 1. Nu gaan we de tweede voorwaarde controleren.
Conditie 2:
- In grafiek 1 is het totale aantal randen 10, d.w.z. G1 = 10.
- In grafiek 2 is het totale aantal randen 10, d.w.z. G2 = 10.
Hier,
Er zijn een gelijk aantal randen in beide grafieken G1 en G2. Deze grafieken voldoen dus aan voorwaarde 2. Nu gaan we de derde voorwaarde controleren.
Conditie 3:
Java-stapel
- In grafiek 1 is de mate van reeks s {2, 2, 2, 2, 3, 3, 3, 3}, d.w.z. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- In grafiek 2 is de mate van reeks s {2, 2, 2, 2, 3, 3, 3, 3}, d.w.z. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Hier
Er zijn een gelijk aantal gradenreeksen in beide grafieken G1 en G2. Deze grafieken voldoen dus aan voorwaarde 3. Nu gaan we de vierde voorwaarde controleren.
Voorwaarde 4:
- Grafiek G1 vormt een cyclus met lengte 4 met behulp van hoekpunten van graad 3.
- Grafiek G2 vormt geen cyclus met lengte 4 met behulp van hoekpunten, omdat de hoekpunten niet aangrenzend zijn.
Hier,
Zowel de grafieken G1 als G2 vormen niet dezelfde cyclus met dezelfde lengte. Deze grafieken zijn dus in strijd met voorwaarde 4.
Omdat de grafieken G1 en G2 voorwaarde 4 schenden. Vanwege de schending van voorwaarde 4 zullen deze grafieken dus geen isomorfisme zijn.
∴ Grafieken G1 en G2 zijn geen isomorfisme.