Arbo (grafeteorio)

Arbo
Markita arbo kun 6 verticoj kaj 5 lateroj
class of graphs with few cliques
koneksa grafo • arbaro • pseudotree • uniquely colorable graph • hypertree • block graph
Verticoj	v
Lateroj	v-1
Koloriga nombro	2
Propraĵoj	Koneksa

En grafeteorio, arbo estas grafeo en kiu ĉiuj du verticoj estas koneksaj per akurate unu vojo. Tiel, ĉiu koneksa grafeo sen cikloj estas arbo. Arbaro estas disa unio 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 K₃ 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.

Propraĵoj

• Ĉ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, kiu estas arbo kiu enhavas ĉ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 n^n-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 d₁, d₂, ..., d_n 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

• Diestel, Reinhard (2005). Graph Theory - Grafea teorio, 3-a (Berlino, Novjorko). Springer-Verlag. ISBN 978-3-540-26183-4.