Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo tài liệu 'structures arborescentes', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chapitre 2. Structures Arborescentes CHAPITRE 2. STRUCTURES ARBORESCENTES. 2.1 DEFINITIONS. 2.1.1 Arbres. C est un graphe non orienté connexe acyclique. Un arbre comprend n - 1 arêtes. L addition à un arbre d une arête entre deux sommets crée un cycle et un seul. 2.1.2 Forets. C est un graphe non orienté acyclique pas forcément connexe . Chaque composante connexe d une forêt est un arbre. 2.1.3 Arborescence. C est un graphe orienté où chaque sommet possède un seul précédent sauf un qui n en a pas la RACINE. Pour tout x de X il existe un chemin unique de la racine à x. On considère un nreud x d une arborescence T de racine r. Un nreud y quelconque sur le chemin unique de rà x est appelé ANCETRE de x x est un DESCENDANT de y. Si le dernier arc sur le chemin de r vers x est y x alors y est le père de x x est un fils de y. Si deux nreuds ont le même père ils sont frères. Un nreud sans fils est une feuille. Un noeud qui n est pas une feuille est dit un noeud interne. La longueur du chemin entre r et x est la profondeur de x dans T. Truong My Dung Mail tmdung@fit.hcmuns.edu.vn 15 Chapitre 2. Structures Arborescentes La hauteur d un noeud x est definie recursivement de la I aqon suivante h x 0 si x est la racine. h x 1 h y si y est le pere de x. Degre d un noeud Degre d une aborescence. Degre d un noeud est le nombre de ses sous-aborescences. Degre d une aborescence est le degre maximal des noeuds. Si une aborescence T a le degre m T est dit l aborescence a m- aires. Si chaque nreud a au maximum deux fils on parle d arborescence binaire. EXEMPLE. Arborescence 3-aires de 8 nreuds de hauteur 4 avec la racine. Niveau 0. ----------------------Gb 1 3 Niveau 1. Niveau 2. Niveau 3. Niveau 4. FIG.2.2. 2.1.4. EXEMPLE. On peut parfois representer une relation d inclusion entre plusieurs ensembles par une aborescence B C D c A. E F G H c B. M N c D. I c E. J K c F. L c H. Truong My Dung 16 Mail tmdung@fit.hcmuns.edu.vn Chapitre 2. Structures Arborescentes Une variable structuree .
