Bài giảng môn Lý thuyết đồ thị

Bài giảng Lý thuyết đồ thị bao gồm những nội dung về các khái niệm cơ bản; đồ thị đẳng cấu; cây; đồ thị phẳng; tô màu; dòng. Bài giảng phục vụ cho các bạn chuyên ngành Toán học và những bạn quan tâm tới lĩnh vực này, mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Lý thuyết đồ thị LÝ THUYẾT ĐỒ THỊ s THÔNG TIN THAM KHẢO Giới thiệu tài liệu tất cả ngành toán bao gồm các hướng dẫn  phương pháp học tập : http://www.cargalmathbooks.com/#Principles of  Hamilton http://www.densis.fee.unicamp.br/~moscato/Hamilton.html Các ngành toán học http://www.math.fau.edu/locke/graphthe.htm http://www.graphtheory.com/ http://www.imada.sdu.dk/Research/Digraphs/ s TÀI LIỆU THAM KHẢO Toán học rời rạc ứng dụng trong tin học – Kenneth H. Rosen    (Bản dịch tiếng Việt NXB KHKT 1997) Graph, Networks and algorithms – M. N. S. Swamy,    K. ThulasiramanJohn Wiley & Sons, Inc. 1981. Discrete mathematics, Kenneth A. Ross .                Charles R.B. Wright, Prentice­Hall, 1988 s NỘI DUNG Các khái niệm cơ bản Đồ thị đẳng cấu Cây Đồ thị phẳng Tô màu Dòng s LỊCH SỬ Bài toán : Một khối đa diện đều có 12 mặt và 20 góc. Mỗi mặt là ngũ giác đều và 3 cạnh gặp nhau ở mỗi góc. Mỗi góc là một thành phố. Tìm đường đi qua 20 thành phố mỗi thành phố đúng 1 lần. s LỊCH SỬ Cầu Konigsberg. s MỘT VÀI ỨNG DỤNG Vẽ ngôi nhà của Santa Claus bằng 1 nét duy nhất. s MỘT VÀI ỨNG DỤNG Làm thế nào để 3 ngôi nhà và 3 nhà máy nối nhau mà không có  đường cắt nhau.  Nhà A  Nhà B  Nhà C  Gaz  Nước  Điện s MỘT VÀI ỨNG DỤNG Kết quả một bảng thi đấu vòng tròn giữa 6 đội banh. Mũi tên hướng từ A đến B chỉ đội thắng là A. A B F C E D Ba ông chồng ghen cùng với 3 bà vợ qua 1 con sông. Đò chỉ chở tối đa 2 người 1 chuyến:  hoặc là 1 chồng và 1 bà vợ hoặc 2 bà vợ. s MỘT SỐ QUI ƯỚC Cho x là một số thực : số nguyên  x    x số nguyên  x    x, Đồ thị  =  hay  =  Tập đỉnh V = {A, B, C, …, P} Tập cạnh E = {a, b, c, …, m} Đồ thị trống   = < ,  > =  s LÝ THUYẾT ĐỒ THỊ s ĐỒ THỊ Biểu diễn bằng hình vẽ của đồ thị  Đỉnh Vòng Cạnh Cạnh song  h A song g b c e C G Đỉnh cô  f a lập B d H D Cạnh treo s ĐỒ THỊ Biểu diễn bằng tập hợp của đồ thị  =  A h g Tập đỉnh V b c e V = {A, B, C, D, G, H} C G a f Tập cạnh E B d H D E = {a, b, c, d, e, f, g, h} Quan hệ tới I I = {CaB, AbB, AcB, BdH, AeH, BfG, AgG, GhG} s ĐỒ THỊ Biểu diễn bằng ma trận của đồ thị  A h A B C D G H g A 0 2 0 0 1 1 b c e B 2 0 1 0 1 1 C G C 0 1 0 0 0 0 a f D 0 0 0 0 0 0 B d H D G 1 1 0 0 1 0 H 1 1 0 0 0 0 s ĐỒ THỊ Bậc của đỉnh là số cạnh tới của đỉnh. deg(A) = 4 A h g b c e deg(C) = 1 C deg(G) = 4 G a f B d D deg(D) = 0 H deg(B) = 5 deg(H) = 2 s ĐỒ THỊ Bổ đề : Tổng bậ ...