TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 1: Giới thiệu tổng quan

Chương 1: Giới thiệu tổng quan trình bày khái niệm đồ thị, một số lĩnh vực ứng dụng của đồ thị; định nghĩa; một số đồ thị đặc biệt; biểu diễn đồ thị; đường đi và chu trình; liên thông và thành phần liên thông; một số vấn đề liên quan đến cài đặt đồ thị. | Bài giảng LÝ THUYẾT ĐÒ THỊ GRAPH THEORY Trần Quốc Việt Tài liệu tham khảo Nguyền Cam Chu Đức Khánh Lý thuyết Đồ thị 1998. Kenneth H. Rosen Discrete Mathematics and Its Applications 29 09 2014 Chương 1 Giới thiệu tổng quan Khái niệm đồ thị một số lĩnh vực ứng dụng của đồ thị Định nghĩa Một số đồ thị đặc biệt Biểu diễn đồ thị Đường đi và chu trình Liên thồng và thành phần liên thồng Một số vấn đề liên quan đến cài đặt đồ thị Một số lĩnh vực ứng dụng Trong thực tế rất nhiều bài toán thuộc các lĩnh vực khác nhau được giải bằng đồ thị Lĩnh vực mạng máy tính Biểu diễn mạng máy tính xác định 2 máy có thể liên lạc vơi nhau trên một mạng . 1 Một SỐ lĩnh vực ứng dụng Lĩnh vực giao thông Tìm đường đi đường đi ngắn nhất giữa hai thành phố trong mạng giao thông . Tỉnh c Mỗi đỉnh một tỉnh Mỗi cạnh nối 2 đỉnh u v Có đường đi trực tiếp giữa 2 tỉnh u v Con số trên mỗi cạnh Độ dài đường đi trực tiếp giữa 2 tỉnh. Yêu câu Tìm đườnq đi nqắn nhất từ môt tỉnh nào đó đến môt 5 tỉnh khác chẳng hạn từ A đến F Ví dụ Bài toán về các cây cầu ở Konigsberg 29 09 2014 Một SỐ lĩnh vực ứng dụng Giải các bài toán về lập lịch thời khóa biểu và phân bố tần số cho các trạm phát thanh và truyền hình 6 2. Một số định nghĩa Đô thỉ vô hường undirected graph Đồ thị vô hướng G V E với W0 là tập các đỉnh E Là đa tập hợp với các phần tử có dạng u v với u ve V không có thứ tự gọi là các cạnh của đồ thị Biểu diễn bằng biểu đồ Mỗi đỉnh một điểm Mỗi cạnh u v một cạnh vô hướng nối giữa u và V ví dụ Cho đồ thị G với Tập đinh V 1 2 3 4 tập cạnh E 1 2 2 3 3 4 2 4 Kí hiệu G V E J 2 2. Một số định nghĩa Cho đồ thị vô hướng G V E Với cạnh e u v eE u v gọi là 2 đỉnh kề nhau e gọi là cạnh liên thuộc với 2 đỉnh u v Hai cạnh e1 e2 liên kết cùng một cặp đỉnh khác nhau đuợc gọi là 2 cạnh song song paralell edges . Một cạnh trên cùng một đỉnh gọi khuyên loop . Đỉnh 1 kề với đỉnh 2 Đỉnh 2 kề với đỉnh 3 Đỉnh 5 kề với đỉnh 4 Đỉnh 1 không kề với đỉnh 4 . e3 e4 Các cạnh song song e8 Khuyên 9 2. Một số định nghĩa Bậc của đỉnh trong .

• Toán học
• Lý thuyết đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Bài giảng lý thuyết đồ thị
• Ứng dụng đồ 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ị
• 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ị
• Đạ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ị
• 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
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị