Thuật ngữ về cây nhị phân Mình đọc lý thuyết đồ thị, đang đọc phần cây nhị phân thì gặp 1 thuật ngữ là "Planted trivalent binary trees". Mọi người cho mình hỏi thuật ngữ này trong tiếng Việt có nghĩa là gì? |
Cái cây nhị phân này liên quan đến số Catalan, trước giờ em cũng chỉ gặp thuật ngữ tiếng Anh chứ chưa gặp từ tiếng Việt tương ứng bao giờ. Em nghĩ anh dùng tiếng Anh để dạy các em ấy luôn cho dễ vì em nghĩ trong Toán có nhiều cái buộc phải dùng tiếng Anh thôi chứ không có thuật ngữ chính thống tương ứng bên tiếng Việt. Các số square-free trong Lý thuyết số chẳng hạn. Planted trivalent binary tress là cây nhị phân mà trừ root ra thì tất cả các đỉnh trong (interval vertex) đều có bậc 3. Số loại cây này với n đỉnh bằng số lượng số Catalan thứ $n-1 $ và là $\frac{1}{n}C_{2n-2}^{n-1} $. |
Trích:
Bản chất cây cũng là một đồ thị, nhưng khi nói về cây nhị phân, người ta quan tâm đến gốc (root), nút (node), lá (leaf), độ sâu (depth), con trái, con phải, bán kính, đường kính,... Một nút bao giờ cũng có các quan hệ, con của nút cha, cha của nút con. Như thế Planted trivalent binary tress là cây có các nút có bậc là 3, nếu bỏ đi nút gôc, trong toán rời rạc gọi là cây đầy đủ (đỉnh nào cũng có 2 con). Và từ n đỉnh này ta tạo ra được nhiều số cây khung (số Caylay $ n^k-2 $ cây khung, k là độ sâu), nhưng thỏa mãn là cây Planted trivalent thì chỉ có $\frac{1}{n}C_{2n-2}^{n-1} $. Tổng quát bài toán này các bạn đọc thêm về bài toán số lá phiếu () , hay cách chứng minh định lý Caylay bằng lý thuyết hàm sinh. |
Trích:
|
Múi giờ GMT. Hiện tại là 05:29 PM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.