Arbigo

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 = {X1, ..., Xn} estas familio de subaroj de V, kaj T estas arbo, kies vertcioj estas subaroj de Xi, kun la jenaj propraĵoj: section 12.3
 La kunaĵo de aroj Xi 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 Xi, 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ŭ Xi kaj Xj enhavas verticon v, ĉiuj verticoj Xk en ĉiu ĉeno inter Xi and Xj ankaŭ enhavu  v. Tio signifas, verticoj rilataj al v estas koneksa subarbo de T. Ekvivalente, por arbaj verticoj ,  kaj , Se  estas en la ĉeno inter  kaj , do.
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