Subgraaf isomorfisme probleem

In de theoretische informatica, de subgraaf isomorfisme probleem is een computationele taak waarin twee grafieken G en H worden gegeven als input, en men moet bepalen of G bevat een subgraaf die isomorf is met H. subgraaf isomorfisme is een veralgemening van zowel de maximale kliek probleem en het probleem van testen of een grafiek bevat Hamilton cyclus en derhalve NP-compleet. Maar sommige andere gevallen van subgraaf isomorfie kan worden opgelost in polynomiale tijd.

Soms wordt de naam subgraaf matching wordt ook gebruikt voor hetzelfde probleem. Deze naam legt de nadruk op het vinden van dergelijke subgraaf in tegenstelling tot het strikte beslissingsprobleem.

Besluit probleem en computationele complexiteit

Om subgraaf isomorfisme te bewijzen is NP-compleet is, het moet worden geformuleerd als een beslissing probleem. De input voor de beslissing probleem is een paar grafieken G en H. Het antwoord op het probleem is positief als H isomorf is met een subgraaf van G, en negatieve anders.

Formele vraag:

Laat, zijn grafieken. Is er een subgraaf zodanig dat? Dat wil zeggen, Bestaat er een zodanig dat?

Het bewijs van subgraaf isomorfie zijn NP-compleet is eenvoudig en gebaseerd op vermindering van de kliek probleem, een NP-compleet beslissing probleem waar de ingang is een enkele grafiek G en een aantal k, en de vraag is of G bevat een complete subgraaf k hoekpunten. Om dit te vertalen naar een subgraaf isomorfisme probleem, gewoon laten H zijn de complete grafiek Kk; dan is het antwoord op de subgraaf isomorfisme probleem voor G en H is gelijk aan het antwoord op de kliek probleem voor G en K. Omdat de kliek probleem is NP-compleet, deze polynomiale-tijd veel-een vermindering laat zien dat subgraaf isomorfisme is NP-compleet.

Een alternatieve reductie van de Hamiltoniaan cyclus probleem vertaalt een grafiek G die moet worden getest Hamiltonicity in het paar grafieken G en H, waarbij H een cyclus met hetzelfde aantal hoekpunten als G. Aangezien de Hamiltoniaan cyclus probleem NP volledige zelfs voor vlakke grafieken, toont dit aan dat subgraaf isomorfie blijft NP-compleet, zelfs in de vlakke geval.

Subgraaf isomorfisme is een generalisatie van de grafiek isomorfie probleem, dat vraagt ​​of G isomorf is met H: het antwoord op de grafiek isomorfisme probleem is waar als en slechts als G en H hebben allebei hetzelfde aantal hoekpunten en randen en de subgraaf isomorfie probleem G en H klopt. De complexiteit-theoretische status van de grafiek isomorfie blijft echter een open vraag.

In het kader van de Aanderaa-Karp-Rosenberg gissingen op de query complexiteit van monotone grafiek eigenschappen, Gröger bleek dat elke subgraaf isomorfie probleem heeft vraag complexiteit Ω; dat wil zeggen het oplossen van de subgraaf isomorfisme vereist een algoritme om de aanwezigheid of afwezigheid controleren op de ingang van Ω verschillende hoeken in de grafiek.

Algoritmen

Ullmann beschrijft een recursieve backtracking procedure voor het oplossen van de subgraaf isomorfie probleem. Hoewel de looptijd is in het algemeen exponentiële duurt polynomiale tijd op elke vaste keuze H. Wanneer G een vlak grafiek en H wordt vastgesteld, bedraagt ​​subgraaf isomorfisme kan worden verminderd tot lineaire tijd.

Toepassingen

Zoals subgraaf isomorfisme is toegepast op het gebied van cheminformatica gelijkenissen tussen chemische verbindingen uit hun structuurformule vinden; vaak in dit gebied de term onderbouw zoekactie gebruikt. Typisch een query structuur wordt gedefinieerd als SMARTS, een SMILES extensie.

Het nauw verwant probleem van het tellen van het aantal isomorf exemplaren van een grafiek H in groter graaf G werd toegepast op patroonvorsingsalgoritmen in databases, de bioinformatica van eiwit-eiwit interacties netwerken en exponentiële willekeurige grafiek werkwijzen voor het mathematisch modelleren social networks.

Ohlrich et al. beschrijven een toepassing van subgraaf isomorfisme in de computer-aided design van elektronische schakelingen. Subgraaf matching is ook een substap in grafiek herschrijven, en dus worden aangeboden door grafiek herschrijven gereedschappen.

Het probleem is ook van belang in de kunstmatige intelligentie, waar het beschouwd als onderdeel van een reeks van patroonherkenning in grafieken problemen; verlenging van subgraaf isomorfisme zogenaamde graph mining is ook interessant in dit gebied.

(0)
(0)
Commentaren - 0
Geen commentaar

Voeg een reactie

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha