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. 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.

Tính chất của cây dây xích 
 Nếu bỏ tất cả lá và cạnh liên thuộc thì cây dây xích trở thành một đồ thị đường đi.
 Mỗi đỉnh với bậc lớn hơn hoặc bằng 3 thì liền kề với không quá 2 đỉnh trong.
 Cây dây xích là đồ thị duyên dáng.

Xem thêm
Cây (đồ thị)

Đường đi đơn

Đồ thị duyên dáng

Chú thích

Tham khảo

Liên kết ngoài

Lý thuyết đồ thị
Toán học rời rạc
Cây (đồ thị)
Toán hóa học