Thư viện tài liệu, ebook tham khảo dành cho học sinh, sinh viên

Hai đồ thị đồng phôi Định nghĩa ▶ Phép toán loại bỏ cạnh fu; vg và thêm một đỉnh mới w cùng hai cạnh fu; wg; fw; vg gọi là phép phân chia sơ cấp. ▶ Hai đồ thị gọi là đồng phôi nếu chúng có thể nhận được từ cùng một đồ thị bằng một dãy phép phân chia sơ cấp. 10.7 Planar Graphs 723 FIGURE 12 Homeomorphic Graphs. Using r = e − v + 2 (Euler’s f...

36 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 780 | Lượt tải: 0

Định nghĩa ▶ Bạn đời tốt nhất của một người là người tốt nhất trong các lựa chọn có thể của anh/chị ta. ▶ Bạn đời tệ nhất của một người là người tệ nhất trong các lựa chọn có thể của anh/chị ta. Định lý Trong thủ tục kén chồng, mọi chàng trai đều được bạn đời tốt nhất. Định lý Trong thủ tục kén chồng, mọi cô gái đều được bạn đời tệ nhất. ...

49 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 687 | Lượt tải: 0

Chứng minh ▶ Xét M∗ là một ghép cặp cực đại; ▶ đặt F là tập mọi cạnh thuộc M hoặc M∗, nhưng không thuộc cả hai. ▶ Tập cạnh F và các đỉnh tạo thành đồ thị với các đỉnh chỉ có bậc 1 hoặc 2. Tại sao? ▶ Vậy mỗi thành phần liên thông của đồ thị chỉ là đường đi hoặc chu trình; ▶ và trong mỗi đường đi hoặc chu trình này, các cạnh thuộc M luân phi...

39 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 918 | Lượt tải: 0

Số hội đồng bảo vệ ▶ Xét đồ thị với tập đỉnh là các hội đồng, giữa hai dỉnh có cạnh nối nếu hai hội đồng có chung thành viên. ▶ Bài toán tương đương với bài toán tìm số màu ít nhất để tô đồ thị này. ▶ Đồ thị này có chứa clique f1; 2; 3; 4g có kích thước 4 nên số ngày bằng 4 là ít nhất có thể. Ký hiệu ei(G) là số đỉnh của đồ thị G có bậc...

44 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1150 | Lượt tải: 0

Prüfer code ▶ Ta không cần lưu trữ toàn bộ Prüfer code mở rộng, mà ▶ ta chỉ cần lưu tữ dãy gồm n − 2 phần tử của hàng thứ hai. ▶ Dãy này gọi là Prüfer code của cây. ▶ Vậy thì, Prüfer code là một dãy số độ dài n − 2, với mỗi phần tử của nó là một số nguyên từ 0 đến n − 1. Bổ đề Mọi dãy có độ dài n − 2 gồm các số nguyên giữa 0 và n − 1 đều là ...

46 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 737 | Lượt tải: 0

Định nghĩa ▶ Chu trình chứa mọi đỉnh của đồ thị gọi là chu trình Hamilton. ▶ Hành trình dùng mỗi cạnh đúng một lần gọi là hành trình Euler. Tìm chu trình Hamilton của đồ thị tạo bởi các đỉnh và cạnh của khối lập phương. 10.7 P K4 Drawn sings. FIGURE 4 The Graph Q3. FIGURE 5 Represent 56 / 57Bài tập Năm tới, Dr Chunner và Dr Dodder đị...

57 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 766 | Lượt tải: 0

Ví dụ Ở nước Quy nạp, họ dùng đơn vị tiền Mạnh. Họ chỉ có hai loại tiền 3M (Mạnh) và 5M. Dù họ có vấn đề nhỏ với việc đổi tiền 4M hoặc 7M, nhưng họ nhận thấy rằng họ có thể đổi mọi số tiền ít nhất 8M. Hãy giải thích cho họ xem tại sao điều này đúng. ▶ Có một chồng hộp. Bạn sẽ thực hiện một dãy bước chuyển. ▶ Mỗi bước chuyển bạn chia một hộp kích th...

37 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1006 | Lượt tải: 0

Định lý Mọi số nguyên dương lớn hơn một đều phân tích được thành tích các số nguyên tố. Chứng minh bằng STTT. ▶ Giả sử tập phản ví dụ của định lý C ̸= ∅. ▶ Có phần tử n nhỏ nhất thuộc C. Vậy n không nguyên tố. Có nghĩa rằng n = a · b với a; b > 1 ▶ Hơn nữa a; b phải phân tích được thành tích các số nguyên tố. Tại sao? a = p1 · · · pk và b...

37 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1372 | Lượt tải: 0

Số Ramsey có khó tính không? Số Ramsey khá gần đây người ta tính được là r(4; 5) = 25. Dưới đây là thời gian tìm số này: ▶ 1955: Chặn trên đầu tiên cho r(4; 5) ≤ 31. ▶ 1965: Chặn dưới đầu tiên và cải thiện chặn trên 25 ≤ r(4; 5) ≤ 30. ▶ 1968: Cải thiện chặn trên r(4; 5) ≤ 29. ▶ 1971: Cải thiện chặn trên r(4; 5) ≤ 28. ▶ 1991: Cải thiện chặn ...

27 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1003 | Lượt tải: 0

Bài 2: Cho đồ thị có hướng G được biểu diễn dưới dạng ma trận trọng số: a) Thực hiện thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh E đến các đỉnh còn lại của đồ thị G. b) Chứng minh G là một mạng. Thực hiện thuật toán Ford – Fulkerson tìm luồng cực đại và lát cắt nhỏ nhất của mạng G. c) Gọi G’ là phiên bản vô hướng của G (tức là không xét...

5 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1024 | Lượt tải: 0