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.Kenneth H.Rosen, Toán học rời rạc, Nhà xuất bản Khoa Học và Kỹ thuật Hà Nội, 2003, trang 706. 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.a b c Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars", Discrete Mathematics 6 (4): 359–365.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.

 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

 Tham khảo 

Liên kết ngoài

Thể loại:Lý thuyết đồ thị
Thể loại:Toán học rời rạc