Arbigo

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 grafeteorio, arbigo ĵetas grafeon al arbo. Oni povas difini arbolarĝon per la operacio. La arbo rezultata 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₁, ..., X_n} estas familio de subaroj de V, kaj T estas arbo, kies vertcioj estas subaroj de X_i, kun la jenaj propraĵoj:^[1]

1. La kunaĵo de aroj X_i estas V. Tio signifas, ke ĉiu grafea vertico rilatas al almenaŭ unu arba vertico..
2. 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.
3. (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 ${\displaystyle X_{i}}$, ${\displaystyle X_{j}}$ kaj ${\displaystyle X_{k}}$, Se ${\displaystyle X_{k}}$ estas en la ĉeno inter ${\displaystyle X_{i}}$ kaj ${\displaystyle X_{j}}$, do${\displaystyle X_{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

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)

1. Fari direktan grafeon sendirekta. Forigi la direkton de la eĝoj kaj ligi la patrojn de ĉiu verticoj. (moraligado)
2. Kordecigi la grafeon
3. 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.^[2] 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.^[3] 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

1. Diestel (2005) section 12.3
2. Arnborg, Corneil & Proskurowski (1987).
3. Bodlaender (1996).