GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG III ĐỒ THỊ_2

degt(v6) = 0, dego(v6) = 0. Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung treo.
Nội dung trích xuất từ tài liệu:
GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG III ĐỒ THỊ_2 CHƯƠNG III ĐỒ THỊThí dụ 5: v2 v3 v6 v4 v5 v1degt(v1) = 2, dego(v1) = 3,degt(v2) = 5, dego(v2) = 1,degt(v3) = 2, dego(v3) = 4,degt(v4) = 1, deg0(v4) = 3,degt(v5) = 1, dego(v5) = 0,degt(v6) = 0, dego(v6) = 0. Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. Đỉnh cóbậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối làđỉnh treo gọi là cung treo.3.2.8. Mệnh đề: Cho G =(V, E) là một đồ thị có hướng. Khi đó  deg t (v)   deg o (v) = |E|. vV vVChứng minh: Kết quả có ngay là vì mỗi cung được tính một lần chođỉnh đầu và một lần cho đỉnh cuối.3.3. NHỮNG ĐƠN ĐỒ THỊ ĐẶC BIỆT.3.3.1. Đồ thị đầy đủ: Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ thị n(n  1)mà hai đỉnh phân biệt bất kỳ của nó luôn liền kề. Như vậy, Kn có 2 v1 v2cạnh và mỗi đỉnh của Kn có bậc là n1. v3 v1 v1Thí dụ 6: v5 v1 v2 v4 v2 v3 v2 v1 v3K1 K2 V4 K3 K4K5 v13.3.2. Đồ thị vòng: Đơn đồ thị n đỉnh v1, v2, ..., vn (n3) và n cạnh(v1,v2), (v2,v3), ..., (vn-1,vn), (vn,v1) được gọi là đồ thị vòng, ký v1 ệu là Cn. hiNhư vậy, mỗi đỉnh của Cn có bậc là 2. v1Thí dụ 7: v1 v2 v6 v5 v2 v3 v2 v4 v3 v2 v3 v4 v3 v5 v4 C3 C4 C5C63.3.3. Đồ thị bánh xe:Từ đồ thị vòng Cn, thêm vào đỉnh vn+1 và các cạnh(vn+1,v1), (vn+1,v2), ..., (vn+1,vn), ta nhận được đơn đồ thị gọi là đồ thịbánh xe, ký hiệu là Wn. Như vậy, đồ thị Wn có n+1 đỉnh, 2n cạnh, mộtđỉnh bậc n và n đỉnh bậc 3. v1 v1 v1Thí dụ 8: v1 v2 v6 v5 v2 v2 v7 v6 v5 v3 v2 v4 v3 v4 v4 v3 v5 v3 v4 W3 W4 W5W63.3.4. Đồ thị lập phương: Đơn đồ thị 2n đỉnh, tương ứng với 2n xâu nhịphân độ dài n và hai đỉnh kề nhau khi và chỉ khi 2 xâu nhị phân tươngứng với hai đỉnh này chỉ khác nhau đúng một bit được gọi là đồ thị lậpphương, ký hiệu là Qn. Như vậy, mỗi đỉnh của Qn có bậc là n và số cạnhcủa Qn là n.2n-1 (từ công thức 2|E| =  deg(v) ). vV 110Thí dụ 9: 111 10 11 0 1 100 101 00 01 Q1 Q2 011 010 001 000 ...