›
›

Bài giảng Toán rời rạc 2 - Chương 1: Khái niệm về đồ thị

Download
KHÁI NIỆM VỀ ĐỒ THỊ  
Toán rời rạc 2  
Nội dung  
• Định nghĩa đồ thị  
• Một số thuật ngữ cơ bản trên đồ thị vô hướng  
• Một số thuật ngữ cơ bản trên đồ thị có hướng  
• Một số dạng đồ thị đặc biệt  
• Bài tập  
2
Định nghĩa đồ thị  
Đơn đồ thị vô hướng  
• Đơn đồ thị vô hướng G= < V, E> bao gồm V là tập các  
đỉnh, E là tậ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.  
4
Đa đồ thị vô hướng  
• Đa đồ thị vô hướng G = <V, E> bao gồm V là tập các  
đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử  
khác nhau của V gọi là tập các cạnh.  
• e1E, e2E được gọi là cạnh bội nếu chúng cùng  
tương ứng với một cặp đỉnh.  
5
Giả đồ thị vô hướng  
• Giả đồ thị vô hướng G = <V, E> bao gồm V là tập đỉnh, E  
là họ các cặp không có thứ tự gồm hai phần tử (hai phần  
tử không nhất thiết phải khác nhau) trong V được gọi là  
các cạnh.  
• Cạnh e được gọi là khuyên nếu có dạng e =(u, u), trong  
đó u là đỉnh nào đó thuộc V.  
6
Đơn đồ thị có hướng  
• Đơn đồ thị có hướng G = <V, E> bao gồm V là tập các  
đỉnh, E là tập các cặp có thứ tự gồm hai phần tử của V  
gọi là các cung.  
7
Đa đồ thị có hướng  
• Đa đồ thị có hướng G = <V, E> bao gồm V là tập đỉnh, E  
là cặp có thứ tự gồm hai phần tử của V được gọi là các  
cung.  
• Hai cung e1, e2 tương ứng với cùng một cặp đỉnh được  
gọi là cung lặp.  
8
Phân biệt các loại đồ thị  
Loại đồ thị  
Cạnh  
Có cạnh bội  
Có khuyên  
Không  
Không  
Đơn đồ thị vô hướng  
Vô hướng  
Có  
Có  
Không  
Có  
Đa đồ thị vô hướng  
Giả đồ thị vô hướng  
Vô hướng  
Vô hướng  
Không  
Có  
Không  
Có  
Đơn đồ thị có hướng  
Đa đồ thị có hướng  
Có hướng  
Có hướng  
9
Quy ước  
• Ta chủ yếu làm việc với đơn đồ thị vô  
hướng và đơn đồ thị có hướng.  
• Khi viết “đồ thị vô hướng” ta hiểu là “đơn  
đồ thị vô hướng”.  
• Khi viết “đồ thị có hướng” ta hiểu là “đơn  
đồ thị có hướng”.  
10  
Một số thuật ngữ cơ bản trên đồ  
thị vô hướng  
Bậc của đỉnh  
• ĐN 1. Hai đỉnh u và v của đồ thị vô hướng G =<V, E>  
được gọi là kề nhau nếu (u,v) là cạnh thuộc đồ thị G.  
– Nếu e =(u, v) là cạnh của đồ thị G thì ta nói cạnh này liên thuộc  
với hai đỉnh u và v, hoặc ta nói cạnh e nối đỉnh u với đỉnh v, đồng  
thời các đỉnh u và v sẽ được gọi là đỉnh đầu của cạnh (u,v).  
• ĐN 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số  
cạnh liên thuộc với nó và ký hiệu là deg(v).  
12  
Ví dụ  
• deg(a) = 2, deg(b) =deg(c) = deg(f) = 4;  
• deg(e) = 3, deg(d) = 1, deg(g)=0.  
• Đỉnh có bậc 0 được gọi là đỉnh cô lập (g)  
• Đỉnh bậc 1 được gọi là đỉnh treo (d)  
13  
Tổng bậc các đỉnh  
• Định lý 1. Giả sử G = <V, E> là đồ thị vô hướng với m  
cạnh. Khi đó:  
• Hệ quả. Trong đồ thị vô hướng G=<V, E>, số các đỉnh  
bậc lẻ là một số chẵn.  
14  
Đường đi, chu trình  
• ĐN 1. Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị  
vô hướng G=<V,E> là dãy x0, x1,..., xn-1, xn, trong đó n là  
số nguyên dương, x0=u, xn=v, (xi, xi+1)E, i=0,1,2,...,n-1.  
• Đường đi như trên còn có thể biểu diễn thành dãy các  
cạnh (x0, x1), (x1,x2),...,(xn-1, xn).  
• Đỉnh u là đỉnh đầu, đỉnh v là đỉnh cuối của đường đi.  
• Đường đi có đỉnh đầu trùng với đỉnh cuối (u=v) được gọi  
là chu trình.  
• Đường đi hay chu trình được gọi là đơn nếu như không  
có cạnh nào lặp lại.  
15  
Ví dụ  
• a, d, c, f, e là đường đi đơn độ dài 4.  
• d, e, c, a không là đường đi vì (e,c) không phải là cạnh  
của đồ thị.  
• Dãy b, c, f, e, b là chu trình độ dài 4.  
• Đường đi a, b, e, d, a, b có độ dài 5 không phải là  
đường đi đơn vì cạnh (a,b) có mặt hai lần.  
16  
. Đồ thị liên thông  
• ĐN 2. Đồ thị vô hướng được gọi là liên thông nếu luôn  
tìm được đường đi giữa hai đỉnh bất kỳ của nó.  
• Trong trường hợp đồ thị G=<V, E> không liên thông, ta  
có thể phân rã G thành một số đồ thị con liên thông mà  
chúng đôi một không có đỉnh chung.  
– Mỗi đồ thị con như vậy được gọi là một thành phần  
liên thông của G.  
– Như vậy, đồ thị liên thông khi và chỉ khi số thành phần  
liên thông của nó là 1.  
• Đối với đồ thị vô hướng, nếu tồn tại đỉnh uV sao cho u  
có đường đi đến tất cả các đỉnh còn lại của đồ thị thì ta  
kết luận được đồ thị là liên thông.  
17  
Ví dụ  
• Số thành phần liên thông của G là 3  
18  
Cầu, trụ  
• ĐN 3.  
– Cạnh eE được gọi là cầu nếu loại bỏ e làm tăng thành phần  
liên thông của đồ thị.  
– Đỉnh uV được gọi là đỉnh trụ nếu loại bỏ u cùng với các cạnh  
nối với u làm tăng thành phần liên thông của đồ thị.  
• VD: Cạnh (5,10) là cầu, đỉnh 6 là trụ.  
19  
Một số thuật ngữ cơ bản trên đồ  
thị có hướng  
Tải về để xem bản đầy đủ
pdf 42 trang myanh 23080 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 1: Khái niệm về đồ thị", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_toan_roi_rac_2_chuong_1_khai_niem_ve_do_thi.pdf