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

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:279

Thêm vào BST

Báo xấu

92
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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, PrenticeHall, 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ậc bằng 2 lần số cạnh. Thí dụ minh họa A h g b c e C G a f B d H D Tồng bậc = 4+5+1+0+4+2 = 16. Số cạnh = 8. s
ĐỒ THỊ Chứng minh : P = “Tổng bậc bằng 2 lần số cạnh”. Pi = “Đồ thị i cạnh có tổng bậc bằng 2i”. P = (Pi)j N, N là tập số nguyên tự nhiên. Đồ thị có 1 cạnh thì tổng bậc bằng 2 P1 đúng. Giả sử Pn đúng đồ thị n cạnh có tổng bậc bằng 2n”. Lấy đồ thị có n+1 cạnh, chọn 1 cạnh bất kỳ a. (= a) có n cạnh tổng bậc của = 2n. Tổng bậc của = tổng bậc của +2 = 2(n+1). Pn+1 đúng. s
ĐỒ THỊ Bổ đề : Số đỉnh bậc lẻ là số chẵn. Thí dụ minh họa : A B C D E F Có 4 đỉnh bậc chẵn. Có 2 đỉnh bậc lẻ là C, F. s
ĐỒ THỊ Chứng minh : Tổng bậc = Tổng bậc các đỉnh bậc chẵn + Tổng bậc các đỉnh bậc lẻ. Tổng bậc các đỉnh bậc chẵn là số chẵn. Tổng bậc các đỉnh bậc lẻ là số chẵn Số đỉnh bậc lẻ là số chẵn. s
ĐỒ THỊ HỘI B C B C A F A G F E D E D B C = A G F E D s