tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 1 - Tôn Quang Toại

Bài giảng Lý thuyết đồ thị: Chương 1 Một số khái niệm cơ bản về đồ thị, cung cấp cho người đọc những kiến thức như: Một số bài toán dẫn đến khái niệm đồ thị; Định nghĩa đồ thị và phân loại đồ thị; Các thuật ngữ cơ bản; Một số dạng đồ thị. Mời các bạn cùng tham khảo! | CHƯƠNG 1 MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ Tôn Quang Toại Khoa CNTT Đại học Ngoại ngữ - Tin học Nội dung Một số bài toán dẫn đến khái niệm đồ thị Định nghĩa đồ thị và Phân loại đồ thị Các thuật ngữ cơ bản Một số dạng đồ thị MỘT SỐ BÀI TOÁN DẪN ĐẾN KHÁI NIỆM ĐỒ THỊ Một số bài toán dẫn đến khái niệm đồ thị Bài toán 1. Có cách nào xuất phát từ một vị trí sau đó đi qua 7 cây cầu mỗi cây cầu chỉ đi qua một lần và trở về vị trí xuất phát Một số bài toán dẫn đến khái niệm đồ thị Bài toán 2. Có thể vẽ hình phong bì thư sau bởi một nét bút hay không 1 2 3 4 5 Một số bài toán dẫn đến khái niệm đồ thị Bài toán 3. Một Sinh viên muốn đi từ nhà đến trường thì phải đi như thế nào Cách đi nào là nhanh nhất ĐỊNH NGHĨA ĐỒ THỊ VÀ PHÂN LOẠI ĐỒ THỊ Định nghĩa và phân loại đồ thị Định nghĩa Đồ thị Đồ thị là một mô hình toán học để biểu diễn tập các đối tượng V và mối quan hệ giữa các đối tượng đó E . Đồ thị được định nghĩa bởi bộ V E với V là tập các đỉnh Vertices V v1 v2 v3 vn và n V gọi là bậc cấp của đồ thị E là tập cạnh Edges E e1 e2 e3 em gồm một số cặp phần tử không có thứ tự hay có thứ tự của tập V và m E gọi là kích thước của đồ thị. Định nghĩa và phân loại đồ thị Ký hiệu đồ thị G V E Ký hiệu cạnh Cạnh ek nối 2 đỉnh vi và vj được ký hiệu là ek vi vj Định nghĩa và phân loại đồ thị Phân loại đồ thị dựa vào 2 tiêu chuẩn Hướng của cạnh Đồ thị vô hướng Đồ thị có hướng Số cạnh nối 2 đỉnh Đơn đồ thị Đa đồ thị Định nghĩa và phân loại đồ thị Đồ thị vô hướng G V E là đồ thị vô hướng nếu tập cạnh E là tập các cặp không có thứ tự các cạnh không có chiều . Định nghĩa và phân loại đồ thị Đồ thị có hướng G V A là đồ thị có hướng nếu tập cung A là tập các cặp có thứ tự các cạnh có chiều . Biểu diễn đồ thị bằng hình học Biểu diễn đỉnh Mỗi đỉnh là 1 điểm 1 vòng tròn nhỏ hay 1 biểu tượng nào đó trong mặt phẳng hay không gian. Dùng ký hiệu tên hoặc số hiệu của đỉnh ghi bên điểm tương ứng Biểu diễn cạnh cung Nếu e u v là một cạnh thì nối điểm u đến điểm v bằng một đoạn thẳng hay đoạn cong .

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Phân loại đồ thị
• Bài toán dẫn đến khái niệm đồ thị
• Đồ thị có hướng
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng