Đường đi Hamilton

Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại, nó là kiến thức cơ sở cho nhiều ngành khoa học kỹ thuật khác nhau như điện tử, hóa học, ngôn ngữ học, kinh tế học, máy tính,...
Nội dung trích xuất từ tài liệu:
Đường đi HamiltonMỤC LỤC MỞ ĐẦU Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứngdụng hiện đại, nó là kiến thức cơ sở cho nhiều ngành khoa học kỹ thuật khác nhau nhưĐiện tử, Hóa học, Ngôn ngữ học, Kinh tế học, Máy tính, .... Trong Lý thuyết đồ thị thì bài toán tìm đường đi, chu trình Hamilton có rất nhiềuứng dụng trong thực tế. Vì vậy nhóm 5 chọn đề tài “ Đường đi Hamilton” để nghiên cứukỹ hơn. CÔNG VIỆC CỦA CÁC THÀNH VIÊN TRONG NHÓM 5 Nhận xét củaTT Họ và tên Công việc Ghi chú Giáo viên Nghiên cứu về đường đị 1 Hồ Trung Cang và chu trình Hamilton Nghiên cứu chương Đại 2 Nguyễn Thành cương về đồ thị Nghiên cứu về đường đị 3 Phạm Đức Mạnh và chu trình Hamilton Tìm ứng dụng của 4 Hữu Đệ Đường đi, chu trình Hamilton Tìm ứng dụng của 5 Nguyễn Thị Xuân Đường đi, chu trình Hamilton CHƯƠNG I : ĐẠI CƯƠNG VỀ ĐỒ THỊI. Các khái niệm cơ bản: 1. Đồ thị, đỉnh, cạnh: * Đồ thị vô hướng G = (V,E) gồm một tập V các đỉnh và tập E các cạnh. Mỗi cạnhe e E được liên kết với một cặp đỉnh v, w ( không kể thứ tự). v w * Đồ thị có hướng G = (V,E) gồm một tập V các đỉnh và tập E các cạnh có hướnggọi là cung. Mỗi cạnh e ạ E được liên kết với một cặp đỉnh v, w có thứ tự. v w Cho đồ thị có hướng G = (V,E). Nếu ta thay đổi mỗi cung của G bằng một cạnh,thì đồ thị vô hướng nhận được gọi là đồ thị lót của G. Ghi chú : Đồ thị vô hướng có thể xem là đô fthij có hướng trong đó mỗi cạnh e =(v,w) tương ứng với hai cung (v,w) và (w,v). Cho đồ thị (có hướng hoặc vô hướng) G = (V,E). Nếu cạnh e liên kết đỉnh v, w thì ta nói đỉnh e liên thuộc đỉnh v, w, các đỉnh v, wliên thuộc cạnh e, các đỉnh v, w là các đỉnh biên của cạnh e và đỉnh v kề với đỉnh w. Nếu chỉ có duy nhất một cạnh e liên thuộc với cặp đỉnh v, w, ta viết e = (v, w).Nếu e là cung thì v gọi là đỉnh đầu và w gọi là đỉnh cuối của cung e. Nếu có nhiều cạnh liên kết với cùng một cặp đỉnh thì ta nói đó là cạnh song song. Cạnh có 2 đỉnh liên kết trùng nhau gọi là khuyên. Đỉnh không kề với đỉnh khác gọi là đỉnh cô lập. Số đỉnh của đồ thị gọi là bậc của đồ thị, số cạnh hoặc số cung của đồ thị gọi làcỡ của đồ thị. Đồ thị hữu hạn là đồ thị có bậc và cỡ hữu hạn. Đồ thị đơn là đồ thị không có khuyên và không có cạnh song song. Đồ thị vô hướng đủ là đồ thị mà mọi cặp đỉnh đều kề nhau. Đồ thị có hướng đủ là đồ thị có đồ thị lót đủ. 2. Bậc, nửa bậc vào, nửa bậc ra: Cho đồ thị G = (V, E) Bậc của đỉnh v ỉ V là tổng số cạnh liên thuộc với nó và ký hiệu là d(v). Nếu đỉnhcó khuyên thì mỗi khuyên được tính là 2 khi tính bậc, như vậy: d(v) :=Số cạnh liên thuộc + 2*Số khuyênTừ định nghĩa suy ra , đỉnh cô lập trong đồ thị đơn là đỉnh có bậc bằng 0.Số bậc lớn nhất của G ký hiệu là ∆G , số bậc nhỏ nhất của G gọi là δ G . Đỉnh treo là đỉnh có bậc bằng 1. Nửa bậc: Cho G = (V,E) là đồ thị có hướng, v ớ V. Nửa bậc ra của đỉnh v, kí hiệu là dO(v), làsố cung đi ra từ đỉnh v ( v là đỉnh đầu), và nửa bậc vào của đỉnh v ỉ V, kí hiệu dI(v), là sốcung đi tới đỉnh v ( v là đỉnh cuối).Ví dụ : x2 e4 x6 e1 x4 x1 e2 e3 x5 x3Trong đồ thị này, ta có :d(x1) = 6 , d(x2) = d(x3) = 4, d(x4) = 3 , d(x5) = 0 , d(x6) = 1Đỉnh x1 có hai khuyên liên thuộc.Có hai cạnh song song liên thuộc đỉnh x2 và đỉnh x3.Đỉnh x5 là đỉnh cô lập.Đỉnh x6 là đỉnh treo.Ví dụ : Xét đồ thị có hướng sau x2 x6 x4 x1 x5 x3Trong đồ thị có hướng này ta có:dI(x1) = 0 , dO(x1) = 2, dI(x2) = 1 , dO(x2) = 2dI(x3) = 2 , dO(x3) = 1, dI(x4) = 2 , dO(x4) = 2dI(x5) = 1 , dO(x5) = 1, dI(x6) = 2 , dO(x6) = 0* Bổ đề bắt tay ( Hand Shaking Lemma) : Cho đồ thị G = (V,E). Khi đó : i) Tổng bậc các đỉnh của đồ thị là số chẵn và = d (v) = 2* card(E) . vd V ii) Nếu G là đồ thị có hướng thì : � (v) = � (v) = card(E) , trong đó card(E) là d v�V O d v�V Isố phần tử của tập E. Chứng minh : i) Mỗi cạnh e = (u,v) ạ E tham gia tính 1 bậc của đỉnh u, một bậc của đỉnh v. Từ đósuy ra công thức i). ii) Mỗi cung e = (u,v) ỗ E tham gia tính 1 bậc ra của đỉnh u, một bậc vào của đỉnhv. Từ đó suy ra công thức ii).* Hệ quả : Số dỉnh bậc ...