Bài giảng Toán rời rạc 2: Phần 2

➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạm

Loại tài liệu: PDF

Số trang: 59 Trang

Tài liệu: ✅ ĐÃ ĐƯỢC PHÊ DUYỆT

TẢI VỀ

Nội dung chi tiết: Bài giảng Toán rời rạc 2: Phần 2

Bài giảng Toán rời rạc 2: Phần 2

HỌC VIỆN CÔNG NGHẸ Bưu CHÍNH VIỀN THÔNG ---------------03 Q so------KHOA CÔNG NGHỆ THÔNG TINBÀI GIẢNGTOÁN RỜI RẠC 2NGUYỄN DUY PHƯƠNGHà Nội 2016CHƯƠNG

Bài giảng Toán rời rạc 2: Phần 2 4. ĐỒ THỊ EULER, ĐỒ THỊ HAMIL TON4.1.Dồ thị Euler, đồ thị nừa EulerĐịnh nghĩa. Chu trình đơn trong đồ thị G đi qua mỗi canh cua đổ thị đúng một Lằn đ

ược gọi là chu trình Euler. Đường đi đơn trong G đi qua mồi cạnh của nỏ đúng một lần được gọi Là đường đi Euler. Đô thi được gọi là đồ thị Euler nêu n Bài giảng Toán rời rạc 2: Phần 2

ó có chu trình Euler. Đồ thị có đường đi Euler được gọi là nửa Euler.Rô ràng, mọi đồ thị Euler đểu Là nứa Euler nhưng điều ngược lại không đúng.Hình 6

Bài giảng Toán rời rạc 2: Phần 2

.1. Đồ thị vò hướng Gỉ, G2, G3.Đồ thi GI là đồ thị Euler vì nó có chu trinh Euler a. e. c. d. e. b. a Đồ thị G3 không có chu trinh Euler nhưng chứa đư

HỌC VIỆN CÔNG NGHẸ Bưu CHÍNH VIỀN THÔNG ---------------03 Q so------KHOA CÔNG NGHỆ THÔNG TINBÀI GIẢNGTOÁN RỜI RẠC 2NGUYỄN DUY PHƯƠNGHà Nội 2016CHƯƠNG

Bài giảng Toán rời rạc 2: Phần 2 , H3 trong Hình 4.2.Hình 4.2. Dồ thị có hướng HI. H2, H3.Dồ thị H2 là đồ thị Euler vì nó chứa chu trình Euler a. b. c, d. e, a vì vậy nó là đồ thị Eul

er Đô thị H3 không có chu trinh Euler nhưng có đường đi Euler a. b. c, a. d, c nên nó là đô thị nửa Euler. Đồ thị HI không chửa chu trinh Euler cũng n Bài giảng Toán rời rạc 2: Phần 2

hư chu trinh Euler.4.2.Thuật toán tìm chu trình EulerDê lim một chu trình Euler của đồ thị ta sử dụng kết quà của định lý sau.Định lý 1. Điền kiện cần

Bài giảng Toán rời rạc 2: Phần 2

và đu đẽ đồ thị G= là Euler. Đồ thị vô hướng hên thòng G= là đò thị Euler khi và chi khi mọi đinh của G đêu có bậc chằn. Đồ thị có68hướng

HỌC VIỆN CÔNG NGHẸ Bưu CHÍNH VIỀN THÔNG ---------------03 Q so------KHOA CÔNG NGHỆ THÔNG TINBÀI GIẢNGTOÁN RỜI RẠC 2NGUYỄN DUY PHƯƠNGHà Nội 2016CHƯƠNG

Bài giảng Toán rời rạc 2: Phần 2 à hên thòng mạnh).4.2.1. Chứng minh đô thị là EulerDôi với đô thị vò hướng, đê chửng minh đô thi có là Euler hay không la chi cân thực hiện:•Kiêm tra

đô thị có hên thông hay không? Diêu này de dàng thực hiện bang cách kiêm tra DFS(u) - V hoặc BFS(u) - V thi ta kết luận dồ thị là liên thòng (u là đin Bài giảng Toán rời rạc 2: Phần 2

h bâl kỳ cứa đô thị).•Sứ dụng lính chất của ma trận kề biểu đồ thị vố hướng đế tính toán bậc cùa các dinh.-Vì BFS(1)= { 1, 2,6. 3,5, 7.4, 11,8, 10. 12

Bài giảng Toán rời rạc 2: Phần 2

, 9. 13} - V. Do vậy. G liên thông.- Ta lại có :deg(l) = deg(13) = 2.deg (2) = deg(3) = 4deg(4) = deg(5) = 4deg(6) = deg(7) = 4deg(S) = deg(9) = 4deg(

HỌC VIỆN CÔNG NGHẸ Bưu CHÍNH VIỀN THÔNG ---------------03 Q so------KHOA CÔNG NGHỆ THÔNG TINBÀI GIẢNGTOÁN RỜI RẠC 2NGUYỄN DUY PHƯƠNGHà Nội 2016CHƯƠNG

Bài giảng Toán rời rạc 2: Phần 2 0 0 0 1 0 0 0 0 0 0 0 1010110000000 0101100000100 0010001 100100 0110011000000 1 100101000000 0001 1 10100000 0010110000 0 0 10 1 0 1 1 00011011000000

1010000011101 Bài giảng Toán rời rạc 2: Phần 2

HỌC VIỆN CÔNG NGHẸ Bưu CHÍNH VIỀN THÔNG ---------------03 Q so------KHOA CÔNG NGHỆ THÔNG TINBÀI GIẢNGTOÁN RỜI RẠC 2NGUYỄN DUY PHƯƠNGHà Nội 2016CHƯƠNG