Xem mẫu

  1. Lý thuyết đồ thị Chương 1: Giới thiệu 1
  2. 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ý e = vw hay v e w. hiệu 2
  3. Chương 1: Giới thiệu A Các đỉnh: A, B, C, D  Các cạnh: AB, AC, AD,  BD, BC B D C 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. 3
  4. 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. B A C 4
  5. 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). B A C 5
  6. 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). B A B A C C D 6
  7. 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. A A’ E’ B’ E B C’ D C 7
  8. 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). 8
  9. Chương 1: Giới thiệu Biểu đồ  A’ A B B’ A” C’ E’ D C B” C” D’ 9
  10. 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). 10
  11. Chương 1: Giới thiệu Bậc của các đỉnh:  A B C A: 2 G B: 5 F D C: 0 (đỉnh cô lập) E D: 2 Y X E: 1 (đỉnh treo) F: 4 G’ Z T 11
  12. 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. A E B D C 12
  13. 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 đủ. G G 13
  14. Chương 1: Giới thiệu Định lý 1.1:  Với mọi đồ thị G = (V, E), ta có: ∑d (v) = 2 E v∈V 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 ẻ. 14
  15. Chương 1: Giới thiệu Hệ quả 1.3:  1 Đồ thị Kn có n(n-1) cạnh. 2 15
  16. Chương 1: Giới thiệu Biểu diễn đồ thị - Danh sách kề  ABBDE C BAACDE CCCBD B D DABCE EABD A E 16
  17. Chương 1: Giới thiệu Biểu diễn đồ thị - Ma trận kề:  C A B C D E A 0 2 0 1 1 B 2 0 1 1 1 B D C 0 1 2 1 0 D 1 1 1 0 1 E 1 1 0 1 0 A E 17
  18. 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à: n n d (vi ) = ∑ mik = ∑ mki k =1 k =1 18
  19. 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 e1 v1 e2 ... ek 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. 19
  20. Chương 1: Giới thiệu Đường đi P: EACB  A l(P) = 3  B E D C 20
nguon tai.lieu . vn