chương 1 sẽ trình bày những khái niệm tổng quan cơ bản về lý thuyết đồ thị như: định nghĩa một đồ thị, bậc của đồ thị, tính liên thông, đường đi, chu trình của đồ thị … 1.1 Đồ thị vô hướng Định nghĩa 1.1 Đồ thị vô hướng: G = (V, E) gồm một tập V các đỉnh và tập E các cạnh [2] Mỗi cạnh e E được liên kết với một cặp đỉnh v, w ( không kể thứ tự) như hình sau Số hóa bởi Trung tâm Học liệu http://www.1 Đồ thị vô hướng với 7 đỉnh và 8 cạnh Hình 1.1 là một đồ vô hướng bao gồm: - Tập đỉnh V = {1; 2; 3; 4; 5; 6;7} - Tập cạnh E = {(1, 1); (1, 2); (2, 3); (3, 4); (4; 5); (4; 6); (1, 5)} 1.2 Bậc của đồ thị Cho đồ thị G = (V, E) Định nghĩa 1.2 Bậc của đỉnh v V là tổng số cạnh liên thuộc với nó và ký hiệu là d(v). Nếu đỉnh có khuyên thì mỗi khuyên được tính là 2 khi tính bậc, như vậy d(v) = số cạnh liên thuộc + 2* Số khuyên Từ định nghĩa suy ra đỉnh cô lập trong đồ thị đơn là đỉnh có bậc bằng 0 Số bậc lớn nhất của G ký hiệu là ∆(G), số bậc nhỏ nhất của G ký hiệu là δ(G) Đỉnh treo là đỉnh có bậc bằng 1 Định nghĩa 1.3 Số hóa bởi Trung tâm Học liệu http://www.vn/ 5 Cho G = (V, E) là đồ thị có hướng, v V, nửa bậc ra của đỉnh v, ký hiệu là d0(v) là số cung đi ra từ đỉnh v (v là đỉnh đầu) và nửa bậc vào của đỉnh v V, ký hiệu là di(v) là số cung đi tới đỉnh v ( v là đỉnh cuối) Ví dụ1.1: Xét đồ thị ở Hình 1.1 d(1) = 4; d(2) = d(4) = d(5) = 3; d(3) = 2; d(6) = 1; d(7) = 0; Đỉnh 1 có 1 khuyên liên thuộc Đỉnh 7 là đỉnh cô lập Đỉnh 6 là đỉnh treo Định nghĩa 1.4 Đồ thị đầy đủ Kn là đồ thị đơn, đủ n đỉnh ( mỗi cặp đỉnh đều có duy nhất 1 cạnh liên kết) Ví dụ 1.2 Đồ thị đầy đủ với 5 đỉnh Trong Hình 1.2 đồ thị K là một đồ thị đầy đủ có tất cả 5 đỉnh, mỗi cặp đỉnh đều có duy nhất 1 cạnh liên kết.1 Mọi đỉnh của đồ thị Kn có bậc n – 1 và Kn có n(n – 1) / 2 cạnh Số hóa bởi Trung tâm Học liệu http://www.vn/ 6 Định nghĩa 1. Vectơ bậc d(V) của đồ thị G là dãy các bậc của tất cả các đỉnh của G sắp xếp giảm dần. Vectơ v gồm các số tự nhiên gọi là Vectơ đồ thị.
Nếu tồn tại đơn thì đồ thị có vectơ bậc là v. Ghi chú: Từ bổ đề bắt tay suy ra trong vectơ đồ thị số thành phần lẻ là số chẵn.3 Vectơ [3, 3, 2, 2] là Vectơ đồ thị vì nó là vectơ bậc của đồ thị sau 1 2 4 3 Hình 1.3 Đồ thị có vectơ bậc [3, 3, 2, 2] Ngược lại [3, 3, 3, 1] không phải là vectơ đồ thị vì nếu tồn tại đồ thị G(4 đỉnh ) có vectơ bậc là [3, 3, 3, 1] thì sau khi loại đỉnh bậc 1 và cạnh liên thuộc nó ta nhận được đồ thị 3 đỉnh không đơn vì có đỉnh bậc 3, suy ra G cũng không đơn., dn], n 2, là Vectơ n số tự nhiên thỏa mãn n–1 d1 d2. dn 0 Cho v’ là vectơ nhận được từ v bằng cách bỏ thành phần d1 và trừ bớt 1 trong d1 thành phần tiếp theo. Ký hiệu v1 là vectơ v’ trong đó các thành phần được sắp xếp giảm dần.
Khi đó v là vectơ đồ thị khi và chỉ khi v1 là vectơ đồ thị. Số hóa bởi Trung tâm Học liệu http://www.vn/ 7 Sử dụng định lý Hakimi- Havel ta có thể đưa ra thuật toán kiểm tra xem 1 vectơ có phải là vectơ đồ thị không như sau Thuật toán 1.1 Kiểm tra vectơ đồ thị * Đầu vào: vectơ v= [d1, d2, ., dn] gồm n số nguyên giảm dần * Đầu ra: kết luận v là vectơ đồ thị hay v không là vectơ đồ thị * Các bước: Bước 0( khởi tạo): Đặt k: = n và u: = v = [d1, d2, ., dn] Bước 1: Nếu u có thành phần lơn hơn ( k – 1) hoặc nhỏ hơn 0, thì sang bước 4. Bước 2: Nếu các thành phần của u đều là số 0 thì sang bước 5 Bước 3( Bước lặp): Cho u’ là vectơ nhận được từ u bằng cách bỏ thành phần d1 và trừ bớt 1 trong d1 thành phần tiếp theo. Ký hiệu, u1 là vec tơ u’ trong đó các thành phần được sắp xếp giảm dần.
Quay lại bước 1 Bước 4: kết luận: v không phải là vec tơ đồ thị. Kết thúc Bước 5: kết luận: v là vec tơ đồ thị. Kết thúc Ví dụ 1.4: Kiểm tra vectơ v =[5, 4, 4, 3, 3, 3, 2] Bước 0: Đặt k:= 7, u = [5, 4, 4, 3, 3, 3, 2] Bước lặp 1: k:= 7, u = [5, 4, 4, 3, 3, 3, 2], u’= [3, 3, 2, 2, 2, 2], u1= [3, 3, 2, 2, 2, 2] Bước lặp 2: k:= 6, u = [3, 3, 2, 2, 2, 2], u’= [2, 1, 1, 2, 2], u1= [2, 2, 2, 1, 1] Bước lặp 3: k:= 5, u = [2, 2, 2, 1, 1], u’= [1, 1, 1, 1], u1= [1, 1, 1, 1] Bước lặp 4: k:= 4, u = [1, 1, 1, 1], u’= [0, 1, 1], u1= [1, 1, 0] Bước lặp 5: k:= 3, u = [1, 1, 0], u’= [0, 0], u1= [0, 0] Kết luận v là vectơ đồ thị. Đồ thị sau có vectơ bậc là v = [5, 4, 4, 3, 3, 3, 2] Số hóa bởi Trung tâm Học liệu http://www.4 Đồ thị có vectơ bậc [5, 4, 4, 3, 3, 3, 2] 1.3 Đường đi, chu trình, tính liên thông Định nghĩa 1.
Dây từ đỉnh v đến đỉnh w là dãy các đỉnh và cạnh nối tiếp nhau bắt đầu từ đỉnh v và kết thúc tại đỉnh w. Số cạnh trên dãy gọi là độ dài của dãy. Dây từ đỉnh v đến đỉnh n được biểu diễn như sau = (v, e1, v1, e2, v2, …, vn-1, en, w) trong đó vi (i = 1, …, n-1) là các đỉnh trên dãy và ei (i = 1,…,n) là các cạnh trên dãy liên thuộc đỉnh kề trước và sau nó. Các đỉnh và cạnh trên dãy có thể lặp lại.
Đường đi từ đỉnh v đến đỉnh w là dãy từ đỉnh v đến đỉnh w, trong đó có các cạnh không lặp lại. Đường đi sơ cấp là đường đi không đi qua một đỉnh quá 1 lần. Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau. Chu trình sơ cấp là chu trình không đi qua một đỉnh quá 1 lần.
Số hóa bởi Trung tâm Học liệu http://www.vn/ 9 Đồ thị vô hướng gọi là liên thông, nếu mọi cặp đỉnh của nó đều có đường đi nối chúng với nhau.5 Đồ thị vô hướng liên thông Trong Hình 1.5 đồ thị G là đồ thị liên thông có: Đường đi từ đỉnh 1 đến đỉnh 4 là (1, 5) – (5, 4) hoặc (1, 2) – (2, 3) – (3, 4) Chu trình: 1 – 2 – 3 – 4 – 5 – 2 – 1 Chu trình sơ cấp: 1 – 2 – 3 – 4 – 5 – 1 Định lý 1.8 i) Trong đồ thị vô hướng mỗi dãy từ đỉnh v đến w chứa đường đi sơ cấp từ v đến w. ii) Trong đồ thị có hướng mỗi dãy có hướng từ đỉnh v đến w chứa đương đi có hướng sơ cấp từ v đến w.9 Đồ thị G lưỡng phân khi và chỉ khi G không chứa chu trình độ dài lẻ Định nghĩa 1. Đồ thị G’ = (V’, E’) gọi là đồ thị con của G nếu V’ V E’ E Nếu V’ = V thì G’ gọi là đồ thì con phủ của G. Số hóa bởi Trung tâm Học liệu http://www.vn/ 10 Nếu F E, thì ký hiệu G-F là đồ thị con (V, E-F) của G gồm tập đỉnh V và tập cạnh (cung) E-F.
Nếu U V, thì ký hiệu G-U là đồ thị con của G thu được từ G sau khi loại bỏ các đỉnh trong U và các cạnh liên thuộc chúng. Đồ thị con của G sinh bởi U, ký hiệu <U>, là đồ thị (U, EU) với EU = {e E / e liên thuộc đỉnh trong U} Đồ thị con G’ = (V’, E’) của đồ thị (có hướng) G = (V, E) gọi là thành phần liên thông (mạnh) của đồ thị G, nếu nó là đồ thị con liên thông (mạnh) tối đại của G, tức là không tồn tại đồ thị con liên thông (mạnh) G’’ = (V’’, E’’) G’ của G thỏa V’ V’’, E’ E’’.6 Đồ thị vô hướng G với 7 đỉnh 8 cạnh Đồ thị G1 = (V1, E1), với V1 = {1, 2, 5, 7} và E1 = {(1, 1); (1, 2); (1, 5); (2, 5)} là đồ thị con của đồ thị G nhưng không phải thành phần liên thông. Đồ thị G2 = {V-{7}, E} là thành phần liên thông của G. Đồ thị G3 = {7} là thành phần liên thông của G G có 2 thành phần liên thông Số hóa bởi Trung tâm Học liệu http://www.vn/ 11 Ghi chú: Đồ thị là liên thông khi và chỉ khi số thành phần liên thông của nó bằng 1 Định lý 1.11 Cho đồ thị đơn G = (V, E) với n đỉnh, và k thành phần liên thông.
Khi đó số cạnh m của đồ thị thỏa bất đẳng thức (n k )(n k 1) n–k m 2 (n 1)(n 2) Hệ quả 1.2 Mọi đơn đồ thị n đỉnh với số cạnh lớn hơn là liên thông.12 Cho đồ thị G = (V, E) liên thông. Tập cạnh F E gọi là tập hợp tách cạnh của đồ thị liên thông G, nếu G-F không liên thông. Hơn nữa, nếu F là tập hợp tách cạnh cực tiểu(tức không tồn tại F’ F, F’ F, F’ là tập tách cạnh), thì F gọi là tập cắt cạnh. Nếu tập cắt cạnh chỉ có 1 cạnh, thì cạnh đó gọi là cầu.
Đại lượng (G) = min{card(F) / F là tập tách cạnh của G} gọi là số liên thông cạnh của G. Đồ thị G gọi là k cạnh liên thông, nếu mọi tập tách cạnh có ít nhất k cạnh. Từ định nghĩa ta có (G) k k, G là k cạnh liên thông Và (G) = max{k / G là k cạnh liên thông} 1.4 Biểu diễn đồ thị vô hướng 1.1 Ma trận kề Định nghĩa 1.13: Cho đồ thị vô hướng G = (V , E) có n đỉnh theo thứ tự v1, v2, …, vn. Ma trận kề của đồ thị G là ma trận vuông A = (aij)nxn , trong đó aij là cạnh nối vi với vj.
Lưu ý rằng mỗi khuyên được tính là hai cạnh.