PHẦN 2. BẬC CỦA ĐỈNH VÀ ĐỊNH LÝ BẮT TAY 1. WHAT - Khái niệm và nội dung cốt lõi: • Bậc của đỉnh deg(v): Là số cạnh liên thuộc với đỉnh v. Mỗi khuyên tại đỉnh v được tính 2 lần vào deg(v). • Đỉnh cô lập: deg(v) = 0. Đỉnh treo: deg(v) = 1. • Định lý bắt tay (Handshaking Theorem): ∑ deg(v) = 2|E| (Tổng bậc mọi đỉnh bằng hai lần số cạnh). • Hệ quả 1: Trong mọi đồ thị vô hướng, số lượng các đỉnh có bậc lẻ luôn là một số chẵn. • Hệ quả 2: Đồ thị chính quy bậc k (mọi đỉnh đều có bậc k) có số cạnh |E| = n·k / 2 → tích n·k luôn chẵn. • Đồ thị có hướng: deg⁻(v) (bán bậc vào), deg⁺(v) (bán bậc ra). Luôn có: ∑ deg⁻(v) = ∑ deg⁺(v) = |E|. - Đỉnh nguồn: deg⁻(v) = 0 (chỉ đi ra). Đỉnh đích: deg⁺(v) = 0 (chỉ nhận vào). 2. WHEN - Khi nào sử dụng? • Khi cần kiểm tra tính hợp lệ của dữ liệu đồ thị đầu vào (kiểm tra tổng bậc có bằng 2|E| không). • Khi giải các bài toán suy luận tồn tại: kiểm tra một cấu hình bắt tay, phân chia công việc hay mạng kết nối có khả thi hay không. 3. WHY - Tại sao cần nội dung này? • Định lý bắt tay là công cụ kiểm tra tính hợp lệ (sanity check) nhanh nhất trong lập trình thuật toán đồ thị. • Giúp tính nhanh số cạnh khi biết bậc của các đỉnh mà không cần đếm thủ công. 4. HOW - Quy trình thực hiện: • Tính tổng bậc S = ∑ deg(v). Nếu S là số lẻ, kết luận ngay: không tồn tại đồ thị thỏa mãn. • Đếm số đỉnh có bậc là số lẻ. Nếu số lượng đỉnh này lẻ, kết luận vi phạm Hệ quả 1. • Nếu S chẵn, tính số cạnh |E| = S / 2. • Với đồ thị có hướng: cộng riêng tổng bậc vào và tổng bậc ra rồi so sánh với tổng số cung |E|. 5. Ví dụ minh họa: • Một nhóm 25 sinh viên, mỗi người có đúng 3 bạn thân: Tổng bậc = 25 × 3 = 75 (số lẻ) → Trái định lý bắt tay → Không thể xảy ra. • Đồ thị có 7 đỉnh với bậc lần lượt là (2, 4, 3, 3, 4, 3, 1): Tổng bậc = 20 = 2 × 10 → Đồ thị có 10 cạnh; có 4 đỉnh bậc lẻ (3, 3, 3, 1) là số chẵn → Thỏa mãn. 6. Bài tập vận dụng: • Bài 2.1: Cho biết trong các dãy bậc sau, dãy nào có thể là dãy bậc của một đơn đồ thị vô hướng? Giải thích: a) (3, 3, 3, 3, 3) b) (4, 4, 3, 3, 3, 3, 2, 2) c) (5, 5, 4, 3, 2, 1) • Bài 2.2: Một đồ thị có hướng gồm 6 đỉnh có bậc vào lần lượt là (1, 2, 0, 3, 1, 1). Hỏi đồ thị có bao nhiêu cạnh (cung) và tổng bậc ra của các đỉnh bằng bao nhiêu?
PHẦN 2. BẬC CỦA ĐỈNH VÀ ĐỊNH LÝ BẮT TAY
1. WHAT - Khái niệm và nội dung cốt lõi:
• Bậc của đỉnh deg(v): Là số cạnh liên thuộc với đỉnh v. Mỗi khuyên tại đỉnh v được tính 2 lần vào deg(v).
• Đỉnh cô lập: deg(v) = 0. Đỉnh treo: deg(v) = 1.
• Định lý bắt tay (Handshaking Theorem): ∑ deg(v) = 2|E| (Tổng bậc mọi đỉnh bằng hai lần số cạnh).
• Hệ quả 1: Trong mọi đồ thị vô hướng, số lượng các đỉnh có bậc lẻ luôn là một số chẵn.
• Hệ quả 2: Đồ thị chính quy bậc k (mọi đỉnh đều có bậc k) có số cạnh |E| = n·k / 2 → tích n·k luôn chẵn.
• Đồ thị có hướng: deg⁻(v) (bán bậc vào), deg⁺(v) (bán bậc ra). Luôn có: ∑ deg⁻(v) = ∑ deg⁺(v) = |E|.
- Đỉnh nguồn: deg⁻(v) = 0 (chỉ đi ra). Đỉnh đích: deg⁺(v) = 0 (chỉ nhận vào).
2. WHEN - Khi nào sử dụng?
• Khi cần kiểm tra tính hợp lệ của dữ liệu đồ thị đầu vào (kiểm tra tổng bậc có bằng 2|E| không).
• Khi giải các bài toán suy luận tồn tại: kiểm tra một cấu hình bắt tay, phân chia công việc hay mạng kết nối có
khả thi hay không.
3. WHY - Tại sao cần nội dung này?
• Định lý bắt tay là công cụ kiểm tra tính hợp lệ (sanity check) nhanh nhất trong lập trình thuật toán đồ thị.
• Giúp tính nhanh số cạnh khi biết bậc của các đỉnh mà không cần đếm thủ công.
4. HOW - Quy trình thực hiện:
• Tính tổng bậc S = ∑ deg(v). Nếu S là số lẻ, kết luận ngay: không tồn tại đồ thị thỏa mãn.
• Đếm số đỉnh có bậc là số lẻ. Nếu số lượng đỉnh này lẻ, kết luận vi phạm Hệ quả 1.
• Nếu S chẵn, tính số cạnh |E| = S / 2.
• Với đồ thị có hướng: cộng riêng tổng bậc vào và tổng bậc ra rồi so sánh với tổng số cung |E|.
5. Ví dụ minh họa:
• Một nhóm 25 sinh viên, mỗi người có đúng 3 bạn thân: Tổng bậc = 25 × 3 = 75 (số lẻ) → Trái định lý bắt tay
→ Không thể xảy ra.
• Đồ thị có 7 đỉnh với bậc lần lượt là (2, 4, 3, 3, 4, 3, 1): Tổng bậc = 20 = 2 × 10 → Đồ thị có 10 cạnh; có 4 đỉnh
bậc lẻ (3, 3, 3, 1) là số chẵn → Thỏa mãn.
6. Bài tập vận dụng:
• Bài 2.1: Cho biết trong các dãy bậc sau, dãy nào có thể là dãy bậc của một đơn đồ thị vô hướng? Giải thích:
a) (3, 3, 3, 3, 3)
b) (4, 4, 3, 3, 3, 3, 2, 2)
c) (5, 5, 4, 3, 2, 1)
• Bài 2.2: Một đồ thị có hướng gồm 6 đỉnh có bậc vào lần lượt là (1, 2, 0, 3, 1, 1). Hỏi đồ thị có bao nhiêu cạnh
(cung) và tổng bậc ra của các đỉnh bằng bao nhiêu?
Created using ChatSlide
Bài thuyết trình này sẽ giới thiệu về khái niệm và định lý cắt lối, bao gồm các định nghĩa cơ bản và công thức liên quan. Tiếp theo, chúng ta sẽ khám phá ứng dụng và quy trình kiểm tra tính hợp lệ của đồ thị, cùng với các phương pháp suy luận. Cuối cùng, bài thuyết trình sẽ cung cấp ví dụ thực tiễn và bài tập để củng cố kiến thức, giúp người tham gia hiểu rõ hơn về cách áp dụng lý thuyết vào thực tế.