Cây dây xích

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Một cây dây xích

Cây dây xích (tiếng Anh: caterpillar tree) là cây chứa đường đi đơn sao cho mọi đỉnh không thuộc đường đi là liền kề với đỉnh thuộc đường đi[1]. Nói một cách khác, tất cả các đỉnh của cây dây xích sẽ có khoảng cách so với đường đi trung tâm không quá 1.

Cây dây xích được nghiên cứu lần đầu tiên trong một chuỗi các bài báo của Harary và Schwenk. Tên gọi tiếng Anh là caterpillar được đề xuất bởi A. Hobbs[2][3].

Tính chất của cây dây xích[sửa | sửa mã nguồn]

Xem thêm[sửa | sửa mã nguồn]

Cây (đồ thị)

Đường đi đơn

Đồ thị duyên dáng

Chú thích[sửa | sửa mã nguồn]

  1. ^ Kenneth H.Rosen, Toán học rời rạc, NXB Khoa Học và Kỹ thuật Hà Nội, 2003, trang 706.
  2. ^ a b c Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars", Discrete Mathematics 6 (4): 359–365.
  3. ^ a b c El-Basil, Sherif (1987), "Applications of caterpillar trees in chemistry and physics", Journal of Mathematical Chemistry 1 (2): 153–174, doi:10.1007/BF01205666.

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]