Bài giảng môn Lý thuyết đồ thị chương 1: Giới thiệu

Lý thuyết đồ thịChương 1: Giới thiệu Chương 1: Giới thiệu Định nghĩa: Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp các đỉnh (vertices) V (VØ) và các cạnh (edges) E. Mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương ứng với 2 đỉnh v, w thì ta nói v và w là 2 đỉnh liên kết hay kề (adjacent) với nhau và e được gọi là tới các đỉnh v, w. Ký hiệu hay v w. e Chương 1: Giới thiệu Các đỉnh: A, B, C, D Các cạnh: AB, AC, AD, BD, BC Cạnh không phân biệt thứ tự của đỉnh được gọi là cạnh vô hướng. Đồ thị bao gồm các cạnh vô hướng được gọi là đồ thị vô hướng. Chương 1: Giới thiệu Định nghĩa: Cạnh uv tương ứng với 2 đỉnh trùng nhau gọi là vòng (loop) hay khuyên. Chương 1: Giới thiệu Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh gọi là 2 cạnh song song (parallel edge). Chương 1: Giới thiệu Đồ thị không có cạnh song song và khuyên được gọi là đơn đồ thị (simple graph), ngược lại là đa đồ thị (multi graph). Chương 1: Giới thiệu Đồ thị G’ = (V’, E’) gọi là 1 đồ thị con (sub graph) của đồ thị G = (V, E) nếu V’  V và E’  E. B’ C’ Chương 1: Giới thiệu Đồ thị có số đỉnh và số cạnh hữu hạn gọi là đồ thị hữu hạn (finite graph), ngược lại là đồ thị vô hạn (infinite graph). Chương 1: Giới thiệu Biểu đồ Chương 1: Giới thiệu Bậc của một đỉnh Bậc (degree) của một đỉnh v, ký hiệu là d(v), chính là số cạnh tới đỉnh đó. Mỗi vòng tại một đỉnh sẽ được xem như 2 cạnh tới đỉnh đó. Nếu d(v) = 0, v được gọi là đỉnh cô lập (isolated vertex). Nếu d(v) = 1, v được gọi là đỉnh treo (perdant vertex), cạnh tới đỉnh treo được gọi là cạnh treo (perdant edge). Đồ thị mà mọi đỉnh đều là đỉnh cô lập được gọi là đồ thị rỗng (null graph). Chương 1: Giới thiệu Bậc của các đỉnh: A: 2 B: 5 C: 0 (đỉnh cô lập) D: 2 E: 1 (đỉnh treo) F: 4 G G’ Chương 1: Giới thiệu Đồ thị mà mọi cặp đỉnh đều kề nhau được gọi là đồ thị đầy đủ (complete graph). Đồ thị đầy đủ có n đỉnh được ký hiệu là Kn. Chương 1: Giới thiệu Đồ thị bù của một đồ thị G, ký hiệu là G, là một đồ thị có cùng đỉnh với G và có các cạnh là những cạnh mà ta phải bổ sung vàođể G trở thành đầy đủ. Chương 1: Giới thiệu Định lý 1.1: Với mọi đồ thị G = (V, E), ta có: Hệ quả 1.1: Tổng số bậc của các đỉnh bậc lẻ trong 1 đồ thị là 1 số chẵn Hệ quả 1.2: Mọi đồ thị đều có một số chẵn các đỉnh bậc lẻ. Chương 1: Giới thiệu Hệ quả 1.3: Đồ thị Kn có n(n-1) cạnh. Chương 1: Giới thiệu Biểu diễn đồ thị - Danh sách kề A B B D E B A A C D E C C C B D D A B C E E A B D Chương 1: Giới thiệu Biểu diễn đồ thị - Ma trận kề: A B C D E A 0 2 0 1 1 B 2 0 1 1 1 C 0 1 2 1 0 D 1 1 1 0 1 E 1 1 0 1 0 Chương 1: Giới thiệu Định lý 1.2: Tổng các phần tử trên hàng (hoặc cột) thứ i của ma trận kề của đồ thị G có n đỉnh bằng bậc của đỉnh vi của đồ thị ấy, nghĩa là: Chương 1: Giới thiệu Đường đi và chu trình Cho một đồ thị G. Một đường đi P trong G là một dãy các cạnh nối tiếp có chung đầu mút v0v1, v1v2,..., vk-1vk. Ký hiệu: P = v0 v1 ... vk hay P = v0v1...vk k (số cạnh tạo thành P) được gọi là chiều dài của P. Ký hiệu l(P) = k. e1 e2 ek Chương 1: Giới thiệu Đường đi P: EACB l(P) = 3 Chương 1: Giới thiệu Một chu trình (cycle) trong G là một đường đi trong G có dạng c=v0v1...vk-1v0 với l(c)  1. Một đường đi (hoặc chu trình) được gọi là sơ cấp nếu nó không đi qua đỉnh nào quá một lần. Một đường đi (hoặc chu trình) được gọi là đơn giản nếu nó không đi qua cạnh nào quá một lần. Chương 1: Giới thiệu ABCA là một chu trình đơn giản và sơ cấp. ACB là một đường đi đơn giản và sơ cấp. EABCAD là một đường đi đơn giản nhưng không sơ cấp. EACBADE là một chu trình đơn giản nhưng không sơ cấp. Chương 1: Giới thiệu Liên thông Một đồ thị được gọi là liên thông (connected) nếu mọi cặp đỉnh của nó đều được nối với nhau bởi một đường đi. Chương 1: Giới thiệu Xét G = (V, E) là một đồ thị vô hướng. Trên tập hợp V, ta định nghĩa một quan hệ ~ như sau: v, w V, v ~ w  có 1 đường đi trong G giữa v và w. Khi đó: ~ là một quan hệ tương đương trên V và ~ phân hoạch V thành các lớp tương đương. Mỗi lớp tương đương này ứng với một đồ thị con liên thông của G và được gọi là một thành phần liên thông (connected component) của G. Chương 1: Giới thiệu Hai thành phần liên thông bất kỳ của G thì tách biệt. Chương 1: Giới thiệu Định lý 1.3: Một đơn đồ thị G có n đỉnh và k thành phần thì có tối đa là (n – k)(n – k + 1) cạnh. Chương 1: Giới thiệu Đẳng hình Hai đồ thị G = (V, E) và G’ = (V’, E’) gọi là đẳng hình (isomorphic) với nhau nếu có 1 song ánh giữa hai tập hợp V, V’ và 1 song ánh giữa 2 tập hợp E, E’ sao cho nếu cạnh e = vw  E tương ứng với cạnh e’ = v’w’  E’ thì cặp đỉnh v, w  V cũng là tương ứng của cặp đỉnh v’, w’  V’. Chương 1: Giới thiệu A B C D E A’ B’ C’ D’ E’ Chương 1: Giới thiệu Đồ thị có hướng Nếu mỗi cạnh e  E của G được xác định bởi một cặp có thứ tự (v, w) của 2 định v, w  V thì ta nói e là 1 cạnh có hướng từ v đến w, ký hiệu e = vw, và đồ thị G khi này được gọi là một đồ thị có hướng (directed graph). v được gọi là đỉnh đầu (initial vertex). w được gọi là đỉnh cuối (terminal vertex). Chương 1: Giới thiệu e được gọi là tới ngoài (incident out) đỉnh v và tới trong (incident in) đỉnh w. Số cạnh tới ngoài đỉnh v gọi là bậc ngoài (out degree) của v, ký hiệu dout(v); số cạnh tới trong đỉnh w gọi là bậc trong (in degree) của w, ký hiệu din(w). Chương 1: Giới thiệu Một đồ thị có hướng gọi là cân bằng (balanced) nếu mọi đỉnh của nó đều có bậc trong và bậc ngoài bằng nhau. A B C D E Chương 1: Giới thiệu Đồ thị có hướng G gọi là liên thông nếu đồ thị vô hướng tương ứng của nó là liên thông. Một đường đi P trong một đồ thị có hướng G là một dãy hữu hạn các cạnh nối tiếp v0v1, v1v2, ..., vk-1vk. P còn được viết là: v0v1...vk. Chương 1: Giới thiệu Một đồ thị có hướng G gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt v, w luôn luôn tồn tại 1 đường đi nối v với w. Chương 1: Giới thiệu Một chu trình trong đồ thị có hướng G là một đường đi trong G có dạng v0v1...vkv0. Đồ thị có hướng G gọi là đầy đủ nếu đồ thị vô hướng tương ứng của nó là đầy đủ. Chương 1: Giới thiệu Định lý 1.4: Trong một đồ thị có hướng G, tổng các bậc trong và tổng các bậc ngoài của các đỉnh thì bằng nhau và cùng bằng số cạnh của G. Định lý 1.5: Tổng số các phần tử trên hàng (cột) thứ i của ma trận liên kết của đồ thị có hướng G bằng bậc ngoài (trong) của đỉnh vi, nghĩa là: và Chương 1: Giới thiệu Tóm tắt Đồ thị, các loại đồ thị (có hướng, vô hướng, đơn, đa, đầy đủ). Bậc của đỉnh, đồ thị cân bằng. Biểu diễn một đồ thị (danh sách kề, ma trận kề). Đẳng hình. Đường đi, chu trình. Miền liên thông, liên thông mạnh.