›
›

Bài giảng Lý thuyết đồ thị - Chương 1: Đại cương về đồ thị

ppt 39 trang phuongnguyen 2920
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 1: Đại cương về đồ thị", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_ly_thuyet_do_thi_chuong_1_dai_cuong_ve_do_thi.ppt

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 1: Đại cương về đồ thị

  1. Chương 1 Đại cương về đồ thị
  2. Phần 1.1. Định nghĩa đồ thị
  3. Định nghĩa đồ thị Định nghĩa. Một đơn đồ thị vô hướng là một bộ G= , trong đó: u V  là tập hợp hữu hạn gồm các đỉnh của đồ thị. u E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. VD: a. Đơn đồ thị vô hướng b. Không phải đơn đồ thị vô hướng do c. Không phải đơn có các cặp cạnh nối đồ thị vô hướng do cùng một cặp đỉnh có cạnh nối một đỉnh với chính nó. Lý thuyết đồ thị 6/14/2021 3
  4. Định nghĩa đồ thị (tt) Định nghĩa. Một đa đồ thị vô hướng là một bộ G= , trong đó: u V  là tập hợp hữu hạn gồm các đỉnh của đồ thị. u E là danh sách các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Chú ý: u Các cạnh cùng nối giữa một cặp đỉnh được gọi là các cạnh song song. u Nếu đồ thị có cạnh nối từ một đỉnh với chính nó (cạnh này được gọi là khuyên) thì đồ thị được gọi là giả đồ thị vô hướng. Lý thuyết đồ thị 6/14/2021 4
  5. Định nghĩa đồ thị (tt) VD: e2 e1 e a. Đa đồ thị vô b. Giả đồ thị vô hướng. e1 và e2 là các cạnh song song. hướng. e là khuyên Chú ý: Trong một số tài liệu có thể có nhập khái niệm đa đồ thị và giả đồ thị, khi đó, chỉ có một tên gọi chung là đa đồ thị cho cả hai loại. Lý thuyết đồ thị 6/14/2021 5
  6. Định nghĩa đồ thị (tt) Định nghĩa. Một đơn đồ thị có hướng là một bộ G= , trong đó: u V  là tập hợp hữu hạn gồm các đỉnh của đồ thị. u E là tập hợp các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. VD: Lý thuyết đồ thị 6/14/2021 6
  7. Định nghĩa đồ thị (tt) Định nghĩa. Một đa đồ thị vô hướng là một bộ G= , trong đó: u V  là tập hợp hữu hạn gồm các đỉnh của đồ thị. u E là danh sách các cặp không có thứ tự gồm hai phần tử của V gọi là các cung. Chú ý: u Các cung cùng nối giữa một cặp đỉnh được gọi là các cung song song (parallel arcs). u Nếu đồ thị có cung nối từ một đỉnh với chính nó (cung này được gọi là khuyên) thì đồ thị được gọi là giả đồ thị có hướng. Lý thuyết đồ thị 6/14/2021 7
  8. Định nghĩa đồ thị (tt) Ví dụ: e2 e1 e a. Đa đồ thị có hướng. e1 và e2 là các b. Giả đồ thị có cung song song. hướng. e là khuyên Chú ý: Đồ thị sau vẫn được coi là đơn đồ thị có hướng vì e1 và e2, e3 và e4 không phải là 2 cung song song (do khác hướng). e4 e3 e2 e1 Lý thuyết đồ thị 6/14/2021 8
  9. Một số ví dụ về đồ thị: Detroit New York San Francisco Chicago Denver Washington Los Angeles Đơn đồ thị có hướng Giả đồ thị vô hướng Detroit New York San Francisco Chicago Denver Washington Los Angeles Đơn đồ thị vô hướng Đơn đồ thị có hướng Lý thuyết đồ thị 6/14/2021 9
  10. Thuật ngữ Việt - Anh Đồ thị có hướng Directed graph Đồ thị vô hướng Undirected graph Đơn đồ thị Simple graph Đa đồ thị Multi-graph Giả đồ thị Pseudo-graph Đỉnh Vertex / Vertices Cạnh Edge Cung Arc Cạnh song song Parallel Edges Cung song song Parallel Arcs Khuyên Loop Lý thuyết đồ thị 6/14/2021 10
  11. Phần 1.2. Các mô hình đồ thị
  12. Đồ thị lấn tổ (niche overlap graph) n Đơn đồ thị có hướng n Mỗi đỉnh biểu diễn một loài n Hai đỉnh được nối một cạnh nếu hai loài tương ứng cạnh tranh nhau về nguồn thức ăn. Gấu Đại bàng trúc Chim cú Sóc Thú có túi Quạ Chuột Chuột Chim gõ chù kiến Lý thuyết đồ thị 6/14/2021 12
  13. Đồ thị ảnh hưởng (influence graph) n Đơn đồ thị có hướng n Mỗi đỉnh tương ứng với một người n Mỗi cung biểu diễn cho sự ảnh hưởng của người này lên người kia Linda Brian Peter Fred Lita Lý thuyết đồ thị 6/14/2021 13
  14. Thi đấu vòng tròn (Round Robin) n Đơn đồ thị có hướng n Mỗi đỉnh biểu diễn cho một đội n Cung (a,b) biểu diễn cho trận đấu giữa hai đội a và b với kết quả đội a thắng đội b Brazil Italy Holland England Lý thuyết đồ thị 6/14/2021 14
  15. Đồ thị xác định ưu tiên (precedence graph) n Đơn đồ thị có hướng n Mỗi đỉnh thể hiện một công việc n Cung (a,b) thể hiện việc a phải được thực hiện trước việc b VD: S1 S2 S1: a:=0 S2: b:=1 S : c:=a+1 3 S3 S4 S4: d:=a+b S5: e:=d+1 S6: e:=c+d S5 S6 Lý thuyết đồ thị 6/14/2021 15
  16. Phần 1.3. Một số thuật ngữ cơ bản của đồ thị
  17. Những thuật ngữ cơ sở n Xét đồ thị vô hướng G = u Nếu e = (u,v) là một cạnh của G thì: l Hai đỉnh u, v được gọi là hai đỉnh kề nhau l Cạnh e được gọi là cạnh liên thuộc với đỉnh u và đỉnh v l Đỉnh u, đỉnh v được gọi là đỉnh đầu của cạnh e u Bậc của một đỉnh v (deg(v)) u là số cạnh liên thuộc với nó. e u VD: deg(0) = 3, deg(5) = 4, deg(2) = 6, deg(8) = 2, v Lý thuyết đồ thị 6/14/2021 17
  18. Những thuật ngữ cơ sở (tt) n Xét đồ thị có hướng G = u Nếu e = (u,v) là một cung của G thì: l Đỉnh v được gọi là đỉnh kề của đỉnh u l Cung e được gọi là cung đi ra khỏi đỉnh u và là cung đi vào đỉnh v l Đỉnh u được gọi là đỉnh đầu của cung e, đỉnh v được gọi là đỉnh cuối của cạnh e u u Bán bậc ra của một đỉnh v (deg+(v)) e là số cung đi ra khỏi nó. t v u Bán bậc vào của một đỉnh v (deg-(v)) là số cung đi vào nó. u VD: deg+(t) = 1, deg-(t) = 1, s deg+(v) = 0, deg-(0) = 3, x Lý thuyết đồ thị 6/14/2021 18
  19. Những thuật ngữ cơ sở (tt) n Đỉnh có bậc 0 được gọi là đỉnh cô lập n Đỉnh có bậc 1 được gọi là đỉnh treo n Định lý. Xét đồ thị vô hướng G = . Khi đó, tổng bậc của tất cả các đỉnh của đồ thị sẽ bằng hai lần số cạnh của nó. Lý thuyết đồ thị 6/14/2021 19
  20. Những thuật ngữ cơ sở (tt) n Định lý. Xét đồ thị có hướng G = . Khi đó, tổng bán bậc ra của tất cả các đỉnh sẽ bằng tổng bán bậc vào của tất cả các đỉnh và bằng số cung của đồ thị. Lý thuyết đồ thị 6/14/2021 20
  21. Đồ thị con n Định nghĩa. Xét đồ thị G = . Đồ thị H = là một đồ thị con của G nếu và chỉ nếu mọi đỉnh của H cũng là đỉnh của G và mọi cạnh/cung của H cũng là cạnh/cung của G. (W  V, F  E). VD: 2 1 3 4 5 1 2 1 2 3 1 2 3 4 5 4 5 4 5 Đồ thị con của G Đồ thị con của G Không là đồ thị con của G Lý thuyết đồ thị 6/14/2021 21
  22. Thuật ngữ Việt - Anh Kề Adjacent Liên thuộc incident Đỉnh đầu mút Endpoint Đỉnh cô lập Isolated vertex Đỉnh treo Pendant vertex Bậc của đỉnh Degree of Vertex Đỉnh đầu Initial vertex Đỉnh cuối End vertex Bán bậc ra Out-degree Bán bậc vào In-degree Đồ thị con Subgraph Lý thuyết đồ thị 6/14/2021 22
  23. Phần 1.5. Đường đi – Chu trình – Sự liên thông
  24. Đường đi Định nghĩa. Xét đồ thị G = . Một đường đi độ dài n từ u tới v, n là một số nguyên dương, trong một đồ thị là một dãy: u = x0 x1 x2 xn = v sao cho i {0, ,n-1}, (xi, xi+1) E VD: Các đường đi từ 1 đến 5: d1: 1 2 5 Độ dài 2 Độ dài 6 d2: 1 2 4 3 9 2 5 d3: 1 9 2 3 9 2 5 Độ dài 6 Lý thuyết đồ thị 6/14/2021 24
  25. Chu trình Định nghĩa. Xét đồ thị G = . Một chu trình độ dài n (n là một số nguyên dương) là một đường đi có độ dài n với đỉnh đầu và đỉnh cuối trùng nhau VD: Các chu trình trong đồ thị: C1: 1 2 9 1 Độ dài 2 C2: 1 9 0 3 9 2 1 Độ dài 6 C3: 1 9 2 3 9 1 Độ dài 5 Lý thuyết đồ thị 6/14/2021 25
  26. Đường đi – Chu trình n Một đường đi (chu trình) được gọi là đường đi đơn (chu trình đơn) nếu nó không lặp lại cạnh nào. n Một đường đi (chu trình) được gọi là đường đi sơ cấp (chu trình sơ cấp) nếu nó không lặp lại đỉnh nào. VD: Đường đi sơ cấp (hiển nhiên đơn) d1: 1 2 5 Đường đi đơn (không sơ cấp) d2: 1 2 4 3 9 2 5 Đường đi không đơn (không sơ cấp) d3: 1 9 2 3 9 2 5 C1: 1 2 9 1 Chu trình sơ cấp (hiển nhiên đơn) Chu trình đơn (không sơ cấp) C2: 1 9 0 3 9 2 1 Chu trình không đơn (không sơ cấp) C3: 1 9 2 3 9 1 Lý thuyết đồ thị 6/14/2021 26
  27. Sự liên thông Định nghĩa. Xét đồ thị vô hướng G = . G được gọi là đồ thị liên thông nếu luôn tồn tại đường đi giữa hai đỉnh bất kỳ của G. VD: Đồ thị vô hướng liên thông Đồ thị vô hướng không liên thông Lý thuyết đồ thị 6/14/2021 27
  28. Sự liên thông (tt) n Một đồ thị không liên thông là hợp của nhiều đồ thị con liên thông rời nhau. Mỗi đồ thị con này được gọi là một thành phần liên thông của đồ thị ban đầu. Đồ thị trên có 3 thành phần liên thông Lý thuyết đồ thị 6/14/2021 28
  29. Sự liên thông (tt) n Định nghĩa. Xét đồ thị vô hướng, liên thông G = . u Đỉnh v được gọi là đỉnh cắt (hay điểm khớp) nếu việc loại bỏ nó (cùng với các cạnh liên thuộc) ra khỏi đồ thị sẽ làm đồ thị mất tính liên thông. u Cạnh e được gọi là cạnh cắt (hay cầu) nếu việc loại bỏ nó ra khỏi đồ thị sẽ làm đồ thị mất tính liên thông. VD: Đỉnh cắt: e, x, y Cạnh cắt: (e,x), (y,w) Lý thuyết đồ thị 6/14/2021 29
  30. Sự liên thông (tt) Định nghĩa. Xét đồ thị có hướng G = . u G được gọi là đồ thị liên thông mạnh nếu luôn tồn tại đường đi giữa hai đỉnh bất kỳ của G. u G được gọi là đồ thị liên thông yếu nếu đồ thị vô hướng tương ứng với nó (biến các cung 1 chiều thành cạnh 2 chiều) là đồ thị liên thông. VD: ĐồĐồ thịthị cócó hướnghướng khôngliên thông liên Đồ thị có hướng không liên mạnhthông (hiển mạnh nhiên (nhưng cũng là là liên liên thông yếu (hiển nhiên không Lý thuyết đồ thịthông yếu) 6/14/2021 liên thông mạnh) 30
  31. Thuật ngữ Việt - Anh Đường đi Path Chu trình Circuit Đường đi (chu trình) Simple Path đơn (Circuit) Liên thông Connected Liên thông mạnh Strongly connected Liên thông yếu Weakly connected Đỉnh cắt Cut Vertex Cạnh cắt Cut Edge Thành phần liên Connected thông components Lý thuyết đồ thị 6/14/2021 31
  32. Phần 1.4. Một số đơn đồ thị đặc biệt
  33. Đồ thị đầy đủ - Kn n Đặc điểm: u Đồ thị vô hướng u Hai đỉnh bất kỳ luôn kề nhau n Tính chất u n đỉnh u Các đỉnh đều có bậc n – 1 u Số cạnh: Lý thuyết đồ thị 6/14/2021 33
  34. Chu trình vòng - Cn n Đặc điểm: u Đồ thị vô hướng u Các đỉnh nối với nhau theo vòng tròn n Tính chất u n đỉnh u Các đỉnh đều có bậc 2 u Số cạnh: n Lý thuyết đồ thị 6/14/2021 34
  35. Đồ thị bánh xe - Wn n Đặc điểm: n Tính chất: u Đồ thị vô hướng u n+1 đỉnh u Hai đỉnh bất kỳ luôn kề nhau u n đỉnh bậc 3, 1 đỉnh bậc n u Số cạnh: 2n Lý thuyết đồ thị 6/14/2021 35
  36. Đồ thị lập phương - Wn n Đặc điểm: n Tính chất: u Đồ thị vô hướng u 2n đỉnh u Các đỉnh biểu diễn cho các u Các đỉnh đều có dãy n bit. bậc n – 1 u Số cạnh: (n-1).2n-1 Lý thuyết đồ thị 6/14/2021 36
  37. Đồ thị phân đôi (đồ thị khả phân) n Định nghĩa. Một đồ thị G được gọi là đồ thị phân đôi (bipartite graph) nếu tập các đỉnh V có thể phân làm hai tập con không rỗng, rời nhau V1 và V2 sao cho mỗi cạnh của đồ thị luôn nối một đỉnh trong V1 với một đỉnh trong V2. Lý thuyết đồ thị 6/14/2021 37
  38. Đồ thị phân đôi đầy đủ n Đồ thị phân đôi đầy đủ: u Đồ thị phân đôi u Mọi cặp đỉnh giữa hai tập V1 và V2 đều được nối với nhau. V2 V1 n Tính chất: Km,n u m + n đỉnh u mxn cạnh. u m đỉnh bậc n, và n đỉnh bậc m K3x4 Lý thuyết đồ thị 6/14/2021 38
  39. Ví dụ: n Hãy cho biết trong các đồ thị sau, đồ thị nào là đồ thị phân đôi: ? Đồ thị phân đôi Không là đồ thị phân đôi Định lý: Một đồ thị vô hướng là đồ thị phân đôi khi và chỉ khi nó không chứa chu trình với độ dài lẻ Lý thuyết đồ thị 6/14/2021 39