Faktora grafeo

Faktora grafeo estas dukolora grafeo, kiu reprezentas la faktoradon de funkcio. En probabloteorio, faktoran grafeon oni uzas por reprezenti faktoradon 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 
Faktora grafeo estas dukolora grafeo reprezentanta faktoradon de funkcio. Por faktorafo 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 faktorado 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 
dekstra|eta|300x300ra|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ŭ 
 Kredo-elsendo
 Inferencio je Bejesa reto
 Kondiĉa probablo
 Markova reto
 Bejesa reto
 Teoremo de Hammersley–Clifford

Kategorio:Probabla grafea modelo
Kategorio:Grafeteorio