Isomorfismigraafia voidaan kuvata graafina, jossa yhdellä graafilla voi olla useampi kuin yksi muoto. Tämä tarkoittaa, että kahdella eri graafilla voi olla sama määrä reunoja, pisteitä ja samat reunayhteydet. Tämän tyyppiset graafit tunnetaan isomorfismikaavioina. Esimerkki isomorfismigraafista on kuvattu seuraavasti:
Yllä oleva kaavio sisältää seuraavat asiat:
- Sama kaavio esitetään useammassa kuin yhdessä muodossa.
- Tästä syystä voimme sanoa, että nämä graafit ovat isomorfismikaavioita.
Graafisen isomorfismin ehdot
Mitä tahansa kahta kuvaajaa kutsutaan isomorfismiksi, jos ne täyttävät seuraavat neljä ehtoa:
- Annetuissa kaavioissa on yhtä paljon pisteitä.
- Annetuissa kaavioissa on yhtä monta reunaa.
- Annetuissa kaavioissa on yhtä paljon astesekvenssiä.
- Jos ensimmäinen graafi muodostaa k-pituisen syklin kärkien {v1, v2, v3, … avulla. vk}, silloin myös toisen graafin tulee muodostaa sama samanpituinen k sykli kärkien {v1, v2, v3, … avulla. vk}.
Huomaa: Graafin astesekvenssiä voidaan kuvata kaikkien kärkien astesekvenssinä nousevassa järjestyksessä.
Tärkeitä kohtia
- Jotta mitkä tahansa kaksi kuvaaja olisi isomorfismi, vaadittavat ehdot ovat edellä määritellyt neljä ehtoa.
- Ei ole välttämätöntä, että edellä määritellyt ehdot ovat riittäviä osoittamaan, että annetut graafit ovat isomorfisia.
- Jos kaksi kuvaajaa täyttää edellä määritellyt neljä ehtoa, silloinkaan ei ole välttämätöntä, että graafit ovat varmasti isomorfisia.
- Jos graafi ei täytä mitään ehtoja, voimme sanoa, että graafit eivät varmasti ole isomorfia.
Riittävät edellytykset graafisen isomorfismille
Jos haluamme todistaa, että mitkä tahansa kaksi kuvaajaa ovat isomorfia, on olemassa joitain riittäviä ehtoja, joiden avulla voimme taata, että nämä kaksi graafia ovat varmasti isomorfisia. Kun nämä kaksi kuvaajaa on onnistuneesti tyhjennetty kaikki edellä mainitut neljä ehtoa, vasta sitten tarkistamme nämä kaaviot riittäviin ehtoihin, jotka kuvataan seuraavasti:
- Jos molempien graafien komplementtigraafit ovat isomorfisia, niin nämä graafit ovat varmasti isomorfia.
- Jos molempien graafien vierekkäiset matriisit ovat samat, nämä graafit ovat isomorfismi.
- Jos kahden graafin vastaavat graafit saadaan poistamalla yhden graafin joitain pisteitä ja niitä vastaavat kuvat muissa kuvissa ovat isomorfisia, vain silloin nämä graafit eivät ole isomorfismia.
Kun kaksi kuvaajaa täyttää jonkin yllä olevista ehdoista, voimme sanoa, että nuo graafit ovat varmasti isomorfisia.
Esimerkkejä graafisen isomorfismista
Graafin isomorfismista on paljon esimerkkejä, jotka kuvataan seuraavasti:
Esimerkki 1:
Tässä esimerkissä olemme osoittaneet, ovatko seuraavat graafit isomorfia.
Ratkaisu: Tätä varten tarkistamme kaikki neljä graafin isomorfismin ehtoa, jotka kuvataan seuraavasti:
Ehto 1:
- Graafissa 1 on yhteensä 4 pisteitä, eli G1 = 4.
- Graafissa 2 on yhteensä 4 pisteitä, eli G2 = 4.
Tässä,
tostring java -menetelmä
Kummassakin graafissa G1 ja G2 on yhtä paljon pisteitä. Joten nämä kaaviot täyttävät ehdon 1. Nyt tarkastetaan toinen ehto.
Ehto 2:
- Kaaviossa 1 on yhteensä 5 reunoja, eli G1 = 5.
- Kaaviossa 2 on yhteensä 6 reunoja, eli G2 = 6.
Tässä,
Kummassakin graafissa G1 ja G2 ei ole yhtä monta reunaa. Nämä kaaviot eivät siis täytä ehtoa 2. Nyt emme voi tarkistaa kaikkia jäljellä olevia ehtoja.
Koska nämä graafit rikkovat ehtoa 2. Nämä graafit eivät siis ole isomorfismi.
∴ Graafi G1 ja graafi G2 eivät ole isomorfismigraafia.
Esimerkki 2:
Tässä esimerkissä olemme osoittaneet, ovatko seuraavat graafit isomorfia.
Ratkaisu: Tätä varten tarkistamme kaikki neljä graafin isomorfismin ehtoa, jotka kuvataan seuraavasti:
Ehto 1:
lajittele taulukkoluettelo
- Graafissa 1 on yhteensä 4 pisteitä, eli G1 = 4.
- Graafissa 2 on yhteensä 4 pisteitä, eli G2 = 4.
- Graafissa 3 on yhteensä 4 pisteitä, eli G3 = 4.
Tässä,
Kaikissa grafiikoissa G1, G2 ja G3 on yhtä paljon pisteitä. Joten nämä kaaviot täyttävät ehdon 1. Nyt tarkastetaan toinen ehto.
Ehto 2:
- Kaaviossa 1 on yhteensä 5 reunoja, eli G1 = 5.
- Kaaviossa 2 on yhteensä 5 reunoja, eli G2 = 5.
- Kaaviossa 3 on yhteensä 4 reunaa, eli G2 = 4.
Tässä,
- Kummassakin graafissa G1 ja G2 on yhtä monta reunaa. Joten nämä kaaviot täyttävät ehdon 2.
- Mutta graafissa (G1, G2) ja G3:ssa ei ole yhtä monta reunaa. Joten kuvaajat (G1, G2) ja G3 eivät täytä ehtoa 2.
Koska graafit (G1, G2) ja G3 rikkovat ehtoa 2. Voimme siis sanoa, että nämä graafit eivät ole isomorfismi.
powershell pienempi tai yhtä suuri kuin
∴ Graafi G3 ei ole isomorfismi graafin G1 eikä graafin G2 kanssa.
Koska graafit G1 ja G2 täyttävät ehdon 2. Voimme siis sanoa, että nämä graafit voivat olla isomorfia.
∴ Kaaviot G1 ja G2 voivat olla isomorfia.
Nyt tarkastetaan kolmas ehto kaavioille G1 ja G2.
Ehto 3:
- Kaaviossa 1 sekvenssin s aste on {2, 2, 3, 3}, eli G1 = {2, 2, 3, 3}.
- Kaaviossa 2 sekvenssin s aste on {2, 2, 3, 3}, eli G2 = {2, 2, 3, 3}.
Tässä
Kummassakin graafissa G1 ja G2 on yhtä monta astejonoa. Joten nämä kaaviot täyttävät ehdon 3. Nyt tarkastetaan neljäs ehto.
Ehto 4:
Graafi G1 muodostaa syklin, jonka pituus on 3, kärkien {2, 3, 3} avulla.
Graafi G2 muodostaa myös syklin, jonka pituus on 3, kärkien {2, 3, 3} avulla.
Tässä,
Se osoittaa, että molemmat graafit sisältävät saman syklin, koska molemmat graafit G1 ja G2 muodostavat syklin, jonka pituus on 3, kärkien {2, 3, 3} avulla. Joten nämä kaaviot täyttävät ehdon 4.
Täten,
- Kaaviot G1 ja G2 täyttävät kaikki edellä mainitut neljä tarpeellista ehtoa.
- Joten G1 ja G2 voivat olla isomorfismi.
Nyt tarkastetaan riittävät ehdot osoittamaan, että kuvaajat G1 ja G2 ovat isomorfia.
Riittävien olosuhteiden tarkistaminen
miten java päivitetään
Kuten olemme oppineet, että jos molempien graafien komplementtikuvaajat ovat isomorfisia, nämä kaksi kuvaajaa ovat varmasti isomorfia.
Joten piirretään G1:n ja G2:n komplementtikuvaajat, jotka kuvataan seuraavasti:
Yllä olevissa G1:n ja G2:n komplementtikaavioissa voimme nähdä, että molemmat graafit ovat isomorfisia.
∴ Kuvaajat G1 ja G2 ovat isomorfisia.
Esimerkki 3:
Tässä esimerkissä olemme osoittaneet, ovatko seuraavat graafit isomorfia.
Ratkaisu: Tätä varten tarkistamme kaikki neljä graafin isomorfismin ehtoa, jotka kuvataan seuraavasti:
Ehto 1:
- Kaaviossa 1 on yhteensä 8 pisteitä, eli G1 = 8.
- Graafissa 2 on yhteensä 8 pisteitä, eli G2 = 8.
Tässä,
Kummassakin graafissa G1 ja G2 on yhtä paljon pisteitä. Joten nämä kaaviot täyttävät ehdon 1. Nyt tarkastetaan toinen ehto.
Ehto 2:
- Kaaviossa 1 reunojen kokonaismäärä on 10, eli G1 = 10.
- Kaaviossa 2 reunojen kokonaismäärä on 10, eli G2 = 10.
Tässä,
Kummassakin graafissa G1 ja G2 on yhtä monta reunaa. Joten nämä kaaviot täyttävät ehdon 2. Nyt tarkastetaan kolmas ehto.
Ehto 3:
- Kaaviossa 1 sekvenssin s aste on {2, 2, 2, 2, 3, 3, 3, 3}, eli G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- Kaaviossa 2 sekvenssin s aste on {2, 2, 2, 2, 3, 3, 3, 3}, eli G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Tässä
Kummassakin graafissa G1 ja G2 on yhtä monta astejonoa. Joten nämä kaaviot täyttävät ehdon 3. Nyt tarkastetaan neljäs ehto.
Ehto 4:
monisäikeinen java
- Graafi G1 muodostaa syklin, jonka pituus on 4, asteen 3 kärkien avulla.
- Graafi G2 ei muodosta 4:n pituista sykliä pisteiden avulla, koska kärjet eivät ole vierekkäisiä.
Tässä,
Sekä kuvaajat G1 että G2 eivät muodosta samaa sykliä, jolla on sama pituus. Joten nämä kaaviot rikkovat ehtoa 4.
Koska kaaviot G1 ja G2 rikkovat ehtoa 4. Ehdon 4 rikkomisen vuoksi nämä kaaviot eivät ole isomorfismi.
∴ Kuvaajat G1 ja G2 eivät ole isomorfismi.