giáo trình lý thuyết đồ thị

Tài liệu nhỏ này được biên soạn nhân dịp tôi và các bạn làm đề tài Toán rời rạc. Nội dung chủ yếu của tài liệu này viết về lí thuyết đồ thị, và đi sâu về đồ thị Halmilton. Xin nói rằng, tôi không lấy làm hãnh diện khi viết xong tài liệu này. Đây chỉ là một chút sự góp nhặt nhỏ bé từ các tài liệu khác...
Nội dung trích xuất từ tài liệu:
giáo trình lý thuyết đồ thị Bi ên soạn: Lê Đình HuyLời nói đầu Tài liệu nhỏ này được biên soạn nhân dịp tôi và các bạn làm đề tài Toán rờirạc. Nội dung chủ yếu của tài liệu này viết về lí thuyết đ ồ thị, và đi sâu về đồ thịHalmilton. Xin nói rằng, tôi không lấy làm hãnh diện khi viết xong tài liệu này.Đây chỉ là một chút sự góp nhặt nhỏ bé từ các tài liệu khác (chủ yếu là: Đại cươngvề toán học hữu hạn – Hoàng Chúng) mà được tôi rút ra để tổng hợp l ại những gìđã được học. Tất nhiên một mình tôi thì không thể biên soạn được tài liệu này. Trong quátrình biên soạn, xin chân thành cám ơn nhóm đề tài toán rời rạc của lớp tôi gồmcác bạn: Cù Minh Khương; Phạm Thị Th u H à; Phan Phương Dung; Nguyễn ThiThùy Dung; Phạm Thị Nâu. C ám ơn các thầy cô đã đón nhận. Chắc chắn tài liệusẽ có những sai sót không tránh khỏi, hi vọng được thầy cô, bạn đọc đón nhận vàgóp ý. Mùa xuân, Canh Dần, TP Hồ Chí Minh Lê Đình Huy 1 Bi ên soạn: Lê Đình Huy Sơ lược về GraphI Graph (Đồ thị): H ai chữ “đồ thị” vẫn thường xuyên xuất hi ện trong đời sống toán học và cảtrong đời sống hàng ngày. Trong các giờ toán, chúng ta từng nói tới đồ thị của các hàm số.Hay trong cáccông sở, các nhân viên phải lập các biểu đồ theo dõi lượng tiêu thụ điện … Nóichung, khái niệm đồ thị là một khái niệm khá quen thuộc với chúng ta nhằm biểudiễn tương quan qua lại giữa 2 hoặc nhiều đối tượng toán học khác nhau. Ở đây, khái niệm đồ thị vẫ được dùng theo nghĩa đó nhưng nó mang tính trừutượng hơn. Lí thuyết đồ thị (tiếng Anh và tiếng Đức đọc là “graph”) nghiên cứu những tínhchất toán học, những quan hệ mà không phụ thuộc vào bản chất riêng của nhữngmối quan hệ này. Để tránh bị hiểu nhầm là đồ thị của hàm số, trong tài liệu nàychúng tôi sẽ dùng thuật ngữ “graph”. Một graph có thể hiểu đơn giản là một hệ thống các đỉnh và các cạnh nối cácđỉnh này với nhau. Một graph G được xác định bởi: _ Tập hợp V những phần tử gọi là đỉnh của G. _ Tập hợp E những phần tử gọi là cạnh của G. Giả thuyết rằng V, E là các tập hữu hạn, V không rỗng.Kí hiệu: G(V,E) hayV(G),V(E) để chỉ rõ V,E lần lượt là tập đỉnh, tập cạnh của graph G. Một cạnh (u, v) của G thường được viết là uv (hay vu), ta nói cạnh uv nối uvới v, lúc đó, ta nói u và v là 2 đỉnh kề nhau. VD1: Graph G được xác định bởi: V = { a,b,c,d,e} E = { ab,ac,ad,ae,bd,bc,cd,ce}Tổng quát hơn khái niệm graph, chúng ta có khái niệm đa graph: Một đa graph G được xác định bởi: 2 Bi ên soạn: Lê Đình Huy _ Tập hợp V những phần tử gọi là đỉnh củ a G. _ Bộ E những phần tử gọi là cạnh của G; mỗi cạnh là một cặp không sắp thứ tựcủa 2 đỉnh. Giả thuyết rằng V là các tập hữu hạn, không rỗng và E là một bộ gồm hữu hạnphần tử. Một bộ (khác với một tập hợp) có thể chứa nhiều phần tử trùng n hau.Trong đagraph, E có thể chứa nhiều cạnh cùng nối một cặp đỉnh.Mỗi cạnh là một cặp không sắp (không sắp thứ tự) của 2 đỉnh không nhất thiếtkhác nhau( như graph). VD2: Đa graph G được xác định bởi: V = {u,v,x,y} E = {uv,uv,ux,xy,yy} Đ a graph G có 2 cạnh uv cùng nối 1 cặp đỉnh,ta gọi đó là những cạnh songsong (cạnh bội). Cạnh yy có 2 đầu mút trùng nhau, ta gọi là khuyên. Một đa graph không có cạnh song song và không có khuyên (như VD1) gọi làmột graph. ( Các thuật ngữ về graph hiện chưa thống nhất. Có tác giả dùng đồ thị (đa đồ thị)thay cho graph (đa graph). Có tác giả gọi đa graph và graph lần lượt là graph vàđơn graph. Có tác giả gọi đa graph là giả graph, một giả graph không có khuyêngọi là đa gr aph, một đa graph không có cạnh song song gọi là graph. Vì vậy, khiđọc các tài liệu người đọc cần chú ý đến thuật ngữ mà tác giả sữ dụng.)II Biểu diễn graph: Ta thường dùng biểu diễn hình học của graph như sau: biểu diễn các đỉnh củagraph bằng các điểm (vòng tròn nhỏ,ô vuông nhỏ) và nối 2 điểm bằng 1 đường(cong hay thẳng) khi cặp điểm đó ứng với 1 cạnh của graph. Đinh lí: Mọi graph G đều có thể biểu diễn bằng 1 hình trong không gian. 3 Bi ên soạn: Lê Đình Huy c d b e a Biểu diễn của graph trong VD1 Biểu diễn graph G trong VD2 Trong nhiều trường hợp (nhất là với graph có nhiều đ ...