Isomorfie van grafen
In de grafentheorie wordt met isomorfie van grafen bedoeld dat twee of meer grafen structureel gelijk zijn. Een isomorfisme tussen twee niet-gewogen grafen G en H is een bijectie f tussen de knopenverzamelingen van G en H die een bijectie meebrengt tussen de kanten van G en H: twee knopen u en v in G zijn naburig, dus verbonden door een kant, dan en slechts dan als hun beelden f(u) en f(v) naburig zijn in H. Als G een gerichte graaf is, moet de richting van de kanten voor de isomorfie rekening verschil maken. Wanneer er een isomorfisme bestaat tussen twee grafen, zijn die isomorf.
Grafenisomorfisme is een equivalentierelatie op grafen en de verzameling van alle grafen wordt erdoor verdeeld in equivalentieklassen.
Als de bogenmatrix is van graaf G en de bogenmatrix van graaf H, dan zijn G en H isomorf als en slechts als er een permutatiematrix bestaat zodat:
Als G en H dezelfde graaf zijn, spreekt men over een automorfisme. De verzameling van alle automorfismen van een graaf vormt een automorfismegroep met als groepsbewerking functiecompositie. Merk op dat de structuur van twee isomorfe grafen al dezelfde is en dat elke graaf isomorf is met zichzelf: de identiteitsrelatie is een isomorfie op de graaf, maar er kunnen meer automorfismen bestaan.
Voorbeelden bewerken
Deze twee grafen zijn isomorf, zoals de kleuring van de knopen illustreert, hoewel ze anders zijn getekend:
| Graaf G | Graaf H | Isomorfisme tussen G en H |
|---|---|---|
|
|
ƒ(a) = 1
ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7 |
De twee grafen hieronder zijn automorf: verwissel knoop 1 met 2 en knoop 3 met 4. In de onderste graaf zijn deze knopen met dezelfde knopen verbonden als in de bovenste graaf:
Andere automorfismen van de bovenste graaf zijn (5 6)(7 8) of (1 2)(3 4)(5 6)(7 8) wat men kan beschouwen als een verticale spiegeling van de graaf, of (1 7)(2 8)(3 5)(4 6) wat overeenkomt met een horizontale spiegeling.
Bepalen van isomorfie bewerken
Het probleem: van twee eindige grafen bepalen of ze isomorf zijn, is een computationeel moeilijk probleem waarvoor geen efficiënt algoritme bekend is. De computationele complexiteit van dit probleem is niet eens bekend: het behoort tot de complexiteitsklasse NP maar het is niet bekend of het daarin behoort tot klasse P of dat het NP-volledig is. Voor sommige speciale klassen van grafen zijn wel algoritmen bekend in polynomiale tijd.[1] Het probleem heeft vele grafentheoretici aangetrokken en er zijn honderden algoritmen over gepubliceerd.[1] In een overzichtsartikel uit 1977 hadden Read en Corneil het over de The graph isomorphism disease,[2]) naar analogie met de 'vierkleurenziekte', die Frank Harary in 1969 noemde voor de zoektocht naar een bewijs van de vierkleurenstelling en veel wiskundigen 'besmette'.
Het is niet alleen een theoretisch probleem: grafenisomorfisme komt onder meer in de scheikunde aan bod voor het bepalen van chemische isomeren met dezelfde molecuulformule maar met een andere structuur, optical character recognition of de analyse van sociale netwerken.
Andere isomorfieproblemen zijn database-problemen zoals: vind een isomorfe graaf in een database van grafen, of: verwijder isomorfe grafen uit de database. Daarmee is het grafensorteerprobleem gedefinieerd: de grafen in een verzameling onder te verdelen van onderling isomorfe grafen.
Voetnoten
|