›
›

Bài giảng Toán rời rạc - Chương 5: Lý thuyết đồ thị

Download
TOÁN RỜI RẠC  
Chương 5: LÝ THUYẾT ĐỒ THỊ  
GV: NGUYỄN LÊ MINH  
Bộ môn Công nghệ thông tin  
Nội dung  
Khái niệm đồ thị  
Các loại đồ thị  
Bậc của đồ thị  
Biểu diễn đồ thị  
Tính liên thông trong đồ thị  
Chu trình Euler – Hamilton  
Tìm đường đi ngắn nhất  
2
Khái niệm  
Đồ thị là 1 cấu trúc rời rạc gồm các đỉnh và các cạnh (vô  
hướng hoặc có hướng) nối các đỉnh đó.  
Có 2 loại đồ thị: Đồ thị có hướng – Đồ thị vô hướng  
3
Đồ thị có hướng  
Đồ thị có hướng G = (V, E) trong đó:  
• Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị  
• 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.  
• Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 푉2, quy định  
hướng đi từ i -> j  
Đồ thị vô hướng  
Đồ thị vô hướng G = (V, E) trong đó:  
• Tập khác rỗng V là tập hợp hữu hạn các đỉnh của đồ thị  
• 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.  
• Mỗi cạnh e∈E liên kết với 1 cặp đỉnh (i,j)∈ 푉2, không quy  
định thứ tự.  
3
Cạnh song song và khuyên  
• 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  
• Nếu hai cạnh V và V’ cùng liên kết với cặp (i,j) thì V và V’  
được gọi là p ạh sg sog ớau  
3
Các loại đồ thị  
Đồ thị rỗng  
Đồ thị đơn  
Đồ thị đủ  
Có tập cạnh là tập Không có khuyên Là đồ thị vô hướng,  
rỗng  
và cạnh song song đơn, 2 đỉnh bất kỳ  
luôn kề nhau  
3
Các loại đồ thị  
Đồ thị hai phía (Đồ thị lưỡng phân)  
Là một đồ thị trong đó tập các đỉnh có thể được chia thành  
hai tập không giao nhau thỏa mãn điều kiện không có cạnh  
nối hai điểm bất kỳ thuộc cùng một tập  
3
Đỉnh kề  
Trong đồ thị vô hướng G=(V,E), nếu e=(u,v) là 1 cạnh thì:  
• Đỉnh u, v là hai đỉnh kề nhau  
• Cạnh e là cạnh liên thuộc với đỉnh u,v  
• Đỉnh u, v là đỉnh đầu  
u
cạnh e  
e
v
Đỉnh kề  
Trong đồ thị có hướng G=(V,E), nếu e=(u,v) là 1 cung thì:  
• Đỉnh v là đỉnh kề của đỉnh u  
• Cung e là cung đi ra đỉnh u và cung đi vào đỉnh v  
• Đỉnh u là đỉnh đầu  
cung e, đỉnh v là đỉnh  
cuối cung e  
u
e
t
v
s
x
3
Bậc của đỉnh  
Bậc của đỉnh v trong đồ thị vô hướng G=(V,E), ký hiệu deg(v),  
là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh  
được tính hai lần cho bậc của nó  
Deg(v) = 1 -> đỉnh treo  
Deg(v) = 0 -> đỉnh cô lập  
VD: Deg(9) = ?  
Deg(0) = ?  
Bậc của đỉnh  
Trong đồ thị có hướng G=(V,E),  
• Bán bậc ra của một đỉnh v (푑푒푔+ (v)) là số cung đi ra  
khỏi nó.  
• Bán bậc vào của một đỉnh v (푑푒푔− (v)) là số cung đi vào  
nó.  
u
e
• Bậc của đỉnh = (푑푒푔+) + (푑푒푔−)  
• 푑푒푔+(푣)= ?  
t
v
• 푑푒푔−(푣)= ?  
s
x
Định lý  
Xét đồ thị vô hướng G=(V,E), 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ó  
deg(v) 2| E |  
vV  
3
Định lý  
Xét đồ thị có hướng G=(V,E), 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ị  
deg(v) deg(v) | E |  
   
vV  
vV  
u
t
v
x
t
Đường đi  
Xét đồ thị G = <V, E>. 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:  
Độ dài 2  
d1: 1 2 5  
Độ dài 6  
d2: 1 2 4 3 9 2 5  
Độ dài 6  
d3: 1 9 2 3 9 2 5  
Chu trình  
Xét đồ thị G = <V, E>. 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ị  
Độ dài 3  
C1: 1 2 9 1  
Độ dài 6  
C2: 1 9 0 3 9 2 1  
Độ dài 5  
C3: 1 9 2 3 9 1  
Đường đi - Chu trình  
• 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.  
• 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:  
d1: 1 2 9 1  
d2: 1 2 4 3 9 2 5  
d3: 1 9 2 3 9 2 5  
C1: 1 2 9 1  
C2: 1 9 0 3 9 2 1  
C3: 1 9 2 3 9 1  
Sự liên thông  
• Xét đồ thị vô hướng G = <V, E>. 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.  
Đồ thị vô hướng liên thông  
Đồ thị vô hướng không liên thông  
3
Sự liên thông  
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  
3
Sự liên thông  
• Xét đồ thị vô hướng G = <V, E>. 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.  
Đồ thị vô hướng liên thông  
Đồ thị vô hướng không liên thông  
3
Tải về để xem bản đầy đủ
pdf 59 trang Mãnh Khiết 12/01/2024 15501 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 - Chương 5: Lý thuyết đồ 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_chuong_5_ly_thuyet_do_thi.pdf