Cây dây xích

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

  • 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

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

Liên kết ngoài