Giáo án môn lý thuyết đồ thị

Lý thuyết đồ thị là nghành khoa học đã có từ lâu nhưng lại có rất nhiều ứng dụng hiện đại. Những ý tưởng cơ sở ban đầu của nó được đưa ra từ những năm đầu thế kỷ 18 bởi nhà toán học người Thuỵ Sỹ là Leonhard Euler. Lý thuyết đồ thịđược dùng để giải quyết các bài toán thuộc nhiều lĩnh vực khác nhau. Chẳng hạn: Dùng mô hình đồ thịđể xác định xem hai máy tính trong một mạng máy tính có trao đổi thông tin được với nhau hay không?. Đồ...
Nội dung trích xuất từ tài liệu:
Giáo án môn lý thuyết đồ thị Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ €GIÁO ÁN MÔN LÝ THUYẾT ĐỒ THN Số tiết học: 60 tiết ( 45 tiết lý thuyết + 15 tiết thực hành)Tài liệu tham khảo: 1) Toán rời rạc, PGS. TS Đỗ Đức Giáo, Nhà xuất bản Đại học Quốc gia Hà Nội 2002 2) Toán rời rạc, Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Nhà xuất bản Đại học Quốc gia Hà Nội 2003 3) Giáo trình Lý thuyết đồ thị, Nguyễn Thanh Hùng, Nguyễn Đức Nghĩa 4) Toán học rời rạc ứng dụng trong tin học, Dịch từ Discrete Mathematics and Its Applications, Nhà xuất bản khoa học kỹ thuậtChương 1 CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THN (9 tiết)1.1 Giới thiệu Lý thuyết đồ thị là nghành khoa học đã có từ lâu nhưng lại có rất nhiều ứng dụng hiện đại. Nhữngý tưởng cơ sở ban đầu của nó được đưa ra từ những năm đầu thế kỷ 18 bởi nhà toán học người ThuỵSỹ là Leonhard Euler. Lý thuyết đồ thị được dùng để giải quyết các bài toán thuộc nhiều lĩnh vực khác nhau. Chẳnghạn: Dùng mô hình đồ thị để xác định xem hai máy tính trong một mạng máy tính có trao đổi thôngtin được với nhau hay không?. Đồ thị với các trọng số được gắn cho các cạnh có thể dùng để giảiquyết bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng lưới giao thông. Chúng tacũng có thể phân biệt các hợp chất hoá học có cùng công thức phân tử nhưng có cấu trúc khác nhaunhờ vào đồ thị...1.2 Các định nghĩa và tính chất cơ bảnĐịnh nghĩa 1: Giả sử V là một tập khác rỗng các phần tử nào đó và E ⊆ VxV (E là tập con của tích đề cácVxV). Bộ G = (V, E) được gọi là một đồ thị. Mỗi phần tử v ∈ V được gọi là một đỉnh của đồ thị, V được gọi là tập các đỉnh của đồ thị. Mỗi phần tử e = (u, v) ∈ E được gọi là một cạnh của đồ thị, E được gọi là tập các cạnh của đồ thị.Ví dụ 1:G = (V = {v1, v2, v3, v4,...}, E = {e1 = (v1,v2), e2 = (v1,v3), e3 = (v2,v3), e4 = (v3,v4),... }) v2 e1 e3 v1 v3 e2 e4 v4 .... Như vậy ta có thể hình dung đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnhnày với nhau. 1NguyÔn Minh §øc - §HQG Hµ Néi Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞChú ý: Nếu tập V là tập hữu hạn các phần tử thì G = (V,E) được gọi là đồ thị hữu hạn. Từ đây về sau chủyếu ta nghiên cứu các đồ thị hữu hạn. (có thể coi đây là một định nghĩa về đồ thị)Ví dụ 2:G = (V={Thanh hoá, Nghệ an, Hà nội, TP.HCM},E={(Thanh hoá,Nghệ an),(Thanh hoá, Hà nội),(Nghệ an, Hà nội), (Hà nội, TP.HCM) }) Thanh hoá Nghệ an Hà nội TP.HCMĐịnh nghĩa 2: a) Hai đỉnh được gọi là kề nhau nếu có cạnh nối hai đỉnh đó với nhau. Cạnh nối hai đỉnh được gọilà cạnh liên thuộc. b) Hai cạnh được gọi là kề nhau nếu giữa chúng có đỉnh chung. c) Nếu e = (v,v) là một cạnh của đồ thị thì e được gọi là một khuyên. Trong trường hợp này đồ thịđược gọi là giả đồ thị.Ví dụ 3: v1 v2 v3 e3 e1 e2v1 và v2 được gọi là hai đỉnh kề nhau, e1 được gọi là cạnh liên thuộc hai đỉnh v1 và v2.e1 và e2 được gọi là hai cạnh kề nhau, e3 được gọi là một khuyên.Định nghĩa 3: a) Nếu mỗi cạnh e = (u , v) ∈ E là không phân biệt thứ tự của các đỉnh u và v, (tức là từ u tới vkhông kể hướng) thì ta nói đồ thị G = (V,E) là đồ thị vô hướng. b) Nếu mỗi cạnh e = (u , v) ∈ E có phân biệt thứ tự của các đỉnh u và v, (tức là từ u tới v khác vớitừ v tới u) thì ta nói đồ thị G = (V,E) là đồ thị có hướng. Cạnh của đồ thị có hướng còn được gọi làcung. Tây hồVí dụ 4: v1 CVThủ lệ Hồ gươm v2 v3 TTCPQG Đồ thị vô hướng Đồ thị có hướng 2NguyÔn Minh §øc - §HQG Hµ Néi Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞĐịnh nghĩa 4: Đồ thị G =(V,E) được gọi là đơn đồ thị nếu giữa hai đỉnh bất kỳ của đồ th ...