Arbigo

eta|Grafeo kun ok verticojn eblas malkomponi al arbo kun ses verticoj. Ĉiu eĝo en la origina grafeo ligas iujn du verticojn en la arbo. Ĉiu vertico de la arbo estas subaro da koneksaj vertcicoj. Ĉar la maksimuma kardinalo inter arba verticoj estas 3, do la arbolarĝo de la origina grafeo estas 2.
En grafeoteorio, **arbigo** ĵetas grafeon al arbo. Oni povas difini arbolarĝon per tia operacio. La rezulta arbo ankaŭ utilas por rapidigi ian komputadon.

En maŝinlernado, arbigo grave rolas en problemoj, ekzemple probabla inferencio, kaj matrica malkomponado.

La ideon de arbigo unue proponis Rudolf Halin (1976). Poste refoje ĝin malkovris Neil Robertson kaj Paul Seymour (1984). Ĝi estas temo de pluraj studoj ĝis nun.

## Difino 
intuicie, arbigo reprezentas la verticojn de grafeo *G* per subaroj de arbo tiel, ke la verticoj en G estas najbaroj se nur se iliaj subaroj intersekcas. Tiel ĉi, *G* iĝas subgrafeo de la intersekca grafeo de la subarboj. La tuta intersekca grafeo estas kordeca grafeo.

Ĉiu subaro rilatas grafea vertico kun aro da arbaj verticoj. Precize, por grafeo *G* = (*V*, *E*), ĝia arbigito estas paro (*X*, *T*), kie *X* = {*X*1, ..., *X**n*} estas familio de subaroj de *V*, kaj *T* estas arbo, kies vertcioj estas subaroj de *X**i*, kun la jenaj propraĵoj:
# La kunaĵo de aroj *X**i* estas *V*. Tio signifas, ke ĉiu grafea vertico rilatas al almenaŭ unu arba vertico..
# Por ĉiu eĝo (*v*, *w*) de la grafeo, estas subaro *X**i*, kiu enhavas ambaŭ *v* kaj *w*. Tio signifas, verticoj estas najbaroj en la grafeo nur se iliaj subaroj intersekcas.
# (**Propraĵo pri kuranta intersekco**, aŭ **kohereco**) Se ambaŭ *X**i* kaj *X**j* enhavas verticon *v*, ĉiuj verticoj *X**k* en ĉiu ĉeno inter* X**i* and *X**j* ankaŭ enhavu  *v*. Tio signifas, verticoj rilataj al *v* estas koneksa subarbo de *T*. Ekvivalente, por arbaj verticoj X_i, X_j kaj X_k, Se X_k estas en la ĉeno inter X_i kaj X_j, doX_i \cap X_j \subseteq X_k.
Eble estas pluraj arbigitoj de unu grafeo. Ekzemple, triviala arbigo estas simple vertico kiu enhavas ĉiujn grafeajn verticojn.

## Metodo 
eta|Du malsamaj arbigoj de unu grafeo.
Jen estas unu simpla algoritmo por arborigi direktan grafeon. (Por aborigi sendirektan grafen, preterlasu la 1-an paŝon)
# Fari direktan grafeon sendirekta. Forigi la direkton de la eĝoj kaj ligi la patrojn de ĉiu verticoj. (*moraligado*)
# Kordecigi la grafeon
# Fari verticon el trianguloj de la kordecigita grafeo. Se du trianguloj havas komunan lateron, iliaj verticoj ligiĝu. Tiel oni faras koneksan grafeon, kiu estas la arbigo de la origina grafeo.

## Arbolarĝo 
La *larĝo* de arbigo estas la maksimuma kardinalo inter verticoj minus 1. La arbolarĝo tw(*G*) de grafeo *G* estas la minimuma larĝo inter ĉiuj eblaj arbigoj ĝiaj. La "minus 1" parto estas por ke la arbolarĝo de arbo estu 1. Aliaj difinoj eblas por arbolarĝo, ekzemple per kordeca grafeo.

Estas NP-plena problemo determini ĉu grafeo *G* havas arbolarĝon malpli granda ol variablo* k*. Tamen, se *k* estas konstanta, oni povas rekoni grafeojn kun arbolarĝo *k*, kaj konstrui arbigon kun larĝon *k* por ili en lineara tempo. La algoritmo dependas eksponenciale sur *k*.

## Vidu ankaŭ 
* Enbranĉigo, proksimume rilata transformo, kies larĝo estas proksimume je konstante faktoro al arbolarĝo.
* Kredo-elsendo uzas arbigon por grafeo kun ciklo.
* Kordeca grafeo

## Notoj 
Kategorio:Grafeteorio