Arbo (grafeoteorio)

En grafeoteorio, **arbo** estas grafeo, en kiu ĉiuj du verticoj estas konektitaj per precize unu vojo. Tiel, ĉiu koneksa grafeo sen cikloj estas arbo. **Arbaro** estas disa kunaĵo de arboj.

## Difinoj 
**Arbo** estas nedirektita simpla grafeo *G* kiu kontentigas iun el jenaj ekvivalentaj kondiĉoj:

* *G* estas koneksa kaj ne havas ciklojn.
* *G* ne havas ciklojn, kaj simpla ciklo estas nepre formita se inter iuj ajn verticoj de *G* la nova latero estas aldonita al *G*.
* *G* estas koneksa, kaj ĝi estas ne plu koneksa se ajna latero estas forprenita de *G*.
* *G* estas koneksa kaj la 3-vertica plena grafeo *K3* ne estas minoro de *G*.
* Ĉiuj du verticoj en *G* povas esti trakonektitaj per unika simpla vojo.

Se la kvanto *n* de verticoj de *G* estas finia, do estas ankoraŭ jenaj ekvivalentaj kondiĉoj:

* *G* estas koneksa kaj havas *n-1* laterojn.
* *G* ne havas simplajn ciklojn kaj havas *n-1* laterojn.

**Nereduktebla** aŭ **serio-malpligrandigita** arbo estas arbo en kiu ne estas vertico de grado 2.

Nedirektita simpla grafeo *G* estas nomata kiel *arbaro* se ĝi havas ne simplajn ciklojn.

La termino **heĝo** iam temas pri ordigita vico de arboj.

**Direktita arbo** estas orientita grafeo kiu estus arbo se la direktoj sur la lateroj estus ignoritaj. Iu aŭtoroj limigas la terminon al la okazo je kiu la lateroj estas ĉiuj direktita al aparta vertico, aŭ ĉiuj direktita for de aparta vertico.

Arbo estas nomata kiel **radikhava arbo** se unu vertico estas destinita al esti la *radiko*, en kiu okazo la lateroj havas naturan orientiĝon, *al* aŭ *for* de la radiko. La **arbo-ordo** estas la parta ordigo de la verticoj de la arbo kun *u≤v* se kaj nur se la unika vojo de la radiko al *v* pasas tra *u*. En ĉirkaŭteksto kie arboj estas supozitaj al havi radikon, arbo sen iu destinita radiko estas nomata kiel **senradika arbo**. En radikhava arbo, la **gepatro** de vertico estas la vertico koneksa al ĝi sur la vojo al la radiko; ĉiu vertico escepte la radiko havas unikan gepatron. **Infano** de vertico *v* estas vertico kies gepatro estas *v*. **Folio** estas vertico sen infanoj.

**Markita arbo** estas arbo en kiu al ĉiu vertico estas donita unika marko. La verticoj de markita arbo de *n* verticoj estas tipe donitaj la markoj *1, 2, …, n*. **Rikura arbo** estas markita radikhava arbo kie la verticaj markoj respektivas la arbo-ordo, kio estas, se *un-2* malsamaj manieroj trakonekti ilin por fari arbon. Ĉi tiu rezulto estas nomata kiel formulo de Cayley. Ĝi povas esti pruvita per unue montrado ke la kvanto de arboj kun *n* verticoj de gradoj *d1, d2, ..., dn* estas la polinoma koeficiento

:  {n-2 \choose d_1-1, d_2-1, \ldots, d_n-1}

Alternativa pruvo estas per vicoj de Prüfer.

Kalkulado de kvanto de nemarkitaj arboj estas pli malsimpla problemo. Neniu fermita formulo por la kvanto *t(n)* de arboj kun *n* verticoj supren ĝis grafea izomorfio estas sciata. Estas pruvite ke

:  t(n) \sim C \alpha^n n^{-5/2} \! se  n\to\infty

kun *C=0,53495...* kaj *α=2,95576...* kie f \sim g\! signifas ke \lim_{n \to \infty} f/g = 1.

## Vidu ankaŭ 
* Arbo (datumstrukturo)
* Duuma arbo
* Decida arbo
* Pseŭdoarbaro
* Arbo (hierarkio)
* Arba datumstrukturo
* Minimuma generanta arbo

## Eksteraj ligiloj 
* 

Kategorio:Grafeteorio