Đồ thị duyên dáng

Một đồ thị có e đỉnh, và có thể gán nhãn cho mỗi đỉnh với một số tự nhiên bất kỳ nằm giữa 0 và e sao cho:

mỗi đỉnh có một nhãn phân biệt;
trị tuyệt đối của hiệu giữa hai nhãn ở hai đầu mút của các cạnh là khác nhau.

Với n bằng 5

được gọi là đồ thị duyên dáng^[1] (tiếng Anh: graceful graph).

Thuật ngữ "đồ thị duyên dáng" được đặt bởi Solomon W. Golomb; lớp đồ thị có gán nhãn này ban đầu được gọi là β-gán nhãn bởi Alex Rosa trong một bài báo năm 1967 về gán nhãn đồ thị.^[2].

Liên quan đến đồ thị duyên dáng, có một phỏng đoán chưa được chứng minh hay bác bỏ có tên là phỏng đoán Ringel-Kotzig. Phỏng đoán này phát biểu rằng: " tất cả các cây đều là đồ thị duyên dáng". Phỏng đoán Ringel-Kotzig còn có tên gọi khác là "phỏng đoán Von Koch" ^[3] và "phỏng đoán về gán nhãn đồ thị". Kotzig gọi các cố gắng nhằm chứng minh phỏng đoán này là một "căn bệnh".

Các kết quả liên quan sửa

Một đường đi đơn với n đỉnh luôn là đồ thị duyên dáng (xem ^[4] (tr.706)). Cách gán nhãn từ trái qua phải như sau: với đỉnh thứ nhất ta gán nhãn 1, đỉnh thứ hai gán nhãn n, đỉnh thứ 3 gán nhãn 2, đỉnh thứ 4 gán nhãn n-1,... đỉnh thứ k gán nhãn ${\frac {k+1}{2}}$ nếu k lẻ, và $n-{\frac {k}{2}}+1$ nếu k chẵn,.... 2 Hình dưới đây minh họa cho cách gán nhãn cho đường đi đơn độ dài n-1 và đường đi đơn độ dài bằng 4:

Gán nhãn cho đường đi đơn có n đỉnh

Với n bằng 5

Cây dây xích cũng là đồ thị duyên dáng (xem ^[4] (tr. 706)).
Trong bài báo của mình, Rosa đã chứng minh rằng mọi đồ thị Euler với số đỉnh m thỏa mãn $m\equiv 1{\pmod {4}}$ hoặc $m\equiv 2{\pmod {4}}$ đều không duyên dáng.^[2]
Cũng trong bài báo của mình, Rosa đã chứng minh mọi vòng $C_{n}$ với $n\equiv 0{\pmod {4}}$ hoặc $n\equiv 3{\pmod {4}}$ đều duyên dáng.
Tất cả các cây có không quá 27 đỉnh đều duyên dáng, kết quả này được Aldred và McKay khẳng định vào năm 1998 bằng chương trình máy tính ^[5]^[6]. Vào năm 2010, sử dụng một phương pháp máy tính khác, trong dự án mang tên "Graceful Tree Verification Project", dẫn dắt bởi Wenjie Fang, kết quả được mở rộng cho các cây không quá 35 đỉnh^[7].
Tất cả các đồ thị hình bánh xe, đồ thị mạng đều duyên dáng.^[5]
Tất cả các đồ thị siêu khối đều duyên dáng.^[8]
Tất cả các đồ thị đơn có không quá 4 đỉnh đều duyên dáng. Các đơn đồ thị không duyên dáng có 5 đỉnh là đồ thị chu trình $C_{5}$ , đồ thị đầy đủ $K_{5}$ ; và đồ thị cánh bướm.^[9]

Xem thêm sửa

Chú thích sửa

^ Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript
^ ^a ^b Alex Rosa, "On certain valuations of the vertices of a graph." Theory of Graphs (International Symposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod Paris. (1967) 349–355
^ “Bản sao đã lưu trữ”. Bản gốc lưu trữ ngày 17 tháng 1 năm 2007. Truy cập ngày 11 tháng 12 năm 2010.
^ ^a ^b 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
^ ^a ^b Joseph A. Gallian, "A Dynamic Survey of Graph Labeling." The Electronic Journal of Combinatorics 5 (1998). MR 1668059 PDF Lưu trữ 2012-01-31 tại Wayback Machine, updated 2009
^ R. E. L. Aldred, B. D. McKay, "Graceful and harmonious labellings of trees", Bulletin of the Institute of Combinatorics and Its Applications 23 (1998), 69–72 MR 1621760
^ Wenjie Fang, "A Computational Approach to the Graceful Tree Conjecture". arXiv:1003.3045. See also Graceful Tree Verification Project Lưu trữ 2012-07-29 tại Wayback Machine
^ Anton Kotzig. "Decomposition of complete graphs into isomorphic cubes", Journal of Combinatoric Theory, Series B, 31 (1981) 292–296 MR 0638285; cited in Gallian, 1998
^ Weisstein, Eric W., "Graceful graph", MathWorld.

Tham khảo sửa

Liên kết ngoài sửa

[Vas2001-1] Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript

[Ros1967-2] Alex Rosa, "On certain valuations of the vertices of a graph." Theory of Graphs (International Symposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod Paris. (1967) 349–355

[3] “Bản sao đã lưu trữ”. Bản gốc lưu trữ ngày 17 tháng 1 năm 2007. Truy cập ngày 11 tháng 12 năm 2010.

[KHR-4] 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

[Gal2007-5] Joseph A. Gallian, "A Dynamic Survey of Graph Labeling." The Electronic Journal of Combinatorics 5 (1998). MR 1668059 PDF Lưu trữ 2012-01-31 tại Wayback Machine, updated 2009

[6] R. E. L. Aldred, B. D. McKay, "Graceful and harmonious labellings of trees", Bulletin of the Institute of Combinatorics and Its Applications 23 (1998), 69–72 MR 1621760

[7] Wenjie Fang, "A Computational Approach to the Graceful Tree Conjecture". arXiv:1003.3045. See also Graceful Tree Verification Project Lưu trữ 2012-07-29 tại Wayback Machine

[Kot1981-8] Anton Kotzig. "Decomposition of complete graphs into isomorphic cubes", Journal of Combinatoric Theory, Series B, 31 (1981) 292–296 MR 0638285; cited in Gallian, 1998

[Mat2007-9] Weisstein, Eric W., "Graceful graph", MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]