Multitree - Multitree
În matematică combinatorică și teoretică a ordinii , un arboret multiplu poate descrie oricare dintre două structuri echivalente: un grafic aciclic direcționat (DAG) în care setul de vârfuri accesibil din orice vârf induce un copac sau un set parțial ordonat (pozet) care nu au patru itemi a , b , c și d formând un subordine de diamant cu a ≤ b ≤ d și a ≤ c ≤ d, dar cu b și c incomparabile între ele (numit și un pozet fără diamant ).
În teoria complexității computaționale , multi-arbori au fost, de asemenea, numiți grafice puternic fără echivoc sau mangrove ; ele pot fi utilizate pentru a modela algoritmi nedeterministici în care există cel mult o cale de calcul care leagă oricare două stări.
Multi-arbori pot fi folosiți pentru a reprezenta taxonomii multiple suprapuse peste același set de terenuri. Dacă un arbore genealogic poate conține mai multe căsătorii de la o familie la alta, dar nu conține căsătorii între oricare două rude de sânge, atunci formează un arboriu multiplu.
Echivalența dintre definițiile DAG și pozet
Într-un grafic aciclic direcționat, dacă setul de vârfuri accesibile de la orice vârf induce un copac, sau echivalent dacă există cel mult o cale direcționată între oricare două vârfuri în ambele direcții, atunci relația sa de accesibilitate este un ordin parțial fără diamant. În schimb, într-o ordine parțială, dacă nu are diamante, atunci reducerea sa tranzitivă identifică un grafic aciclic direcționat în care setul de vârfuri accesibil din orice vârf induce un copac
Familii fără diamante
O familie de seturi fără diamante este o familie F de seturi a căror ordonare de includere formează o poziție fără diamante. Dacă D ( n ) reprezintă cea mai mare familie posibilă de subseturi fără diamante a unui set de elemente n , atunci se știe că
și se presupune că limita este 2.
Structuri conexe
Un politree , un grafic aciclic direcționat format prin atribuirea unei orientări fiecărei margini a unui arbore nedirecționat, poate fi privit ca un caz special al unui multi-arbore.
Setul tuturor vârfurilor conectate la orice vârf dintr-un arborescență multiplă formează o arborescență .
Cuvântul "multi-copac" a fost, de asemenea, folosit pentru a se referi la o ordine parțială serie-paralelă sau la alte structuri formate prin combinarea mai multor copaci.
