Chào các em học sinh thân mến,

Hôm nay chúng ta sẽ cùng nhau giải một bài toán thú vị về lý thuyết đồ thị, cụ thể là về “cây” trong môn Toán rời rạc. Dù là kiến thức ở cấp độ đại học, nhưng nguyên lý cơ bản của nó rất dễ hiểu và có thể áp dụng ngay.

Một cây có 15 đỉnh thì có bao nhiêu cạnh ?

A. 13

B. 14

C. 15

D. 16

Trước hết, chúng ta cần hiểu rõ cây (hay đồ thị cây) là gì trong lý thuyết đồ thị. Trong môn Toán rời rạc, một cây được định nghĩa là một loại đồ thị đặc biệt.

• Một đồ thị được gọi là cây nếu nó là đồ thị liên thông và không có chu trình.
• Liên thông có nghĩa là có một đường đi giữa bất kỳ hai đỉnh nào trong đồ thị. Các đỉnh “dính” vào nhau, không có đỉnh nào bị cô lập.
• Không có chu trình có nghĩa là không có đường đi khép kín nào mà đi qua các đỉnh và cạnh khác nhau rồi quay về đỉnh xuất phát. Nói cách khác, không có “vòng lặp” trong đồ thị.

Mối quan hệ giữa số đỉnh và số cạnh trong một cây là một trong những tính chất quan trọng nhất và cơ bản nhất của đồ thị cây. Chúng ta hãy xét một vài ví dụ đơn giản để dễ hình dung hơn về tính chất này:

• Nếu một cây chỉ có 1 đỉnh (\(n=1\)), thì nó không thể có cạnh nào.
  
  Số cạnh: \(e=0\).
  
  Ở đây, chúng ta thấy \(e = n – 1 = 1 – 1 = 0\).
• Nếu một cây có 2 đỉnh (\(n=2\)), để liên thông và không có chu trình, chúng ta chỉ có thể nối hai đỉnh đó bằng một cạnh duy nhất.
  
  Số cạnh: \(e=1\).
  
  Ở đây, chúng ta thấy \(e = n – 1 = 2 – 1 = 1\).
• Nếu một cây có 3 đỉnh (\(n=3\)), chúng ta có thể nối chúng thành một đường thẳng (ví dụ: đỉnh 1 nối với đỉnh 2, đỉnh 2 nối với đỉnh 3) hoặc một đỉnh ở giữa nối với hai đỉnh còn lại (ví dụ: đỉnh 2 nối với đỉnh 1 và đỉnh 3). Cả hai trường hợp này đều có 2 cạnh.
  
  Số cạnh: \(e=2\).
  
  Ở đây, chúng ta thấy \(e = n – 1 = 3 – 1 = 2\).
• Nếu một cây có 4 đỉnh (\(n=4\)), chúng ta sẽ thấy nó luôn có 3 cạnh để đảm bảo tính liên thông và không có chu trình.
  
  Số cạnh: \(e=3\).
  
  Ở đây, chúng ta thấy \(e = n – 1 = 4 – 1 = 3\).

Qua các ví dụ trên, chúng ta có thể nhận thấy một quy luật rất rõ ràng:

Định lý cơ bản về cây: Một đồ thị cây với \(n\) đỉnh luôn có đúng \(n-1\) cạnh.

Đây là một trong những định lý nền tảng của lý thuyết đồ thị cây, và nó có thể được chứng minh bằng nhiều cách khác nhau (ví dụ, bằng phương pháp quy nạp toán học hoặc bằng cách xây dựng cây từng bước).

Áp dụng định lý này vào bài toán của chúng ta:

Đề bài cho biết một cây có 15 đỉnh. Vậy, số đỉnh của cây là \(n = 15\).

Sử dụng công thức \(e = n – 1\), trong đó \(e\) là số cạnh và \(n\) là số đỉnh, chúng ta có:

\(e = 15 – 1 = 14\)

Vậy, một cây có 15 đỉnh sẽ có 14 cạnh.

So sánh kết quả này với các phương án đã cho:

• A. 13
• B. 14
• C. 15
• D. 16

Đáp án chính xác là B. 14.

Hy vọng qua bài giải chi tiết này, các em đã hiểu rõ hơn về tính chất cơ bản của đồ thị cây. Đây là một kiến thức nền tảng rất quan trọng trong lý thuyết đồ thị và có nhiều ứng dụng trong khoa học máy tính, kỹ thuật và các lĩnh vực khác. Chúc các em học tốt!