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 .