Bài giảng Toán rời rạc: Chương 7 Lý thuyết đồ thị cung cấp cho người học những kiến thức như: Lý thuyết đồ thị được khởi đầu từ vài trăm năm trước (1736 với bài toán 7 cây cầu thành Konigsberg – Nga, và được gắn với các tên tuổi lớn như Euler, Gauss, Hamilton ); Đường một nét Euler, chu trình Hamilton; Tìm đường đi ngắn nhất, Dijkstra; Cây khung nhỏ nhất, Prim, Kruskal. | TOÁN RỜI RẠC DISCRETE MATHEMATICS Bùi Thị Thủy Đặng Xuân Thọ Support 2 Full name Đặng Xuân Thọ Mobile Email thodx@ Website http thodx Toán rời rạc - ĐHSPHN Chương 7. Lý thuyết đồ thị 3 Lý thuyết đồ thị được khởi đầu từ vài trăm năm trước 1736 với bài toán 7 cây cầu thành Konigsberg Nga và được gắn với các tên tuổi lớn như Euler Gauss Hamilton. Đường một nét Euler chu trình Hamilton Tìm đường đi ngắn nhất Dijkstra Cây khung nhỏ nhất Prim Kruskal Toán Rời Rạc - ĐHSPHN Định nghĩa đồ thị 4 Định nghĩa Một đồ thị được hiểu là một bộ hai tập hợp hữu hạn tập hợp đỉnh và tập hợp cạnh nối các đỉnh này với nhau. Kí hiệu đồ thị là G Graph tập đỉnh là V vertex tập cạnh là E edge . Đỉnh Đỉnh Cạnh Cạnh Bản đồ giao thông Mạng máy tính Đồ thị vô hướng 5 Ví dụ Cho tập V 2 3 4 5 6 . Hãy biểu diễn quan hệ nguyên tố cùng nhau của tập trên. Quan hệ này được biểu diễn bằng đồ thị sau 2 3 6 4 5 Toán Rời Rạc - ĐHSPHN Đồ thị vô hướng 6 Đồ thị vô hướng G V E trong đó V là tập hợp các phần tử gọi là đỉnh E là tập hợp mỗi phần tử là một cặp không thứ tự u v của hai đỉnh thuộc V. u v được gọi là cạnh nối đỉnh u và đỉnh v. Ta có u v v u Toán Rời Rạc - ĐHSPHN Đồ thị có hướng 7 Ví dụ Cho tập V 2 3 4 5 6 . Hãy biểu diễn quan hệ aRb a là ước của b và a b. 6 2 3 4 5 Toán Rời Rạc - ĐHSPHN Đồ thị có hướng 8 Định nghĩa Đồ thị có hướng kí hiệu G V E trong đó V là tập hợp các phần tử gọi là đỉnh E là tập hợp mỗi phần tử là một cặp có thứ tự u v của hai đỉnh của tập V u v được gọi là cung nối từ u đến v. Chú ý u v v u Toán Rời Rạc - ĐHSPHN Đồ thị có hướng 9 Ví dụ Khi nghiên cứu tính cách của nhóm người ta thấy một số người có thể có ảnh hưởng lên suy nghĩ của những người khác. Mỗi người của nhóm được Mai Lan biểu diễn bởi một đỉnh Khi người a có ảnh hưởng lên người b thì giữa đỉnh a và b được nối bằng cạnh có hướng. Bình My Toán Rời Rạc - ĐHSPHN Một số thuật ngữ cơ bản 10 Với cạnh e u v E u v V khi đó e là cạnh liên thuộc u và v. u v được gọi là kề nhau hay láng .
