tailieunhanh - ĐỒ THỊ - PHẦN 2

Tham khảo tài liệu 'đồ thị - phần 2', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | ĐÒ THỊ - PHẦN 2 NHỮNG ĐƠN ĐÒ THỊ ĐẶC BIỆT. . Đô thị đây đủ Đồ thị đầy đủ n đỉnh ký hiệu là Kn là đơn đồ thị mà hai K3 K5 . Đô 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ý hiệu là Cn. Như đỉnh của Cn có bậc là 2. Thí du 7 C3 C4 C5 C6 . Đô 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. Thí dụ 8 W6 W3 W4 W5 . Đồ 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ập phương ký hiệu là Qn. Như vậy mỗi đỉnh của Qn có bậc là n và số cạnh của Qn là từ công thức 2 E E deg v . veV Thí dụ 9 Q1 Q3 . Đồ thị phân đôi đồ thị hai phe Đơn đồ thị G V E sao cho V V V2 V1nV2 0 V1 0 V2 0 và mỗi cạnh của G được nối một đỉnh trong VI và một đỉnh trong V2 được gọi là đồ thị phân .