Faktora grafeo

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search

Faktora grafeo estas dukolora grafeo, kiu reprezentas la faktorigon de funkcio. En probabloteorio, faktoran grafeon oni uzas por reprezenti faktorigon de probablodistribua funkcio, ebligante rapidan komputadon, ekzemple de marĝena distribuo tra la sum-produkta algoritmo. Unu el la gravaj sukcesoj de faktora grafeo kaj la sum-produkta algoritmo estis malkodigo de preskaŭ-perfekta eraro-korektada kodo kiel Maldensa Pareca Kodo kaj kodo turbo.

Faktora grafeo estas ĝeneraligo de limiga grafeo. Faktoro, kies valoro estas aŭ 0 aŭ 0, estas limigo. Limiga grafeo estas faktora grafeo kies faktoroj estas limigoj.

Difino[redakti | redakti fonton]

Faktora grafeo estas dukolora grafeo reprezentanta faktorigon de funkcio. Por faktorigo de funkcio ,

kie estas la argumentaro de la funkcio. La rilata faktora grafeo havas variablo-verticojn, faktoro-verticojn , kaj eĝojn . Ĉiu eĝo ligas variablo-verticon kaj faktoro-verticon, kaj dependas al faktorigo jene: ekzistas sendirekta eĝo inter faktoro-vertico kaj variablo-vertico se kaj nur se , alprene ke la funkcio estas reela:  .

Oni povas uzi faktoran grafeon kun mesaĝada algoritmo por rapide komputi propraĵon de funkcio , ekzemple la marĝenan distribuon.

Ekzemplo[redakti | redakti fonton]

Ekzemplo de faktora grafeo

Konsideru funkcion kiu faktoriĝas jene

,

Dekstre montriĝas la rilata faktora grafeo. Vidu ke la faktora grafeo havas ciklon. Se oni kunigus al unu faktoro, la rezultanta faktora grafeo iĝus arbo.  Tio ĉi gravas ĉar mesaĝadaj algoritmoj ĝenerale bezonas arbon por ekzakta kalkulado.

Vidu ankaŭ[redakti | redakti fonton]