Luận văn Thạc sĩ Toán học: Đặc trưng Euler và một số ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST

Báo xấu

26
lượt xem 5
download

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

Đặc trưng Euler (còn được gọi là bất biến Euler, công thức Euler, hoặc đặc trưng Euler-Poincaré ) là một bất biến tôpô, là số không đổi đặc trưng cho hình dạng hoặc cấu trúc của một không gian tôpô không phụ thuộc vào cách nó bị biến dạng. Đặc trưng Euler thường được ký hiệu là X. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Đặc trưng Euler và một số ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ------------------------------- TRẦN THỊ ÁNH DƢƠNG ĐẶC TRƢNG EULER VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ------------------------------- TRẦN THỊ ÁNH DƢƠNG ĐẶC TRƢNG EULER VÀ MỘT SỐ ỨNG DỤNG Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. Tạ Duy Phƣợng THÁI NGUYÊN - 2018
1 Mục lục Lời nói đầu 3 1 Một số kiến thức sơ lược về lý thuyết đồ thị 5 1.1. Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1. Định nghĩa 1 . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2. Định nghĩa 2 . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3. Định nghĩa 3 . . . . . . . . . . . . . . . . . . . . . . 7 1.1.4. Định nghĩa 4 . . . . . . . . . . . . . . . . . . . . . . 7 1.2. Chu trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3. Một số dạng đồ thị . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1. Đồ thị phẳng . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2. Đồ thị đối ngẫu . . . . . . . . . . . . . . . . . . . . 8 1.3.3. Đồ thị liên thông . . . . . . . . . . . . . . . . . . . 10 1.3.4. Đơn đồ thị . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.5. Đồ thị đầy đủ . . . . . . . . . . . . . . . . . . . . . 11 1.3.6. Đồ thị phân đôi đầy đủ . . . . . . . . . . . . . . . 11 1.4. Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Một số cách chứng minh công thức đặc trưng Euler 14 2.1. Chứng minh dựa trên lý thuyết đồ thị . . . . . . . . . . . . 14 2.2. Chứng minh sử dụng phương pháp điện tích . . . . . . . . . 19 2.2.1. Điện tích . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.2. Điện tích đối ngẫu . . . . . . . . . . . . . . . . . . 20
2 2.3. Chứng minh dựa trên phương pháp sử dụng góc . . . . . . . 21 2.3.1. Tổng của góc . . . . . . . . . . . . . . . . . . . . . 21 2.3.2. Góc hình cầu . . . . . . . . . . . . . . . . . . . . . 22 2.4. Chứng minh của Euler . . . . . . . . . . . . . . . . . . . . . 27 2.5. Một số chứng minh khác . . . . . . . . . . . . . . . . . . . . 30 2.5.1. Phương pháp loại bỏ tam giác . . . . . . . . . . . 30 2.5.2. Chu trình Euler . . . . . . . . . . . . . . . . . . . . 32 3 Một số ứng dụng và bài toán liên quan 35 3.1. Khối đa diện Platon . . . . . . . . . . . . . . . . . . . . . . 35 3.2. Trái bóng đá và bài toán phủ mặt cầu . . . . . . . . . . . . 38 3.3. Đặc trưng Euler và một số ứng dụng trong lý thuyết đồ thị . 39 3.4. Định lí Pick . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.5. Định lí Sylvester-Gallai . . . . . . . . . . . . . . . . . . . . 47 3.6. Định lí về các đường thẳng đơn sắc . . . . . . . . . . . . . . 49 Kết luận 56
3 Lời nói đầu Xét các khối đa diện đều sau Tên Đỉnh V Cạnh E Mặt F V −E+F Tứ diện 4 6 4 2 Hình lập phương 8 12 6 2 Bát diện 6 12 8 2 Thập nhị diện 20 30 12 2 Nhị thập diện 12 30 20 2 Hình 1 Ta nhận thấy V − E + F = 2 với tất cả năm khối đa diện trên. Số 2 không đổi được gọi là đặc trưng Euler. Đặc trưng Euler, hay công thức V − E + F = 2 là một trong 17 phương trình làm thay đổi thế giới (xem [1]). Do tính bản chất và quan trọng của công thức này, đặc trưng Euler có đến vài chục cách chứng minh (xem [5]) và có nhiều ứng dụng (xem thí dụ, [6]). Đặc trưng Euler (còn được gọi là bất biến Euler, công thức Euler, hoặc đặc trưng Euler-Poincaré ) là một bất biến tôpô, là số không đổi đặc trưng cho hình dạng hoặc cấu trúc của một không gian tôpô không phụ thuộc vào cách nó bị biến dạng. Đặc trưng Euler thường được ký hiệu là X . Đặc trưng Euler X (S) của một đa giác phẳng S được chia thành các tam giác bằng số đỉnh trừ đi số cạnh cộng với số mặt của tam giác trong đa
4 giác đó: X (S) = V − E + F. Bất kỳ đa diện lồi cũng có đặc trưng X = V − E + F = 2, trong đó V , E và F tương ứng là số đỉnh (góc), số cạnh và số mặt của khối đa diện. Leonhard Euler, tên của ông được đặt cho khái niệm này, đã có các công trình nghiên cứu đầu tiên về đặc trưng này. Ta cũng có thể mở rộng đặc trưng Euler (tức công thức X = 2) cho hình cầu và áp dụng cho các khối đa diện cầu. Luận văn được chia làm ba chương. Chương 1. Một số kiến thức sơ lược về lý thuyết đồ thị. Chương 2. Một số cách chứng minh công thức đặc trưng Euler. Chương 3. Một số ứng dụng và bài toán liên quan. Tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến PGS. TS. Tạ Duy Phượng, người thầy đã định hướng chọn đề tài và tận tình hướng dẫn để tôi có thể hoàn thành luận văn này. Tôi xin bày tỏ lòng biết ơn chân thành tới các Thầy cô giáo thuộc khoa Toán - Tin, Phòng Đào tạo trường Đại học Khoa học - Đại học Thái Nguyên đã giúp đỡ tôi trong suốt quá trình học tập tại trường. Tôi cũng xin bày tỏ lời cảm ơn sâu sắc đến trường trung học phổ thông Lê Chân đã quan tâm và tạo điều kiện giúp đỡ tôi trong quá trình học tập và công tác. Cuối cùng tôi xin gửi lời cảm ơn đến gia đình, bạn bè đồng nghiệp đã cổ vũ, động viên và tạo điều kiện để tôi hoàn thành luận văn này. Thái Nguyên, tháng 5 năm 2018 Tác giả Trần Thị Ánh Dương
5 Chương 1 Một số kiến thức sơ lược về lý thuyết đồ thị Chương này trình bày sơ lược các khái niệm cơ bản của lý thuyết đồ thị để bổ trợ cho một số cách chứng minh công thức đặc trưng Euler dựa trên lý thuyết đồ thị trong chương sau. Nội dung chính của chương được tham khảo từ tài liệu [2,3,9]. 1.1. Định nghĩa đồ thị 1.1.1. Định nghĩa 1 Đồ thị (graph) G = (V, E) là một bộ gồm các đỉnh V và các cạnh E, trong đó V 6= ∅ và mỗi cạnh nối với hai đỉnh (không nhất thiết phân biệt). Nếu cạnh e tương ứng với hai đỉnh u, v thì ta nói u và v là hai đỉnh kề nhau. Ký hiệu e = (u, v) hay e = (v, u). Cạnh (u, u) tương ứng với hai đỉnh trùng nhau gọi là một vòng hay khuyên(loop) tại u. Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh được gọi là hai cạnh song song hay cạnh bội. Cặp đỉnh không sắp thứ tự được gọi là cạnh vô hướng (cạnh). Cặp đỉnh sắp thứ tự được gọi là cạnh có hướng (cung).
6 Hình 1.1 1.1.2. Định nghĩa 2 Đồ thị G được gọi là đồ thị vô hướng nếu tất cả các cạnh của G đều là cạnh vô hướng. Hình 1.2 Bậc của một đỉnh trong đồ thị vô hướng là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Kí hiệu là: deg(v). - Đỉnh bậc 0 được gọi là đỉnh cô lập. - Đỉnh có bậc bằng 1 được gọi là đỉnh treo. Ví dụ. Cho đồ thị sau: Hình 1.3 Ta có: deg(a) = 4, deg(b) = 5, deg(c) = 4, deg(d) = 0, deg(e) = 1,
7 deg(f ) = 4, deg(g) = 4. 1.1.3. Định nghĩa 3 Đồ thị G được gọi là đồ thị có hướng nếu tất cả các cạnh của G đều là cạnh có hướng. Hình 1.4 1.1.4. Định nghĩa 4 Đồ thị G1 được gọi là đồ thị con của đồ thị G nếu tập đỉnh và tập cạnh của G1 tương ứng là tập con của tập đỉnh và tập cạnh của G. 1.2. Chu trình Đường đi (path) có độ dài n từ v0 đến vn với n là một số nguyên dương, trong một đồ thị vô hướng là một dãy các cạnh liên tiếp v0 v1 , v1 v2 , ..., vn−1 vn . Đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là đỉnh cuối. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là chu trình. Đường đi (Chu trình) không qua cạnh nào lần thứ hai gọi là đường đi đơn (Chu trình đơn). Chu trình đơn chứa tất cả các cạnh của đồ thị được gọi là chu trình Euler. Đồ thị vô hướng được gọi là đồ thị Euler nếu nó có chu trình Euler.
8 Ví dụ. Trong Hình 1.5, đồ thị G1 có chu trình Euler: a, e, c, d, e, b, a. Cả hai đồ thị G2 và G3 không có chu trình Euler. Hình 1.5 1.3. Một số dạng đồ thị 1.3.1. Đồ thị phẳng Đồ thị G là đồ thị phẳng nếu có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh. Hình 1.6 1.3.2. Đồ thị đối ngẫu 0 Đồ thị đối ngẫu của một đồ thị phẳng G là một đồ thị G trong đó có một đỉnh tương ứng cho mỗi miền mặt phẳng của đồ thị G và có mỗi cạnh tương ứng với mỗi cạnh của G kết nối hai miền kề nhau của G.
9 Hình 1.7: Đồ thị đối ngẫu Xác định đồ thị đối ngẫu từ một đồ thị phẳng Bước 1: Xác định các miền của đồ thị phẳng. Ta có đồ thị phẳng G, xác định các miền như sau: • Miền trong 1: Miền bị giới hạn bởi tam giác CDE. • Miền trong 2: Miền bị giới hạn bởi tam giác BCE. • Miền trong 3: Miền bị giới hạn bởi tam giác ABE. • Miền ngoài: Miền không bị giới hạn bởi hình ngũ giác ABCDE. Hình 1.8: Nối miền trong tam giác CDE với miền mà 3 cạnh DE , CD và CE tiếp xúc Bước 2: Xác định miền tiếp xúc với mỗi miền vừa xác định ở bước 1. Xét tam giác CDE (miền trong 1) ta thấy: • Cạnh DE, CD tiếp xúc với miền ngoài. • Cạnh CE tiếp xúc với tam giác BCE (miền trong 2). Ta thực hiện vẽ các đường cong nối từ tam giác CDE sang miền ngoài và tam giác BCE.
10 Tương tự ta xét với tam giác BCE và tam giác ABE. Hình 1.9: Nối miền trong tam giác BCE với miền mà 3 cạnh BC , BE và CE tiếp xúc Bước 3: Gọi H là đồ thị mới vừa tìm được, ta có H là đồ thị đối ngẫu của G. Hình 1.10: Nối miền trong tam giác ABE với miền mà 3 cạnh AB , AE và BE tiếp xúc 1.3.3. Đồ thị liên thông Một đồ thị liên thông nếu luôn tồn tại đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ví dụ. Trong Hình 1.11 đồ thị G là liên thông và đồ thị H là không liên thông.
11 Hình 1.11 1.3.4. Đơn đồ thị Đồ thị không có khuyên và cạnh bội được gọi là đơn đồ thị. Ngược lại, được gọi là đa đồ thị. 1.3.5. Đồ thị đầy đủ Là đơn đồ thị bao gồm n đỉnh mà mọi đỉnh đều có bậc n − 1 (mỗi đỉnh đều nối với n − 1 đỉnh còn lại). Ký hiệu: Kn . Ví dụ. Hình 1.12 1.3.6. Đồ thị phân đôi đầy đủ Là đơn đồ thị trong đó: - Các đỉnh của đồ thị chia làm hai tập con. - Mỗi cạnh nối một đỉnh từ tập này đến một đỉnh ở tập kia.
12 Kí hiệu: Km,n Ví dụ. Hình 1.13 1.4. Cây Cây là một đồ thị mà trong đó hai đỉnh bất kì đều được nối với nhau bằng đúng một đường đi. Cây là đồ thị vô hướng, liên thông và không có chu trình đơn. Hình 1.14: Cây Cây bao trùm (spanning tree) còn được gọi là cây khung của đồ thị G là cây con của đồ thị G , chứa tất cả các đỉnh của G. Hay nói cách khác, cây bao trùm của một đồ thị G là một đồ thị con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình. Cây khung của đồ thị liên thông G là một đồ thị con liên thông nhỏ nhất của G.
13 Hình 1.15: Cây khung
14 Chương 2 Một số cách chứng minh công thức đặc trưng Euler Chương này trình bày một số cách chứng minh công thức đặc trưng Euler. 2.1. Chứng minh dựa trên lý thuyết đồ thị Biểu diễn phẳng của một đồ thị chia mặt phẳng thành các miền, kể cả miền vô hạn. Ví dụ biểu diễn phẳng của đồ thị trên hình 2.1 chia mặt phẳng thành 6 miền. Chúng được gán nhãn như hình vẽ. Hình 2.1 Euler đã chứng minh rằng tất cả các biểu diễn phẳng của một đồ thị đều chia mặt phẳng thành cùng một số miền như nhau. Ông đã tìm ra mối quan hệ giữa số miền, số đỉnh và số cạnh của một đồ thị phẳng. Khi đó công thức đặc trưng Euler đối với đồ thị phẳng được phát biểu như sau Định lí. Nếu G là một đồ thị phẳng liên thông có V đỉnh, E cạnh và F
15 miền thì V − E + F = 2. Sau đây là một số cách chứng minh công thức đặc trưng Euler dựa trên cơ sở lý thuyết đồ thị. Chứng minh 2.1.1 (xem [2]). Gọi G là một đơn đồ thị phẳng liên thông với E cạnh và V đỉnh. Gọi R là số miền trong biểu diễn phẳng của G. Cần chứng minh R = E − V + 2. Trước tiên ta xác định biểu diễn phẳng của G. Ta sẽ chứng minh bằng cách xây dựng một dãy các đồ thị con G1 , G2 , ..., Ge = G, mỗi bước ghép thêm một cạnh vào đồ thị ở bước trước. Điều này làm được khi sử dụng phương pháp quy nạp toán học như sau. Lấy tùy ý một cạnh của G để nhận được G1 . Để nhận được Gn từ Gn−1 ta thêm tùy ý một cạnh liên thuộc với một đỉnh của Gn−1 và thêm một đỉnh khác liên thuộc với cạnh mới đó, nếu nó chưa có trong Gn−1 . Điều này làm được vì G liên thông. G sẽ nhận được sau khi e cạnh được ghép thêm vào các đồ thị tạo ra trước. Gọi Rn , En và Vn tương ứng là số miền, số cạnh và số đỉnh của biểu diễn phẳng của Gn do biểu diễn phẳng của G sinh ra. Ta sẽ chứng minh bằng quy nạp. Với n = 1, hệ thức R1 = E1 − V1 + 2 là đúng với G1 vì E1 = 1, V1 = 2 và R1 = 1. Hình 2.2 Giả sử Rn = En − Vn + 2. Gọi {an+1 , bn+1 } là cạnh gộp vào Gn để được Gn+1 . Có hai khả năng xảy ra. Trường hợp 1. Cả hai đỉnh an+1 , bn+1 đã thuộc Gn . Khi đó chúng phải ở trên biên của miền chung R nếu không thì không thể gộp cạnh {an+1 , bn+1 } vào Gn mà không có các cạnh cắt nhau (Gn+1 là phẳng). Cạnh mới này sẽ chia miền R thành hai miền con.
16 Hình 2.3 Do đó Rn+1 = Rn + 1, En+1 = En + 1 và Vn+1 = Vn . Vì vậy ta có công thức Rn+1 = En+1 − Vn+1 + 2. Trường hợp 2. Một trong hai đỉnh an+1 , bn+1 chưa thuộc Gn . Hình 2.4 Giả sử an+1 thuộc Gn còn bn+1 không thuộc Gn . Thêm cạnh này không sinh ra một miền mới nào, vì bn+1 phải ở trong miền có an+1 ở trên biên của nó. Do đó, Rn+1 = Rn . Nhưng En+1 = En + 1 và Vn+1 = Vn + 1. Vì vậy Rn+1 = En+1 − Vn+1 + 2. Vậy với mọi n ta đều có Rn = En − Vn + 2. Vì đồ thị gốc là Ge nhận được sau khi thêm e cạnh, Định lí được chứng minh. Công thức Euler được minh họa trong ví dụ sau: Ví dụ 2.1.1 Giả sử đơn đồ thị phẳng liên thông có 20 đỉnh, mỗi đỉnh đều có bậc bằng 3. Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền? Giải. Đồ thị phẳng này có 20 đỉnh, mỗi đỉnh đều có bậc bằng 3, do
17 vậy V = 20. Vì tổng số bậc của các đỉnh, 3V = 3.20 = 60, bằng hai lần số cạnh, tức là 2E, ta có E = 60 : 2 = 30. Do vậy theo công thức Euler, số các miền là R = E − V + 2 = 30 − 20 + 2 = 12. Chứng minh 2.1.2 (xem [8]). Đồ thị trong Hình 2.5 có năm đỉnh, bảy cạnh, bốn miền và 5 − 7 + 4 = 2. Hình 2.5 Nếu không tính vùng không giới hạn là miền thì công thức Euler trở thành V − E + F = 1. Xét một cây (một đồ thị phẳng liên thông và không có chu trình). Vì cây không có chu trình, miền duy nhất là miền không bị giới hạn, nên công thức Euler V − E + 1 = 2 hay V = E + 1. Do đó, số đỉnh của cây lớn hơn số cạnh 1 đơn vị. Ta dùng cách loại bỏ các cạnh ra khỏi đồ thị để chứng minh định lí. Xét một đồ thị phẳng liên thông. Chọn một cạnh bất kì. Cạnh có thể liên thuộc hai đỉnh hoặc là một khuyên. Hình 2.6
18 Giả sử cạnh liên thuộc hai đỉnh. Ta thu nhỏ cạnh cho đến khi nó biến mất hoàn toàn và trở thành một đỉnh. Điều này có thể thực hiện trong đồ thị phẳng (xem loại bỏ cạnh a, c, d trong Hình 2.6). Như vậy sẽ làm cho số cạnh và số đỉnh giảm đi 1 đơn vị. Số miền không đổi. Do đó, giá trị của biểu thức V − E + F không thay đổi. Giả sử cạnh là một khuyên. Ta loại bỏ các cạnh b, e. Do đó, số cạnh và số miền giảm đi 1 đơn vị. Số đỉnh không thay đổi. Vì vậy, giá trị của biểu thức V − E + F không thay đổi. Tiếp tục quá trình loại bỏ cạnh cho đến khi còn lại một đỉnh duy nhất, không có cạnh và có một miền (miền ngoài). Do đó V − E + F = 2. Bởi vì V − E + F không đổi trong suốt quá trình nên V − E + F = 2 đúng với đồ thị ban đầu. Chứng minh 2.1.3 (xem [5]). Gọi G là một đơn đồ thị phẳng liên thông với E cạnh, V đỉnh và F miền. Giả sử T ⊆ E là tập hợp các cạnh của cây bao trùm trong G, tức là một đồ thị con nhỏ nhất liên thông với tất cả các đỉnh của G. Đồ thị này không chứa chu trình bởi vì nó là nhỏ nhất. Ta xác định đồ thị đối ngẫu 0 G của G như sau: - Đặt một đỉnh vào mỗi miền của G. - Thêm một cạnh cho mỗi cạnh trong G tách hai miền liền kề và nối 2 0 0 đỉnh của G bằng cung e cắt cạnh chung e của hai miền đó. Sau đó ta vẽ một số cạnh liên thông trong đồ thị đối ngẫu. 0 0 Xét tập hợp T ⊆ E của các cạnh trong đồ thị đối ngẫu tương ứng với 0 các cạnh trong E\T . Các cạnh trong T liên thông tất cả các miền. Như 0 0 vậy T là một cây bao trùm của G . Đối với mọi cây, số đỉnh hơn số cạnh 1 đơn vị nên ta có: