TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

Bổ đề về số mũ đúng (Lifting The Exponent Lemma) là một bổ đề rất hữu dụng trong việc giải các bài toán số học và rất được biết đến trong lịch sử Olympiad. Thực chất là nó được mở rộng ra từ bồ đề Hensel. Ta thường viết tắt tên của bố đề là LTE, tên Tiếng Việt thì có thể gọi là bổ đề về số mũ đúng. Bài viết này xin được giới thiệu với bạn đọc về bổ...

12 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 975 | Lượt tải: 1

Giới thiệu Bài toán ghép cặp có thể chia thành 2 loại Xét việc ghép mỗi phần tử của tập hợp này với 1 phần tử của tập hợp khác như phân công n việc khác nhau cho n người, mỗi người 1 việc, đó chính là bài toán hôn nhân. Xét việc chia 2k phần tử của 1 tập hợp thành k cặp, ví dụ như sắp xếp 2k sinh viên vào k phòng trong ký túc xá (mỗi phòng có 2 ...

26 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 342 | Lượt tải: 0

Các khái niệm mở đầu (tt) Điều kiện để bài toán có lời giải: Phải tồn tại đường đi từ s đến t: Đồ thị vô hướng liên thông Đồ thị có hướng liên thông mạnh Đồ thị vô hướng, s và t nằm trong cùng một thành phần liên thông Đồ thị có hướng, có tồn tại đường đi từ s đến t Trong đồ thị không tồn tại chu trình âm Đồ thị có hướng: không tồn tại chu ...

20 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 476 | Lượt tải: 0

Biểu diễn đồ thị trên máy tính??? Tại sao phải biểu diễn đồ thị trên máy tính??? Lý thuyết đồ thị ngày càng được ứng dụng rộng rãi. Để xây dựng được các ứng dụng của đồ thị trên máy tính thì cần phải tìm cách biểu diễn đồ thị trên máy tính thích hợp. Máy tính không thể hiểu được các đồ thị dưới dạng hình vẽ thông thường. Tiêu chuẩn để lựa chọn...

31 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 322 | Lượt tải: 0

Cây khung (tt) Định lý: Một đơn đồ thị liên thông nếu và chỉ nếu nó có cây khung. Chứng minh: Nếu G có chứa cây khung thì do tính chất của cây khung là liên thông và cây khung chứa tất cả các đỉnh của G. Suy ra các đỉnh của G luôn được nối với nhau hay G liên thông. Xét G liên thông. Giả sử trong G còn tồn tại chu trình, xóa bớt một cạnh trong ...

17 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 464 | Lượt tải: 0

Cây có gốc Trong một số cây, một đỉnh đặc biệt được chọn làm gốc Đường đi từ gốc đến các đỉnh được định hướng từ gốc đến đỉnh đó Suy ra một cây cùng với gốc sẽ sinh ra đồ thị có hướng, được gọi là cây có gốc. Trong cây có gốc: Mỗi đỉnh chỉ có một cha duy nhất – là đỉnh mà trực tiếp đi đến nó trên đường đi từ gốc Mỗi đỉnh có thể không có, có 1...

32 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 388 | Lượt tải: 0

Kiểm tra đồ thị Hamilton??? Các quy tắc để xác định chu trình Hamilton (H) của đồ thị: Quy tắc 1: Nếu có 1 đỉnh bậc 2 thì hai cạnh của đỉnh này bắt buộc phải nằm trong H Quy tắc 2: Không được có chu trình con (độ dài nhỏ hơn n) trong H Quy tắc 3: Ứng với một đỉnh nào đó, nếu đã chọn đủ 2 cạnh vào H thì phải loại bỏ tất cả các cạnh còn lại (vì k...

34 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 605 | Lượt tải: 0

Thuật toán xây dựng chu trình Euler Gọi chu trình Euler cần tìm là C. Thuật toán sẽ tiến hành theo các bước sau: Khởi tạo: Chọn một đỉnh bất kỳ cho vào C. Lặp trong khi G vẫn còn cạnh Chọn cạnh e nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cầu nếu không còn cạnh nào khác để chọn. Bổ sung e và đỉnh cuối của nó vào C. Xó...

26 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 374 | Lượt tải: 0

Ý tưởng B1. Xuất phát từ 1 đỉnh cho trước nào đó. B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau. B3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và lần lượt xử lý các đỉnh kề với đỉnh đang xét B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD: Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5 Chọn 2 để xử lý. Đư...

17 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 334 | Lượt tải: 0

Định nghĩa đồ thị (tt) Định nghĩa. Một đa đồ thị có hướng là một bộ G=, trong đó: V   là tập hợp hữu hạn gồm các đỉnh của đồ thị. E là danh sách các cặp không có thứ tự gồm hai phần tử của V gọi là các cung. Chú ý: Các cung cùng nối giữa một cặp đỉnh được gọi là các cung song song (parallel arcs). Nếu đồ thị có cung nối từ một đỉnh với...

39 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 335 | Lượt tải: 0