tailieunhanh - Bài giảng Lý thuyết đồ thị - Bài 1: Đại cương về đồ thị

Bài giảng "Lý thuyết đồ thị - Bài 1: Đại cương về đồ thị" trình bày định nghĩa đồ thị, các mô hình đồ thị, một số thuật ngữ cơ bản của đồ thị, một số đơn đồ thị đặc biệt, khái niệm Đường đi – Chu trình – Sự liên thông. . | Bài giảng Lý thuyết đồ thị - Bài 1: Đại cương về đồ thị Bài 1 Đại cương về đồ thị . Định nghĩa đồ thị Một số bài toán dẫn đến khái niệm đồ thị Bài toán 1: Có thể vẽ hình phong bì thư bởi một nét bút hay không. Nếu có hãy chỉ ra tuần tự các nét vẽ 1 2 3 4 5 3 Một số bài toán dẫn đến khái niệm đồ thị (tt) Bài toán 2: Một đoàn kiểm tra chất lượng các con đường. Để tiết kiệm thời gian, đoàn kiểm tra muốn đi qua mỗi con đường đúng 1 lần. Kiểm tra xem có cách đi như vậy không? 4 7 5 1 8 6 2 4 Đồ thị là gì? Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. Người ta phân loại đồ thị tùy theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị. 5 Định nghĩa đồ thị Định nghĩa. Một đơn đồ thị vô 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à tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. VD: a. Đơn đồ thị vô hướng b. Không phải đơn đồ thị vô hướng do c. Không phải đơn có các cặp cạnh nối đồ thị vô hướng do cùng một cặp đỉnh có cạnh nối một đỉnh với chính nó. 6 Định nghĩa đồ thị (tt) Định nghĩa. Một đa đồ thị vô 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ử khác nhau của V gọi là các cạnh. Chú ý: Các cạnh cùng nối giữa một cặp đỉnh được gọi là các cạnh song song. Nếu đồ thị có cạnh nối từ một đỉnh với chính nó (cạnh này được gọi là khuyên) thì đồ thị được gọi là giả đồ thị vô hướng. 7 Định nghĩa đồ thị (tt) VD: e2 e1 e a. Đa đồ thị vô hướng. e1 và e2 là b. Giả đồ thị vô hướng. e là khuyên các cạnh song song. Chú ý: Trong một số tài liệu có thể có nhập khái niệm đa đồ thị và giả đồ thị, khi đó, chỉ có một tên gọi chung là đa đồ thị cho cả hai loại. 8 Định nghĩa đồ thị (tt) Định nghĩa. Một đơn đồ .

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• 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ị
• 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