tailieunhanh - 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. | Thí dụ 5 CHƯƠNG III ĐÒ THỊ degt vi 2 dego vi 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 vô 0 dego vG 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. . Mệnh đề Cho G V E là một đồ thị có hướng. Khi đó E deg t v E deg o V E . Chứ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. . NHỮNG ĐƠN ĐÒ THỊ ĐẶC BIỆT. . Đồ thị đầy đủ Đồ thị đầy đủ n đỉnh ký hiệu là Kn là đơn đồ thị V1 V1 dụ 6 V2 3 V4 K2 K1 V2 J V3 V1 V1 V4 V2 hai đỉnh phân biệt bất kỳ của nó luôn liềnkề. Như vậy Kn có yi ------------------------------------ v21 2 h và mỗi đỉnh của Kn có bậc là n-1. 2C V3 cạnh và mỗi đỉnh của Kn có bậc là n-1. Thí dụ 6 K1 K2 K3 K4 k5 VỊ . Đồ thị vòng Đơn đồ thị n đỉnh v1 V2 . Vn n 3 Và n cạnh V1 V2 V2 Vj . Vn-1 Vn Vn V1 được gọi là đồ thị vòng kýhệmlà Cn. Như vậy mỗi đỉnh của Cn có bậc là 2 Thí dụ 7 V1 V2 V6 V2 V3 V2 V4 V3 V4 V3 C3 C4 C5 C6 . Đồ thị bánh xe Từ đồ thị vòng Cn thêm vào đỉnh vn i và các cạnh vn i 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. W3 _ Iv1J Thí dụ 8. y yT Ív4 1 W4 W5 W6 . Đồ 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ị .