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 u<v por du verticoj u kaj v, tiam la marko de u estas pli malgranda ol la marko de v.

Orda arbo estas radikhava arbo por kiu ordigo estas donita por la infanoj de ĉiu vertico.

k-uma arbo estas radikhava arbo por kiu ĉiu vertico kiu ne estas folio havas maksimume n infanojn. 2-uma arbo estas duuma arbo.

 Ecoj 
 Ĉiu arbo estas dukolora grafeo kaj mediana grafeo. Ĉiu arbo kun nur kalkuleble multaj verticoj estas ebena grafeo.

 Ĉiu koneksa grafeo G enhavas generantan arbon, kio estas arbo enhavanta ĉiujn verticojn de G kaj kies lateroj estas (eble ne ĉiuj) lateroj de G.

 Ĉiu finia arbo kun n≥2 verticoj, havas almenaŭ du lasojn aŭ verticojn de grado 1. La minimuma kvanto de lasoj respektivas al la arbo kiu estas vojo kaj la maksimuma ebla kvanto de lasoj n-1 respektivas al la arbo kiu estas stelo.

 Por ĉiuj tri verticoj de arbo, la tri vojoj inter ili havas almenaŭ unu komunan verticon.

 Kvanto de arboj 
Se estas donitaj n markitaj verticoj do estas nn-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



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

  se 

kun C=0,53495... kaj α=2,95576... kie  signifas ke .

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

 Eksteraj ligiloj 



Kategorio:Grafeteorio