Đơn đồ thị là gì? Cách xác định đơn đồ thị

Cách xác định đơn đồ thị nhanh và chính xác

Đơn đồ thị là một trong những khái niệm nền tảng của Lý thuyết đồ thị trong chương trình Toán 11. Việc hiểu rõ đơn đồ thị là gì, đặc điểm nhận dạng và cách xác định đơn đồ thị không chỉ giúp học sinh nắm vững kiến thức lý thuyết mà còn hỗ trợ hiệu quả trong việc giải các bài tập về đỉnh, cạnh, bậc của đỉnh và mô hình hóa các bài toán thực tế.

Đồ thị là gì?

Một đồ thị là một tập hợp hữu hạn các diemr (gọi là các đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị.

Chú ý: Theo định nghĩa của đồ thị, các cạnh của đồ thị thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào đều không quan trọng, mà bản chất là đồ thị có bao nhiêu đỉnh, bao nhiêu cạnh và đỉnh nào nối với đỉnh nào.

Ta thường kí hiệu V(G) là tập hợp các đỉnh, E(G) là tập hợp các cạnh của đồ thị G và viết G = (V; E)

Nếu hai đầu mút của cạnh trùng nhau tại đỉnh C thì gọi cạnh ấy là khuyên, kí hiệu là CC.

Đơn đồ thị

Một đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh (không có hai cạnh nào cùng nối một cặp đỉnh) gọi là một đơn đồ thị.

Vậy để xác định đồ thị có phải đơn đồ thị hay không ta xét xem đồ thị có thỏa mãn:

• Giữa hai đỉnh bất kỳ có không quá một cạnh nối chúng.

• Không có cạnh nào nối một đỉnh với chính nó (không có khuyên).

Ví dụ: Tập đỉnh: V={A,B,C,D}

Tập cạnh: E={AB,AC,BD,CD}

Đây là đơn đồ thị vì:

• Không có hai cạnh trùng nhau giữa cùng một cặp đỉnh.

• Không có cạnh khuyên.

Ví dụ: Xác định xem đồ thị có tập đỉnh {A, B, C, D} với tập cạnh {(A,B), (A,C), (B,C), (C,D)} có phải là đồ thị đơn giản hay không?

Kiểm tra khuyên: Không có cạnh nào nối một đỉnh với chính nó (ví dụ: không có (A,A)), vì vậy không có khuyên.

Kiểm tra các cạnh song song:  Mỗi cặp đỉnh chỉ xuất hiện nhiều nhất một lần trong tập hợp cạnh. Ví dụ, (A,B) chỉ được liệt kê một lần. Vì vậy, không có cạnh trùng lặp.

Ta có thể hiểu đơn giản đơn đồ thị qua các ví dụ sau:

Ví dụ 1: Quan hệ bạn bè trong lớp

Xét 4 bạn học sinh:

• An kết bạn với Bình.

• An kết bạn với Cường.

• Bình kết bạn với Dũng.

Mỗi cặp bạn chỉ có một mối quan hệ bạn bè.

Hoặc viết dưới dạng tập cạnh: E={AB, AC, BD}

⇒ Đây là đơn đồ thị vì giữa hai bạn bất kỳ chỉ có tối đa một cạnh.

Ví dụ 2: Sơ đồ đường đi giữa các địa điểm

Giữa các địa điểm:

• Trường học (T)

• Thư viện (V)

• Công viên (C)

Có các con đường:

Mỗi cặp địa điểm chỉ có một con đường trực tiếp.

⇒ Đây là đơn đồ thị.

--------------------------------

Nắm vững khái niệm và cách xác định đơn đồ thị là bước quan trọng để học tốt chuyên đề Lý thuyết đồ thị Toán 11. Khi hiểu được các đặc trưng của đơn đồ thị, học sinh sẽ dễ dàng tiếp cận các dạng bài tập nâng cao, đồng thời phát triển tư duy logic và kỹ năng phân tích cấu trúc mạng lưới trong toán học.