Isomorfie van grafen – Wikipedia

Posted on by
before-content-x4

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 (d.w.z. 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 isomorfie de richting van de kanten respecteren. Wanneer er een isomorfisme bestaat tussen twee grafen, zijn die isomorf.

after-content-x4

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 elke graaf isomorf is met zichzelf: de identiteitsrelatie is een isomorfie op de graaf. Er kunnen echter ook andere automorfismen bestaan.

Grafenisomorfisme is een equivalentierelatie op grafen en de verzameling van alle grafen wordt erdoor verdeeld in equivalentieklassen.

Als

A1{displaystyle A_{1}}

de bogenmatrix is van graaf G en

A2{displaystyle A_{2}}

de bogenmatrix van graaf H, dan zijn G en H isomorf als en slechts als er een permutatiematrix

P{displaystyle P}

bestaat zodat:

Deze twee grafen zijn isomorf, zoals de kleuring van de knopen illustreert, hoewel ze anders getekend zijn:

Graaf G Graaf H Isomorfisme
tussen G en H
Graph isomorphism a.svg Graph isomorphism b.svg ƒ(a) = 1

ƒ(b) = 6

ƒ(c) = 8

ƒ(d) = 3

ƒ(g) = 5

ƒ(h) = 2

ƒ(i) = 4

ƒ(j) = 7

Deze twee grafen hieronder zijn automorf: we verwisselen 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:

Voorbeeld van twee automorfe grafen

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.

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 “grafenisomorfismeziekte” (The graph isomorphism disease[2]), naar analogie met de term “vierkleurenziekte”, die Frank Harary in 1969 gebruikte voor de zoektocht naar een bewijs van de vierkleurenstelling die vele wiskundigen “besmette”.

Dit is niet louter een theoretisch probleem; grafenisomorfisme komt o.m. aan bod in de scheikunde (voor het bepalen van chemische isomeren met dezelfde molecuulformule maar een andere structuur), Optical character recognition (OCR) of de analyse van sociale netwerken.

Andere isomorfieproblemen zijn database-problemen zoals: vind een isomorfe graaf in een databank van grafen, of: verwijder isomorfe grafen uit de databank; en het grafensorteerprobleem: de grafen in een gegeven verzameling onderverdelen in isomorfismeklassen.

after-content-x4