TAILIEUCHUNG - Giáo trình toán ứng dụng trong tin học part 6

Tham khảo tài liệu 'giáo trình toán ứng dụng trong tin học part 6', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Ill - Đổ THỊ EULER VÀ Đổ THỊ HAMILTON Trong mục này chúng ta sẽ nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Dưới đây nếu không có giải thích bổ sung thuật ngữ đổ thị được dùng để chỉ chung đa đổ thị vô hướng và có hướng và thuật ngữ cạnh sẽ dùng để chỉ chung cạnh của đồ thị vô hướng cũng như cung cùa đổ thị có hướng. . Đồ thị Euler ĐỊNH NGHĨA 1 Chu trình đơn trừng G đi qua mỗi cạnh của nó 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ó một lẩn được gọi là đường Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler vá gọi là đồ thị nửa Euler nếu nổ có đường đi Euler. Rõ ràng mọi đồ thị Euler luôn là nửa Euler nhưng điều ngược lại không luôn đúng. Ví dụ 1. Đồ thị Gị trong hình là đồ thị Euler vì nó có chu trình Euler a e c d e b a. Đổ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a c d e b d a b vì thê G3 là đồ thị nửa Euler. Đồ thị G2 không có chu trình cũng như đường Euler. G G2 G3 Hình 4 Ỉ7 Đồ thị Gị Ví dụ 2 Đồ thị H2 trong hình là đồ thị Euler vì nó có chu trình Euler a b c d e a. Đồ thị H3 không có chu trình Euler nhưng nó có đường di Euler c a b c d b vì thế H3 là đồ thị nửa Euler. Đổ thị Hj không có chu trình cũng như đường đi Euler. a b ---- ---- ---- a b Hình . Đồ H3 141 Điều kiện cần và đủ để một đồ thị là đồ thị Euler được Euler tìm ra vào năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thời đó về bảy cái cầu ở thành phố Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thỆ Những cái cầu ở thành phố Konigsberg có thể diễn tả bằng đồ thị trong hình . Định lý 1 Euler Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Hình Để chứng minh định lý trước hết ta chứng minh bổ đề Bổ đề Nếu bậc của mồi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình. Chứng minh Nếu G có cạnh lặp thì khẳng định của bổ đề là hiển nhiên. Vì vậy giả sử G là đơn đồ thị. Gọi v là một đỉnh nào đó của G. Ta sẽ xây

• Toán học
• toán ứng dụng trong tin học
• giáo trình toán ứng dụng trong tin học
• bài giảng toán ứng dụng trong tin học
• tài liệu toán ứng dụng trong tin học
• bài tập toán ứng dụng trong tin học
• Ứng dụng toán trong tin học
• Phương pháp tính
• Tìm hiểu phương pháp tính
• Xấp xỉ và sai số
• Ứng dụng công nghệ thông tin
• Ứng dụng CNTT trong giảng dạy
• Ứng dụng CNTT trường Đại học Thủy Lợi
• Ứng dụng CNTT trong giảng dạy trường Thủy Lợi
• Đề tài ứng dụng CNTT
• Ứng dụng CNTT trong tính toán khối lượng
• Suy luận toán học
• Quan hệ toán học
• Quan hệ hai ngôi
• Tập hợp toán học
• Giáo trình Tin học ứng dụng trong kinh doanh
• Tin học ứng dụng trong kinh doanh
• Tin học ứng dụng
• Bài toán dự báo kinh tế
• Bài toán điểm hòa vốn
• Bài toán qui hoạch tuyến tính
• Bài giảng Ứng dụng tin học
• Ứng dụng tin học ngành kinh tế
• Tin nhọc ứng dụng
• Tính toán trên Excel
• Vai trò của Tin học
• Nhập môn tin học ứng dụng
• Bài giảng Tin học ứng dụng trong kinh doanh
• Chương trình excel
• Dữ liệu tin học
• Hàm toán học
• Quan hệ và suy luận toán học
• Tập hợp và Quan hệ
• Suy luận toán học
• Bài toán tối ưu
• Quy hoạch toán học
• Quy trình giải bài toán tối ưu trong Excel
• Tổ chức dữ liệu trong Excel
• Bài giảng môn Tin học ứng dụng
• Bài giảng Tin học ứng dụng
• Ứng dụng excel
• Bài toán trong kinh tế
• Bài toán tiết kiệm
• Bài toán lựa chọn phương án đầu tư
• Quản trị nhà hàng
• Các hàm trong Excel
• Cơ sở dữ liệu
• Bài toán chuyên ngành bằng Excel
• Sử dụng excel để giải bài toán
• Vẽ đồ thị hòa vốn
• Tin học doanh nghiệp
• Hệ thống thông tin quản lý
• Hàm tài chính trong Excel
• Phân tích điểm hòa vốn
• Phân tích phương sai
• ứng dụng excel trong toán chuyên ngành
• ứng dụng tin học trong thiết kế
• Microsoft excel
• toán chuyên ngành
• Quy hoạch tuyến tính
• kỹ thuật tin học
• thủ thuật trong tin học
• ứng dụng tin học trong tính toán