tailieunhanh - Ebook Lý thuyết tổ hợp và đồ thị: Phần 2

Nối tiếp nội dung phần 1, phần 2 cuốn sách cung cấp cho người học các kiến thức: Nghịch đảo Mobius, các khái niệm và kết quả cơ bản của đồ thị, một số bài toán tối ưu trên đồ thị, độ liên thông, ghép cặp và nhân tử của đồ thị, tô màu đồ thị, lý thuyết ramsey. nội dung chi tiết. | Chương 5 Nghịch đảo Mõbius Chương này nhằm mục đích tổng quát hoá phương pháp đếm bằng công thức nghịch đào ờ Chương 3 cho các tập được sắp bộ phận. Hai hàm quan trọng được đề cập tới ờ đây là hàm Zeta và hàm Mõbius. Phương pháp đếm bằng công thức nghịch đảo là phương pháp đếm hủu hiệu trong việc giầi quyết nhiều bài toán dểm trong giải tích số học . . Tập được sắp bộ phận Quan hệ hai ngôi a trên tập X được gọi là có tính chất . .X . i phản xạ nếu với mọi X 6 X ta luôn có X a X ii phản đối xứng nếu với mọi X y X ứxayvẫyax suy ra x - 2 íii bắc cầu nếu với mọi ÍT y z X từ a y và y a z suy ra X Oi z. Quan hệ hai ngôi a trên tập X được gọi là một thứ tự bộ phận trên X nếu nó có cả ba tính chất phản xạ phản đối xứng và bắc cầu. Tập X trên đó .đã xác định một thứ tự bộ phận ữ được gọi là tập ẫược sắp bộ phận-bời thứ tự bộ phận a và được ký hiệu là X a . _ Người ta thường sử dụng dấu để ký hiệu cho một thứ tự bộ phận a. Người ta cũng viết y X nếu X y. Hơn thế nừa ta viết X y nễu X y và 2 y. Nếu X y tương ứng X y ì thì người ta cũng quen nói rằng x nhò hơn y tương ứng x nhỏ hơn hoặc bằng y . Ta cùng dùng ký hiệu X y tương ứng X y để chỉ rằng x không w CEBOOK .co. PDA Y KE M. 164 Chương 5. Nghịch ẵảo Mobius nhỏ hơn y tương ứng X không nhó hơn hoặc bằng y . Ví dụ . Quan hệ nhổ hơn hoặc bang thông thường trên tập p tất cả các số nguyên dương là một thứ tự bộ phận trên p. o Ví dụ . Quan hệ Of với ữ ý X chia hết y là một thứ tự bộ phận trên p tất cả các số nguyên dương. A . Ví dụ . Quan hệ ừ với ữ B 4 c B là một thứ tự bộ phận trẻn tập luỹ thừa P X tất cả các tập con của tập X. Giả sử là một thứ tự bộ phận trên tập X. Hai phần tử Xf y X được gọi là so sánh được với nhau đối với thứ tự bộ phận nếu hoặc X y hoặc y X. Thứ tự bộ phận trên X được gọi ỉà thứ. tự tuyến iinh nếu với mọi rr5 y e X X và y so sánh được vói nhau. Tập X trên đó đã xác định một thứ tự tuyến tính được gọi là tập được sắp đầy đù haỹ cũng gọi là .