Bài giảng Toán rời rạc: Chương 5 - Nguyễn Lê Minh

Chia sẻ: Minh Nguyệt | Ngày: | Loại File: PDF | Số trang:59

Thêm vào BST

Báo xấu

54
lượt xem 4
download

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

Bài giảng "Toán rời rạc - Chương 5: Lý thuyết đồ thị" cung cấp cho người học các kiến thức: 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. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 5 - Nguyễn Lê Minh

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 3
Đồ 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à cặp cạnh song song với nhau 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 3
Đỉ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 u e cung e, đỉnh v là đỉnh t v cuối cung e 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) = ? 3
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 • Bậc của đỉnh = (𝑑𝑒𝑔+ ) + (𝑑𝑒𝑔− ) e t v • 𝑑𝑒𝑔+ (𝑣)= ? • 𝑑𝑒𝑔− (𝑣)= ? s x 3
Đị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 | vV 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V  ( v )   (v) | E | deg vV  u t v t x 3
Đường đi 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: Độ 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 3
Chu trình 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ị Độ 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 3
Đườ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 3
Sự liên thông • 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. Đồ 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 = . 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