Chương II. Lý thuyết đồ thị

Chia sẻ: Lê Trang | Ngày: | Loại File: PPT | Số trang:49

Thêm vào BST

Báo xấu

90
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

ĐỊNH NGHĨA ĐỒ THỊ (GRAPH) Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E) V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh thuộc V.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương II. Lý thuyết đồ thị

Chương II. Lý thuyết đồ thị I. Các khái niệm cơ bản II. Biểu diễn đồ thị III. Tính liên thông IV. Chu trình Euler V. Bài toán tìm đường đi ngắn nhất VI. Đồ thị phẳng VII.Tô màu đồ thị
I. Các khái niệm cơ bản 1. ĐỊNH NGHĨA ĐỒ THỊ (GRAPH)  Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh  đó. Được mô tả hình thức: G = (V, E) V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh  (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh thuộc V. Ví dụ:  Đường Mạng phố máy tính
2. Phân loại đồ thị G được gọi là đơn đồ thị nếu giữa hai đỉnh phân biệt u,  v của V có nhiều nhất là 1 cạnh trong E n ối t ừ u t ới v. G được gọi là đa đồ thị nếu giữa hai đỉnh phân biệt u, v  của V có thể có nhiều hơn 1 cạnh trong E nối t ừ u t ới v G được gọi là giả đồ thị nếu G là đa đồ thị và có thể có  cạnh nối từ một đỉnh đến chính nó. Cạnh đó được gọi là khuyên G được gọi là đồ thị vô hướng nếu các cạnh trong E  không có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cuối. G được gọi là đồ thị có hướng nếu các cạnh trong E có  sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cu ối.
Ví dụ Đơn đồ Đơn đồ thị thị có hướng vô hướng Đa đồ thị Đa đồ thị vô hướng có hướng
3. Cạnh liên thuộc, đỉnh kề, bậc Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e ∈ E, nếu  e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v. Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v,  ký hiệu deg(v) là số cạnh liên thuộc với v. Định lý: Giả sử G = (V, E) là đồ thị vô hướng với m cạnh, khi  đó tổng tất cả các bậc đỉnh trong V sẽ bằng 2m: ∑ deg(v) = 2m v ⊂V Chứng minh: Khi lấy tổng tất cả các bậc đỉnh tức là mỗi cạnh  e = (u, v) bất kỳ sẽ được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra kết quả. Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ là số chẵn 
Đối với đồ thị có hướng G = (V, E). Xét một cung e ∈ E, nếu e  = (u, v) thì đỉnh u khi đó được gọi là đỉnh đầu,đỉnh v được gọi là đỉnh cuối của cung e. Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: bậc ra  của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bậc vào ký hiệu deg-(v) là số cung đi vào đỉnh đó. Định lý: Giả sử G = (V, E) là đồ thị có hướng với m cung, khi  đó tổng tất cả các bậc ra bằng tổng tất cả các bậc vào và bằng m: ∑ deg + (v) = ∑ deg − (v) = m v ⊂V v ⊂V
4. Một số dạng đồ thị đặc biệt a. Đồ thị đầy đủ Kn (n≥1) có n đỉnh và mỗi cặp đỉnh đều có  đúng một cạnh nối. K4 K3 K2
b. Chu trình Cn (n≥3) có n đỉnh v1,v2,..vn và các cạnh  (v1,v2); (v2,v3)....(vn-1,vn) và (vn,v1) C4 C3 c5
c. Đồ thị hình bánh xe  Khi thêm một đỉnh vào giữa chu trình Cn và nối đỉnh này với  các đỉnh của đồ thị Cn ta thu được đồ thị hình bánh xe. W4 W5 W3
d. Đồ thị hình khối Qn có 2n đỉnh, mỗi đỉnh được biểu diễn  bằng xâu nhị phân độ dài n. Hai đỉnh là liền kề nếu các xâu nhị phân biểu diễn chúng khác nhau đúng một bit. 10 11 110 111 Q1 101 100 Q2 Q3 010 011 001 000 01 00
e. Đồ thị phân đôi là đồ thị có 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ị nối 1 đỉnh của V1 với 1 đỉnh của V2 Đồ thị phân đôi đầy đủ Km,n là đồ thị có tập các đỉnh  được phân thành hai tập con tương ứng có m đỉnh và n đỉnh và có cạnh giữa hai đỉnh nếu đỉnh thứ nhất thuộc tập con này, đỉnh thứ hai thuộc tập con kia.
II. Biểu diễn đồ thị 1. Ma trận liền kề (ma trận kề) Giả sử G = (V, E) là một đơn đồ thị có số đỉnh là n, không  mất tính tổng quát có thể coi các đỉnh được đánh số 1, 2, ..., n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông cấp n A = [aij]. Trong đó: aij= 1 nếu (i, j) ∈ E  aij = 0 nếu (i, j) ∉ E  Đối với đa đồ thị thì việc biểu diễn cũng tương tự trên, chỉ có  điều nếu như (i, j) là cạnh thì không phải ta ghi số 1 vào vị trí aij mà là ghi số cạnh nối giữa đỉnh i và đỉnh j
Ví dụ
Ưu điểm và nhược điểm Ưu điểm của ma trận liền kề:   Đơn giản, trực quan, dễ cài đặt trên máy tính  Để kiểm tra xem hai đỉnh (u, v) c ủa đ ồ th ị có k ề nhau hay không, ta chỉ việc kiểm tra bằng một phép so sánh: auv≠ 0. Nhược điểm của ma trận liền kề:   Tiêu tốn bộ nhớ: bất kể số cạnh của đồ th ị là nhi ều hay ít, ma trận liền kề luôn luôn đòi hỏi n 2 ô nhớ để lưu các phần tử ma trận.  Khó làm việc với đồ thị có số lượng đỉnh lớn.
2. Danh sách cạnh Trong trường hợp đồ thị có n đỉnh, m cạnh, ta có thể biểu diễn  đồ thị dưới dạng danh sách cạnh, trong cách biểu diễn này, người ta liệt kê tất cả các cạnh của đồ thị trong một danh sách, mỗi phần tử của danh sách là một cặp (u, v) tương ứng với một cạnh của đồ thị. Danh sách được lưu trong bộ nhớ dưới dạng mảng hoặc danh  sách móc nối. Ví dụ với đồ thị dưới đây:
Ưu điểm của danh sách cạnh:  Trong trường hợp đồ thị có số cạnh tương đối nhỏ: chẳng  hạn m < 6n cách biểu diễn bằng danh sách cạnh sẽ tiết kiệm được không gian lưu trữ, bởi nó chỉ cần 2m ô nhớ để lưu danh sách cạnh. Dể dàng duyệt tất cả các cạnh của đồ thị.  Nhược điểm của danh sách cạnh: Nhược điểm cơ bản của danh sách cạnh là khi ta cần  duyệt tất cả các đỉnh kề với đỉnh v nào đó của đồ thị, thì chẳng có cách nào khác là phải duyệt tất cả các cạnh, lọc ra những cạnh có chứa đỉnh v và xét đỉnh còn lại.
3. Danh sách kề Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị, ta cho  tương ứng với nó một danh sách các đỉnh kề với v. Đỉnh Đỉnh kề 1 2,3,5 2 1,3 3 1,2,4 Ưu điểm 4 3,5 Dễ dàng duyệt tất cả các đỉnh kề với một 5 1,4 đỉnh v cho trước Dễ dàng duyệt tất cả các cạnh Nhược điểm: Cài đặt danh sách kề có phần dài dòng hơn.
III. Tính liên thông Đường đi độ dài n từ đỉnh u đến đỉnh v trong đồ thị là  một dãy các cạnh e1, e2, ..en với (u,x1) = e1; (x1,x2) = e2; .. (xn-1,v) = en Độ dài đường đi bằng với số cạnh mà nó đi qua  Chu trình là đường đi mà nó bắt đầu và kết thúc tại cùng  một đỉnh Chu trình (đường đi) gọi là đơn khi nó không đi qua cùng  1 cạnh quá một lần Một đồ thị được gọi là liên thông nếu có đường đi giữa  mọi cặp đỉnh phân biệt của đồ thị Định lý: Giữa mọi cặp đỉnh của một đồ thị vô hướng  liên thông luôn có đường đi đơn
Một đồ thị không liên thông là hợp của 1 hay nhiều đồ thị con  liên thông. Các đồ thị này được gọi là các thành phần liên thông Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a  tới b và từ b tới a với a, b là hai đỉnh bất kỳ của đồ thị.
IV. Chu trình và đường đi Euler Bài toán bảy cây cầu Euler, còn gọi là Bảy cầu ở Königsberg  nảy sinh từ vấn đề cụ thể. Thành phố Königsberg, Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel, bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Câu hỏi đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không. Năm 1736, Leonhard Euler đã chứng minh rằng điều đó là không thể được. Trong lịch sử toán học, lời giải của Euler cho bài toán bảy cây cầu ở Königsberg được coi là định lý đầu tiên của lý thuyết đồ thị.