zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Bài 6 - TS. Nguyễn Văn Hiệu

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:46

Báo xấu

109
lượt xem 11
download

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

Bài 6 "Lý thuyết đồ thị" thuộc bài giảng Toán rời rạc: Định nghĩa, thuật ngữ cơ sở, định lý cơ sở về bậc, đồ thị đơn đặc biệt, đồ thị phân đôi, đồ thị đẳng cấu, tính liên thông,... Tham khảo nội dung bài giảng để nắm bắt thông tin chi tiết.

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: Bài 6 - TS. Nguyễn Văn Hiệu

BÀI 6 LÝ THUYẾT ĐỒ THỊ Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
Tổng quan về đồ thi Nội dung Nội dung 6.1. Giới thiệu 6.6. Đồ thị phân đôi 6.2. Định nghĩa 6.7. Đồ thị đẳng cấu 6.3. Thuật ngữ cơ sở 6.8. Tính liên thông 6.4. Định lý cơ sở về bậc 6.9. Đồ thi Euler 6.5. Đồ thị đơn đặc biệt 6.10. Đồ thị Hamilton Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
6.1. Giới thiệu Lý thuyết đồ thị Ứng dụng  Xây dựng mật điện trên một  Nghành học lâu đời, nhưng bảng điện dùng nhiều trong ứng dụng hiện đại  Xác định hai máy tính có kết nối hay không  Xác định đường đi ngắn nhất  Leohard Euler giữa hai thành phố  Lập lịch thi  Phân chia kênh truyền cho đài truyền hình … Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
6.2. Định nghĩa Đơn đồ thị Ứng dụng G = (V, E)  Mạng gồm các máy tính và các kênh điện thoại.  V - tập đỉnh,  Giữa hai máy tính bất kì có nhiêu nhất 1 kênh điện thoại.  E - tập các cặp không có thứ  Kênh thoại cho phép liên lạc hai chiều tự, gọi là cạnh nối các đỉnh  Không có máy tính nào được nối với phân biệt. chính nó.  ∃! (u,v) ∈ 𝐸 ⟹ ∃! (𝑣, 𝑢) ∈ 𝐸  (u, u )∉ 𝐸 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
6.2. Định nghĩa Đơn đồ thị Ứng dụng G = (V, E)  Mạng điện thoại cố định  V - tập đỉnh,  Mạng giao thông  E - tập các cặp không có thứ tự, gọi là cạnh nối các đỉnh phân biệt.  Mạng xe buýt  ∃! (u,v) ∈ 𝐸 ⟹ ∃! (𝑣, 𝑢) ∈ 𝐸  (u, u )∉ 𝐸 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
6.2. Định nghĩa Đa đồ thị Ứng dụng G = (V, E)  Mạng gồm các máy tính và các kênh điện thoại.  V - tập đỉnh,  Cho phép hai máy tính nối nhiều kênh thoại (do truyền tài nhiều)  E : cho phép nhiều hơn hai cạnh nối 2 đỉnh phân biệt.  (u,v) ∈ 𝐸  (u, u )∉ 𝐸 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
6.2. Định nghĩa Giả đồ thị Ứng dụng  Mạng gồm các máy tính và các kênh G = (V, E) điện thoại.  Cho phép máy tính nối u kênh thoại  V - tập đỉnh, với chính nó  E : cho phép vòng (đỉnh đầu và cuối trùng nhau)  (u,u) ∈ 𝐸 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
6.2. Định nghĩa Chú ý Chú ý ĐỒ THI ĐƠN ĐỒ THỊ ≡ ⊂ ĐỒ THỊ VÔ HƯỚNG ĐA ĐỒ THỊ ⊂ GIẢ ĐỒ THỊ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
6.2. Định nghĩa Đơn đồ thị có hướng Ứng dụng G = (V, E)  V - tập đỉnh,  E - tập các cặp có thứ tự, gọi là cung nối các đỉnh phân biệt.  (u,v) ∈ 𝐸 ⇏ (𝑣, 𝑢) ∈ 𝐸  (u, u )∉ 𝐸 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
6.2. Định nghĩa Đa đồ thị có hướng Ứng dụng G = (V, E)  V - tập đỉnh,  E : cho phép nhiều hơn hai cung nối các đỉnh phân biệt.  (u,v) ∈ 𝐸 ⇏ (𝑣, 𝑢) ∈ 𝐸  (u, u )∉ 𝐸  Hai cung tương ứng với một cặp đỉnh được gọi là cung lặp Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
6.2. Định nghĩa Đồ thị tình yêu Ứng dụng    Hai người có ít nhất cùng 1 sở thích thì có thể ghép đôi  G = (V, E) ? Tìm cách ghép đôi sao cho số người  V = {A, B , C , D , E} cô đơn là ít nhất  E: (u,v) ∈ E nếu u và v có cùng một sở thích Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
6.2. Định nghĩa Hội thảo video Ứng dụng  Có n điểm tham gia hội thảo, mỗi  điểm phát tính hiệu cho các điểm còn lại  Tổng các điểm phát ra từ v phải nhỏ hơn băng thông của v.  Thời gian trể từ điểm v đến điểm u phải nhỏ hơn một thông số cho trước.  Đảm bảo băng thông được sử  dụng tốt nhất Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
6.2. Định nghĩa Hội thảo video Ứng dụng  G = (V, E)  V: tập các điểm tham gia hội thảo  E: tập tất cả các kết nối có thể có (đồ thị đầy đủ)  Tìm một cây phủ: cây thể hiện việc phát tính hiệu từ một điểm Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
6.3. Thuật ngữ cơ sở Đồ thị vô hướng G = (V, E) , e = (u,v) ∈ E  u và v – đỉnh liền kề 1 2  e - cạnh liên thuộc với u và v 0  u và v – đỉnh đầu của e  Bậc của u là số cạnh liên thuộc 6 với u. 3  Đỉnh có bậc 0 - đỉnh cô lập  Đỉnh có bậc 1 - đỉnh treo. 7 5 4  Khuyên được tính bậc 2 deg(0) = 3, deg(5) = 1, deg(2) = 0, deg(6) = 5,…. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
6.3. Thuật ngữ cơ sở Đồ thị có hướng G = (V, E) , e = (u,v) ∈ E  u – nối tới v u  v – nối từ u t v  u – đỉnh đầu cung e  v – đỉnh cuối cung e  deg + (u) – bậc ra của u s x  deg - (u) – bậc vào của u deg+(s) = 2, deg-(s) = 1, deg+(x) = 1, deg-(v) = 0,… Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
6.4 Định lý cơ sở về bậc Đồ thị vô hướng G = (V, E) 1 2  2 |E| = ∑ v€ V deg (v) 0 Tổng số bậc lẽ của đồ 6 3 thị là một số chẳn. 7 5 4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
6.4 Định lý cơ sở về bậc Đồ thị có hướng G = (V, E) u  ∑ v€ V deg + (v) = ∑ u € V deg - (u) = | E | t v  Bỏ qua hướng của G ta có đồ thị vô hướng nền của G s x có số cạnh bằng số cung của G Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
6.5 Đồ thị đơn đặc biệt Đồ thị đầy đủ - Kn Minh họa  Có n đỉnh  Hai đỉnh bất kỳ luôn có cạnh nối  Tất cả các đỉnh có bậc n-1  Số cạnh là n*(n-1)/2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
6.5 Đồ thị đơn đặc biệt Đồ thị vòng - Cn Minh họa  Có n đỉnh  Các đỉnh nối với nhau theo vòng tròn  Mỗi đỉnh có bậc là 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
6.5 Đồ thị đơn đặc biệt Đồ thị bánh xe - Wn Minh họa  n+1 đỉnh  2n cạnh  n đỉnh bậc 3 và 1 đỉnh bậc n  Hai đỉnh bất kỳ luôn kề nhau Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.