I matematikk , og spesielt i grafteori , er et artikulasjonspunkt et toppunkt for en ikke-rettet graf som, hvis den fjernes fra grafen, øker antall tilkoblede komponenter . Hvis grafen ble koblet til før du fjernet dette toppunktet, blir den derfor ikke-koblet.
En graf sies å være koblet til hvis den ikke inneholder artikulasjonspunkter. En graf som inneholder artikulasjonspunkter kan spaltes i to koblede komponenter ved å multiplisere artikulasjonspunktene. Dette tilsvarer å si at to kanter på en tokoblet komponent tilhører en syklus.
I et tre , alle punktene av grad strengt større enn 1 er interessante artikulasjon.
Forestillingen som tilsvarer artikulasjonspunktene for kantene, er den av ismus .
La G være en graf med n hjørner og m kanter. En triviell kompleksitet algoritme av orden O ( nm ) er som følger:
a = antall tilkoblede komponenter av G (bestemt ved hjelp av algoritmen for dybdepassering eller algoritmen for breddeovergang ) for hvert toppunkt v av V som har innfallende kanter fjern v fra V b = antall tilkoblede komponenter av G en gang v eliminert hvis b> a v er et artikulasjonspunkt av G sett på plass igjenDenne algoritmen er naiv, det er mye bedre. John Hopcroft og Robert Tarjan beskrev en i 1973 av kompleksiteten i orden O ( n + m ) og som bruker deep traversal algoritmen . Problemet er også studert ut fra online algoritmer .