tailieunhanh - Lý thuyết đồ thị_sách dùng cho sinh viên ngành tin học

Quyển "Lý Thuyết Đồ Thị" được biên soạn nhằm để đáp ứng nhu cầu tham khảo sách bằng tiếng Việt của sinh viên. Đây là giáo trình Toán dành cho sinh viên ngành Tin học, các vấn đề được trình bày bằng ngôn ngữ giải thuật, phần chứng minh vẫn chặt chẽ và rõ ràng. Nội dung quyển sách bao gồm những vấn đề cơ bản nhất của Lý thuyết Đồ thị cùng một số các bài toán áp dụng và được chia làm 8 chương . | Simpo PDF Merge and Split Unregistered Version - http 0 Chương ỉ Mớ đau------------------- -5 0 Chưunp 2 Cac bài toan vé chu trinh-30 0 Chương 3 Đồ thi phong -------------57 0 CÀưory 4 Cây--------------------- 76 0 Cốưong 5 Boi toàn về con đương ngớn nhót--------J16 __ Chương 6 Mộỉ sò ap dụng ỉ4 ỉ 0 PHỤ LỤC Huờng dồn vo dơp sỏ --201 - - . -II II II I - -II I - Sinjp DF fgyn Unregistered Version - http Một đổ thị thường được biểu diễn băng một biểu đồ như sau . Mỗi đinh biểu diễn thành 1 điểm và mỗi cạnh biểu diễn thành 1 đoạn nối 2 đỉnh tương ứng với nó. THÍ Dự 1 Dưới đây là biểu đồ của vài đồ thị. Gs Gft THÍ DỤ 2 Ta dùng ký hiệu Kn đê chi đơn đô till đay đu co dinh. Biếu dố cúa K với 1 n 5 như sau n 6 BẬC CỦA MỘT ĐỈNH Xét. một đỉnh V trong đồ thị G. Sô cạnh tới V trong đó mồi vòng tại V được kể là 2 cạnh tới V gọi là bậc degree của V và ký hiệu là d v . Đỉnh có bậc 0 gọi là đỉnh cô lập isolated vertex . Đính có bậc 1 gọi là đỉnh treo pendant vertex cạnh tới đỉnh treo gọi là cạnh treo pendant edge . Đồ thị mà mọi đính đểu là đĩnh cô lập gọi là đồ thị rồng null graph . 1 ĐỊNH Lý Với mọi đồ thị G V E tơ có d v 2 I EI veV