Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng "Toán học tổ hợp và cấu trúc rời rạc - Chương 4: Đại cương về đồ thị" cung cấp cho người học các kiến thức: Giới thiệu, các khái niệm cơ bản, biểu diễn đồ thị, đẳng cấu đồ thị, đường đi, chu trình. nội dung chi tiết. | Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 4 - Lê Văn Luyện Chương 4. ĐẠI CƯƠNG VỀ ĐỒ THỊ lvluyen@hcmus.edu.vn http://www.math.hcmus.edu.vn/~luyen/cautrucroirac FB: fb.com/cautrucroirac CuuDuongThanCong.com https://fb.com/tailieudientucntt Nội dung 1. Giới thiệu 2. Các khái niệm cơ bản 3. Biểu diễn đồ thị 4. Đẳng cấu đồ thị 5. Đường đi, chu trình CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 1. Giới thiệu Bài toán. Thành phố Königsberg, Đức nằm trên một con sông, có hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Bài toán đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không? CuuDuongThanCong.com https://fb.com/tailieudientucntt 3 Năm 1736, nhà toán học Leonhard Euler đã chứng minh rằng điều đó là không thể được. CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 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 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 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à ngắn nhất? CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 2. Các khái niệm cơ bản Định nghĩa. Một đồ thị vô hướng (undirected graph) G=(V, E) được định nghĩa bởi: • Tập hợp V ≠ ∅ được gọi là tập các đỉnh (vertex) và n = |V| gọi là cấp của đồ thị; • Tập hợp E là tập các cạnh (edge) của đồ thị; Mỗi cạnh e∈E được liên kết với một cặp đỉnh {i, j}, không phân biệt thứ tự CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 Đỉnh kề Định nghĩa. Trên đồ thị vô hướng, xét cạnh e được liên kết với cặp đỉnh
