Đang chuẩn bị liên kết để tải về tài liệu:
ĐỒ THỊ - PHẦN 3

Tài liệu tham khảo dành cho giáo viên, sinh viên cao đẳng, đại học chuyên môn toán học - Giáo trình toán cao cấp, giúp bạn củng cố và nâng cao kiến thức cũng như trình độ toán học của mình. | ĐÒ THỊ - PHẦN 3 CÁC ĐÒ THỊ MỚI TỪ ĐÒ THỊ CŨ. 3.5.1. Định nghĩa Cho hai đồ thị G1 V1 E1 và G2 V2 E2 . Ta nói G2 là đồ thị con của G1 nếu V2 G V1 và E2 G E1. Trong trường hợp V1 V2 thì G2 gọi là con bao trùm của G1. Thí dụ 14 a d 1 a a a a d a e e c c b b G2 e e b c b c G3 a d b c a d G1 d a b b c c b c b b G G4 G5 G1 G2 G3 và G4 là các đồ thị con của G trong đó G2 và G4 là đồ thị con bao trùm của G còn G5 không phải là đồ thị con của G. 3.5.2. Định nghĩa Hợp của hai đơn đồ thị G1 V1 E1 và G2 V2 E2 là một đơn đồ thị có tập các đỉnh là V1 u V2 và tập các cạnh là E1 u E2 ký hiệu là G1 u G2. Thí dụ 15 G1 G2 G1OG2 .ixz. . _ . . . . 3.5.3 Định nghĩa Đơn đồ thị G V E được gọi là đồ thị bù của đơn đồ thị G V E nếu G và G không có cạnh chung nào E n E 0 và G u G là đồ thị đầy đủ. Dễ thấy rằng nếu G là bù của G thì G cũng là bù của G . Khi đó ta nói hai đồ thị là bù nhau. Thí dụ 16 G G G1 G1 Hai đồ thị G và G là bù nhau và hai đồ thị G1 và G1 là bù nhau. 3.6. TÍNH LIÊN THÔNG. 3.6.1. Định nghĩa Đường đi độ dài n từ đỉnh u đến đỉnh v với n là một số nguyên dương trong đồ thị giả đồ thị vô hướng hoặc đa đồ thị có hướng G V E là một dãy các cạnh hoặc cung e1 e2 . en của đồ thị sao cho e1 x0 x1 e2 x1 x2 . en xn-1 xn với x0 u và xn v. Khi đồ thị không có cạnh hoặc cung bội ta ký hiệu đường đi này bằng dãy các đỉnh x0 x1 . xn. Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh. Đường đi hoặc chu trình gọi là đơn nếu nó không chứa cùng một cạnh hoặc cung quá một .