Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị và ứng dụng để giải toán sơ cấp

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

Thêm vào BST

Báo xấu

67
lượt xem 6
download

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

Đề tài đưa ra một số bài toán dẫn đến khái niệm đồ thị. Bằng những ví dụ gần gũi với thực tế. Làm rõ khái niệm đồ thị bằng những ví dụ gần gũi với thực tế cuộc sống. Tổng kết một số khái niệm hay dùng trong lý thuyết đồ thị. Ứng dụng một số kết quả của đồ thị vào giải quyết sáu dạng toán hay gặp trong chương trình bồi dưỡng toán trung học phổ thông.

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ĩ Khoa học: Lý thuyết đồ thị và ứng dụng để giải toán sơ cấp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN NGỌC HẢI LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, NĂM 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN NGỌC HẢI LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 40 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. TS. ĐẶNG HUY RUẬN HÀ NỘI, NĂM 2014
Mục lục Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 Các khái niệm và định lý cơ bản 7 1.1 Các ví dụ về đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Biểu diễn đồ thị bằng hình học . . . . . . . . . . . . . . . . . . 12 1.4 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . . . . . 13 1.5 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Đồ thị và một số bài toán phổ thông 16 2.1 Bài toán liên quan đến bậc của đồ thị . . . . . . . . . . . . . . . 16 2.1.1 Bậc của đỉnh . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Nửa bậc . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 17 2.1.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Bài toán liên quan đến chu trình . . . . . . . . . . . . . . . . . 28 2.2.1 Xích, Chu trình . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Đường, Vòng . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 29 2.2.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Bài toán liên quan đến tính liên thông . . . . . . . . . . . . . . 38 2.3.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.2 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 39 2.3.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4 Đồ thị Euler - Đồ thị Hamilton . . . . . . . . . . . . . . . . . . 50 3
2.4.1 Đường đi Euler và đồ thị Euler . . . . . . . . . . . . . . 50 2.4.2 Đường đi Hamilton và đồ thị Hamilton . . . . . . . . . . 55 2.4.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.5 Bài toán liên quan đến đồ thị tô màu . . . . . . . . . . . . . . . 70 2.5.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.5.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.5.3 Thuật toán tìm sắc số . . . . . . . . . . . . . . . . . . . 74 2.5.4 Lớp đồ thị có chu trình tam giác cùng màu . . . . . . . . 75 2.5.5 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.6 Bài toán về cây . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.6.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.6.2 Đặc điểm của cây và bụi . . . . . . . . . . . . . . . . . . 85 2.6.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Lời kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4
Mở đầu Lý thuyết đồ thị (lý thuyết graph) là một ngành toán học hiện đại, một lĩnh vực khá trẻ của toán học mặc dù những vấn đề của lý thuyết đồ thị đã có từ vài trăm năm trước đây. Những ý tưởng cơ bản về lý thuyết đồ thị được đưa ra vào năm 1736 bởi nhà toán học Thụy Sĩ Leonhard Euler với bài toán nổi tiếng về 7 cây cầu ở thành phố K¨onigsberg. Những công trình nghiên cứu về lý thuyết đồ thị gắn liền với những tên tuổi các nhà toán học lớn như Euler, Hamilton,... Cuốn sách giáo khoa đầu tiên về lý thuyết đồ thị được K¨onig viết và xuất bản tại Leipzig năm 1936. Mãi 22 năm sau, cuốn sách giáo khoa thứ hai về đồ thị mới được ra đời bởi nhà toán học Berge viết và in tại Paris. Vả lại, do đặc trưng rất “gần gũi” với thực tế của mình, lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng trong việc áp dụng để giải các bài toán trong cuộc sống. Nó có nhiều ứng dụng quan trọng trong nhiều ngành khoa học, kĩ thuật hiện đại: vật lý, hóa học, sinh học, tin học,... Ngày nay, lý thuyết đồ thị đã trở thành một công cụ không thể thiếu được khi phải giải quyết những vấn đề có tính chất phải xem xét cả tổng thể. Được sự hướng dẫn tận tâm, sự chỉ bảo tận tình và những bài giảng tâm huyết của NGND.GS.TS Đặng Huy Ruận. Tác giả xin đóng góp một phần nhỏ tìm hiểu của bản thân về lý thuyết đồ thị qua luận văn: “Lý thuyết đồ thị và ứng dụng để giải toán sơ cấp”. Luận văn gồm phần mở đầu, kết luận, tài liệu tham khảo và 2 chương. Chương 1. Các khái niệm và định lý cơ bản. Chương 1 trình bày một số bài toán dẫn đến khái niệm đồ thị, một số khái niệm và định lý hay dùng trong lý thuyết đồ thị. Các lý thuyết này đã được GS.TS Đặng Huy Ruận tích lũy trong cuốn sách “Lý thuyết đồ thị và ứng dụng” bao gồm: - Khái niệm về lý thuyết đồ thị. - Các cách biểu diễn đồ thị. 5
- Một số dạng đồ thị đặc biệt. Chương 2. Đồ thị và một số bài toán phổ thông. Chương 2 trình bày một số ứng dụng của lý thuyết đồ thị để giải quyết 6 dạng toán: 1. Các bài toán liên quan đến bậc của đồ thị. 2. Các bài toán liên quan đến chu trình. 3. Các bài toán liên quan đến đồ thị liên thông. 4. Các bài toán ứng dụng đồ thị Euler và đồ thị Hamilton. 5. Các bài toán ứng dụng đồ thị tô màu. 6. Các bài toán ứng dụng cây. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến NGND.GS.TS Đặng Huy Ruận, người Thầy đã tận tình hướng dẫn, giúp đỡ tác giả trong suốt quá trình học tập và hoàn thành luận văn. Kính chúc thầy mạnh khoẻ, hạnh phúc để thế hệ học trò chúng con được học hỏi nhiều hơn nữa từ tấm gương của thầy. Tác giả xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo Sau đại học, Khoa Toán - Cơ - Tin học, các thầy giáo, cô giáo và các bạn của seminar “Phương pháp Toán sơ cấp” Trường Đại học Khoa học Tự nhiên - ĐHQGHN đã giúp đỡ và góp ý cho luận văn được hoàn chỉnh. Do trình độ còn hạn chế, chắc chắn luận văn không tránh khỏi thiếu sót. Tác giả mong nhận được nhiều đóng góp từ các bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn. Học viên Nguyễn Ngọc Hải 6
Chương 1 Các khái niệm và định lý cơ bản 1.1 Các ví dụ về đồ thị Ví dụ 1.1.1. Một đoàn khách du lịch đến Hà Nội và muốn đi thăm các danh lam thắng cảnh của Hà Nội. Sơ đồ các danh lam thắng cảnh cũng như hệ thống giao thông ở Hà Nội cho phép đi từ địa điểm này sang địa điểm khác được cho theo sơ đồ ở hình 1.1. Trong đó các điểm biểu thị các nơi khách cần đến, các đoạn thẳng biểu thị các con đường có thể đi được. Bạn hãy giao cho Công ty du lịch Hà Nội lập hành trình sao cho khách có thể đi tới thăm mọi địa điểm, mỗi địa điểm đi qua không quá một lần và chỉ đi theo các đường có trong sơ đồ. Thêm vào đó con đường bắt đầu từ A và kết thúc ở K. Hình 1.1 Theo sơ đồ thì đến C và E, mỗi điểm chỉ có hai con đường. Vì thế hành trình thoả mãn yêu cầu bài toán phải đi đến bằng một đường và ra bằng con đường còn lại. Do vậy một đoạn hành trình khi đến C phải là I → C → B hoặc B → C → I. Tương tự hành trình qua E phải là B → E → F hoặc 7
F → E → B. Nhưng trong hành trình, mỗi địa điểm chỉ đi qua không quá một lần nên một đoạn của hành trình phải là I → C → B → E → F hoặc ngược lại F → E → B → C → I (hình 1.2). Do con đường bắt đầu từ A nên một đoạn đầu của hành trình là A → I → C → B → E → F. Hình 1.2 Đoạn còn lại chỉ có thể là F → M → H → D → K. Vậy hành trình phải tìm là: A → I → C → B → E → F → M → H → D → K. Từ lời giải suy ra rằng hành trình thoả mãn bài ra là duy nhất. Ví dụ 1.1.2. Một mảnh giấy được xé làm 3 phần nhỏ. Đến lượt thứ hai ta lại xé một vài mảnh giấy nhỏ, mỗi lần một mảnh giấy nhỏ được xé làm 3 phần nhỏ hơn. Tiếp tục lặp lại quá trình đó. Chứng minh rằng, sau k (với k là số nguyên dương) lần xé ta thu được số mảnh giấy là một số lẻ. Ta biểu thị mỗi mảnh giấy như một dấu chấm chấm tròn. Sự kiện mỗi mảnh giấy sau mỗi lần xé được thành ba mảnh, mô tả trên hình 1.3, trong đó dấu chấm tròn đen biểu thị mảnh giấy ban đầu không còn nữa và dấu chấm tròn trắng biểu thị các mảnh giấy nhận được. Hình 1.3 giúp ta thấy rằng sau mỗi lần xé được thêm hai mảnh giấy (3 mảnh giấy mới thay cho mảnh giấy cũ) và một ví dụ cho 4 lần xé. • Lượt thứ nhất xé mảnh ban đầu: được 3 mảnh giấy nhỏ. 8
Hình 1.3 • Lượt thứ hai xé 2 mảnh: được 7 mảnh giấy nhỏ. • Lượt thứ ba xé 4 mảnh: được 15 mảnh giấy nhỏ. • Lượt thứ tư xé 1 mảnh: được 17 mảnh giấy nhỏ. Có được 17 dấu chấm tròn trắng, tương ứng 17 mảnh giấy được nhận. Khi một mảnh giấy bị xé thành 3 mảnh giấy nhỏ hơn, ta thấy rằng mỗi mảnh giấy mất đi ta được thêm 2 mảnh giấy mới. Cứ như vậy, sau k lần xé, mất đi l mảnh giấy, ta được số mảnh giấy sẽ là: 2l + 1. Vậy số mảnh giấy là một số lẻ. Ví dụ 1.1.3. Có thể có một nhóm 5 người mà mỗi người quen đúng với hai người khác trong nhóm hay không ? Hình 1.4 Biểu thị mỗi một người là một điểm còn nếu hai người quen nhau thì ta nối hai điểm tương ứng lại, nếu không quen nhau thì giữa hai điểm không được nối. 9
Xét một ngũ giác thông thường trên hình 1.4. Rõ ràng mỗi đỉnh ngũ giác được nối với đúng hai đỉnh khác. Vì thế có thể có 5 người mà mỗi người quen với đúng hai người khác trong số 4 người còn lại. Trong bài toán này có thể thay số 5 bởi một số tự nhiên n > 2 tuỳ ý. Lúc đó tương ứng thay ngũ giác bởi đa giác n cạnh. Tuy nhiên ta cũng có thể thử suy nghĩ xem có hay không một nhóm 5 người mà mỗi người quen đúng với 3 người còn lại trong nhóm ? Ví dụ 1.1.4. Hãy phân nhóm học tập cho lớp học sao cho những người trong cùng một nhóm là bạn thân với nhau. Chọn đỉnh của sơ đồ cần lập là những em học sinh trong lớp. Trong sơ đồ biểu diễn, ta nối những cặp hai em học sinh thân nhau bằng một đoạn thẳng (hoặc một đoạn cong). Bằng cách như vậy, ta sẽ có một sơ đồ gồm các đỉnh (các em học sinh) và các cạnh (các đường nối hai em khi và chỉ khi hai em này thân nhau). Những mô hình quy về các tập đỉnh và các cạnh nối đỉnh là những đồ thị. Ví dụ 1.1.5. Bẩy cây cầu ở thành phố K¨ onigsberg năm 1736 (theo [1]). Thành phố K¨onigsberg của nước Đức (bây giờ là thành phố Kaliningrad của liên bang Nga) có dòng sông Pregel chảy qua, giữa sông có cù lao Kneiphof và 7 cây cầu như Hình 1.5a Hình 1.5 Từ khi xuất hiện 7 cây cầu, người dân ở đây đã đặt ra vấn đề: “Liệu có cách nào đi qua được cả bẩy cây cầu và qua mỗi cây cầu đúng một lần được không ?”. 10
Đến năm 1736 nhà toán học Euler đã chứng minh bài toán trên không giải được. Bằng cách dùng các đỉnh A, B, C, D để biểu thị các miền đất ở hai bên cầu; các cây cầu được biểu thị bằng các cạnh nối giữa các đỉnh tương ứng với các miền đất hai bên cầu. Euler đã chứng minh được rằng không thể vẽ tất cả các cạnh của đồ thị Hình 1.5b bằng một nét bút. Từ đó, những đường một nét trong lý thuyết đồ thị được mang tên ông. Trong 5 ví dụ nói trên và nhiều bài toán khác, người ta thường dùng các sơ đồ (hay hình vẽ) gồm các điểm và các đoạn nối các điểm này để giải toán, hoặc làm sáng tỏ các lập luận, hoặc minh họa cho các tình huống. Đó là những minh hoạ của đồ thị. 1.2 Định nghĩa đồ thị Tập hợp X 6= ∅ các đối tượng và bộ E các cặp sắp thứ tự và không sắp thứ tự các phần tử của X được gọi là một đồ thị, đồng thời được ký hiệu bằng G(X, E) (hoặc bằng G = (X, E)) hoặc G(X). Các phần tử của X được gọi là các đỉnh. Cặp đỉnh không sắp thứ tự được gọi là cạnh, cặp đỉnh sắp thứ tự được gọi là cạnh có hướng hay cung. Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng, đồ thị chỉ chứa các cung được gọi là đồ thị có hướng. Nếu đồ thị chứa cả cạnh lẫn cung được gọi là đồ thị hỗn hợp hay đồ thị hỗn tạp. Một cặp đỉnh có thể được nối với nhau bằng hai hoặc nhiều hơn hai cạnh (hai hoặc nhiều hơn hai cung). Các cạnh (cung) này được gọi là các cạnh (cung) bội. Một cung (hoặc một cạnh) có thể bắt đầu và kết thúc tại cùng một đỉnh. Cung (cạnh) này được gọi là khuyên. Cặp đỉnh x, y được nối với nhau bằng cạnh (hoặc cung) a thì x, y được gọi là các đỉnh hay hai đầu của cạnh (cung) a và a được gọi là cạnh (cung) thuộc đỉnh x, đỉnh y. 11
Nếu cung b xuất phát từ đỉnh u và đi vào đỉnh v, thì u được gọi là đỉnh đầu, còn v được gọi là đỉnh cuối của cung b. Cặp đỉnh x, y được gọi là hai đỉnh kề nhau, nếu x 6= y và x, y là hai đầu của cùng một cạnh hay một cung. Đối với mọi đỉnh x, ta dùng D(x) để chỉ tập đỉnh, mà mỗi đỉnh này được nối với x bằng ít nhất một cạnh; D+ (x) để chỉ tập đỉnh, mà mỗi đỉnh này từ x có cung đi tới; D− (x) để chỉ tập đỉnh, mà mỗi đỉnh này có cung đi tới x. Hai cạnh (cung) a, b được gọi là kề nhau nếu: 1. Chúng khác nhau. 2. Chúng có đỉnh chung (nếu a, b là cung, thì không phụ thuộc vào đỉnh chung đó là đỉnh đầu hay đỉnh cuối của cung a, đỉnh đầu hay đỉnh cuối của cung b). 1.3 Biểu diễn đồ thị bằng hình học Giả sử có đồ thị G(X, E). Biểu diễn đỉnh: Lấy các điểm trên mặt phẳng hoặc trong không gian tương ứng với các phần tử thuộc tập X và dùng ngay kí hiệu các phần tử này để ghi tên các điểm tương ứng. Biểu diễn cạnh: Nếu cạnh a với hai đỉnh đầu là x và y thì nó được biểu diễn là bằng đoạn thẳng hay một đoạn cong nối giữa hai điểm x, y và không đi qua các điểm tương ứng trung gian khác. Biểu diễn cung: Nếu cung a có đỉnh đầu là x, đỉnh cuối là y, thì nó được biểu diễn bằng một đoạn thẳng hoặc một đoạn cong được xác định hướng đi từ x sang y và không đi qua các điểm tương ứng trung gian khác. Hình nhận được gọi là dạng biểu diễn hình học của đồ thị G(X, E). Đôi khi người ta cũng gọi dạng biểu diễn hình học là một đồ thị. 12
1.4 Một số dạng đồ thị đặc biệt Trong trường hợp không cần phân biệt giữa cạnh và cung ta quy ước dùng cạnh thay cho cả cung. Đồ thị G(X, E) không có khuyên và mỗi cặp đỉnh được nối với nhau bằng không quá một cạnh, được gọi là đồ thị đơn hay đơn đồ thị và thông thường được gọi là đồ thị. Đồ thị G(X, E) không có khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng từ hai cạnh trở lên được gọi là đa đồ thị. Đồ thị vô hướng (hoặc có hướng) G(X, E) được gọi là đồ thị - đầy đủ, nếu mỗi cặp đỉnh được nối với nhau bằng đúng một cạnh (hoặc một cung với chiều tùy ý). Đồ thị vô hướng (hoặc có hướng) G(X, E) được gọi là đồ thị k - đầy đủ, nếu mỗi cặp đỉnh được nối với nhau bằng đúng k cạnh (hoặc k cung với chiều tùy ý). Đồ thị (đa đồ thị) G(X, E) được gọi là đồ thị (đa đồ thị) hai mảng, nếu tập đỉnh X của nó được phân thành hai tập con rời nhau X1 , X2 (với X1 ∪ X2 = X và X1 ∩ X2 = ∅) và mỗi cạnh đều có một đầu thuộc X1 , còn đầu kia thuộc X2 . Khi đó G(X, E) còn được ký hiệu bằng G(X1 , X2 , E). Đồ thị (đa đồ thị) G(X, E) được gọi là đồ thị (đa đồ thị) phẳng, nếu nó có ít nhất một dạng biểu diễn hình học trải trên một mặt phẳng nào đó, mà các cạnh của đồ thị chỉ cắt nhau ở đỉnh. Đồ thị (đa đồ thị) G(X, E) được gọi là đồ thị (đa đồ thị) hữu hạn, nếu số đỉnh của nó hữu hạn, nghĩa là tập X có lực lượng hữu hạn. Đồ thị (đa đồ thị) với tập đỉnh vô hạn, được gọi là đồ thị (đa đồ thị) vô hạn. Đồ thị (đa đồ thị) với số cạnh thuộc mỗi đỉnh đều hữu hạn được gọi là đồ thị (đa đồ thị) hữu hạn địa phương. Trong các phần tiếp theo, nếu chúng tôi không chú ý gì thêm, thì các đồ thị, đa đồ thị được xét đều hữu hạn. 13
Cho Y ⊆ X, Y 6= ∅; H ⊆ E, F = E ∩ (Y × Y ); V = (X × X)/E với X × X = {(x, y) : x, y ∈ X}; Y × Y = {(x, y) : x, y ∈ Y ⊆ X}. Đồ thị G1 (Y, F ) được gọi là đồ thị con, còn đồ thị G2 (X, H) được gọi là đồ thị bộ phận của đồ thị G(X, E). Đồ thị G0 (X, V ) được gọi là đồ thị bù của đồ thị G(X, E). Đồ thị có hướng G(X, E) được gọi là đồ thị đối xứng, nếu ∀ x, y ∈ X : (x, y) ∈ E ⇒ (y, x) ∈ E. Trong đồ thị đối xứng tùy ý hai đỉnh kề nhau x, y luôn được nối bằng hai cung ngược chiều nhau. Để đơn giản, trong trường hợp này ta quy ước thay hai cung nói trên bằng một cạnh nối giữa x và y. Đồ thị có hướng G(X, E) được gọi là đồ thị phản đối xứng, nếu ∀ x, y ∈ X : (x, y) ∈ E ⇒ (y, x) ∈ / E. 1.5 Phương pháp đồ thị Về thực chất, phương pháp đồ thị là cách giải toán thông qua công cụ trung gian là đồ thị. Phương pháp đồ thị bao gồm 3 bước: Bước 1 : Xây dựng đồ thị (G) mô tả toàn bộ quan hệ được cho trong bài toán T • Đỉnh: Lấy các điểm trên mặt phẳng hoặc trong không gian tương ứng với các đối tượng được cho trong bài toán. Dùng ngay tên các đối tượng để ghi trên các điểm tương ứng. • Cạnh: Hai đỉnh x, y tùy ý được nối bằng một cạnh (hay cung) khi và chỉ khi hai đối tượng x, y có một quan hệ tương ứng nào đó. Đồ thị G mô tả toàn bộ các quan hệ được cho trong bài toán T . Lúc này bài toán T đã được phát biểu dưới dạng tính chất của đồ thị. Bước 2 : Căn cứ vào đồ thị G, trên cơ sở các kết quả của lý thuyết đồ thị, mà ta suy ra đáp án của bài toán T bằng ngôn ngữ đồ thị. 14
Bước 3 : Căn cứ vào sự đặt tương ứng, đặc thù của cạnh và cung mà “dịch” đáp án từ ngôn ngữ đồ thị sang ngôn ngữ thông thường. 15
Chương 2 Đồ thị và một số bài toán phổ thông 2.1 Bài toán liên quan đến bậc của đồ thị 2.1.1 Bậc của đỉnh Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng hoặc không có hướng. Số cạnh và cung thuộc đỉnh x được gọi là bậc của đỉnh x và ký hiệu bằng m(x). Đỉnh có bậc bằng 0 được gọi là đỉnh biệt lập. Đỉnh có bậc bằng 1 được gọi là đỉnh treo. Cạnh (cung) có ít nhất một đầu là đỉnh treo được gọi là cạnh (cung) treo. 2.1.2 Nửa bậc Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng. Số cung đi vào đỉnh x được gọi là nửa bậc vào của đỉnh x và ký hiệu bằng m0 (x) hoặc bằng m− (x). Số cung đi ra khỏi đỉnh x được gọi là nửa bậc ra của đỉnh x và ký hiệu bằng m00 (x) hoặc bằng m+ (x). Ký hiệu tập cung đi vào đỉnh x bằng E − (x), tập cung đi ra khỏi đỉnh x bằng E + (x). 16
2.1.3 Một số tính chất Một số kết quả nhận được từ [5] như sau: Định lý 2.1.1. Trong một đồ thị hay đa đồ thị tùy ý, tổng số bậc của tất cả các đỉnh bao giờ cũng gấp đôi số cạnh. Định lý 2.1.2. Trong một đồ thị hay đa đồ thị tùy ý, số đỉnh bậc lẻ luôn luôn là một số chẵn. Chứng minh. Giả sử đồ thị (đa đồ thị) G(X, E) có n đỉnh, m cạnh X = {x1 , x2 , x3 , . . . , xk , xk+1 , . . . , xn−1 , xn }, các đỉnh x1 , x2 , . . . , xk bậc lẻ và xk+1 , . . . , xn−1 , xn bậc chẵn. Theo định lý 2.1.1 ta có đẳng thức: m(x1 ) + m(x2 ) + . . . + m(xk ) + m(xk+1 ) + . . . + m(xn−1 ) + m(xk ) = 2m. | {z } | {z } A B Vì B là tổng của các số chẵn nên B là một số chẵn. Do đó A = 2m − B là một số chẵn. Số A là tổng của k số lẻ nên k phải là số chẵn. Bởi vậy, số đỉnh bậc lẻ trong đồ thị hay đa đồ thị bất kỳ phải là một số chẵn. Định lý 2.1.3. Trong một đồ thị với n (n > 2) đỉnh có ít nhất 2 đỉnh cùng bậc. Chứng minh. Giả sử đồ thị G(X, E) có n đỉnh với n > 2. Ta xét 2 khả năng: 1) Nếu đồ thị có đỉnh bậc 0: Khi đó trong đồ thị không có một đỉnh nào kề với tất cả các đỉnh còn lại, nên mỗi đỉnh của đồ thị có bậc là một trong n − 1 số nguyên: 0, 1, ..., n − 2. 2) Nếu đồ thị có đỉnh bậc n − 1: 17
Khi đó đồ thị không có đỉnh bậc 0. Do đó, bậc của mỗi đỉnh thuộc đồ thị là một trong n − 1 số nguyên: 1, ..., n − 2, n − 1. Từ kết quả lý luận trên khẳng định được rằng, đồ thị G(X, E) với n đỉnh, nhưng chỉ có không quá n − 1 loại bậc. Bởi vậy, phải có ít nhất 2 đỉnh cùng bậc. Định lý 2.1.4. Nếu đồ thị với n (n > 2) đỉnh có đúng 2 đỉnh cùng bậc thì hai đỉnh này không thể đồng thời có bậc 0 hoặc n − 1. Chứng minh. Với n = 3, định lý hiển nhiên đúng. Ta xét với n > 4. Giả sử là hai đỉnh cùng bậc của đồ thị G(X, E) và đều có bậc 0 hoặc bậc n − 1. Loại x, y và tất cả các cạnh thuộc chúng khỏi đồ thị G, ta được đồ thị con G1 có n − 2 đỉnh. Theo định lý 2.1.3, trong G1 có hai đỉnh cùng bậc, giả sử là u, v. 1) Nếu x, y cùng bậc 0 thì u, v trong G không kề với x, y nên u, v đồng thời là hai đỉnh cùng bậc trong đồ thị G. Như vậy, đồ thị G phải có ít nhất 2 cặp đỉnh cùng bậc. 2) Nếu x, y cùng bậc n − 1. Khi đó mỗi đỉnh u, v đều kề đồng thời với x, y nên trong đồ thị G các đỉnh u, v cũng cùng bậc . Như vậy, đồ thị G phải có ít nhất 2 cặp đỉnh cùng bậc. Cả hai trường hợp đều dẫn tới mâu thuẫn với tính chất: đồ thị G có duy nhất một cặp đỉnh cùng bậc nên x, y không thể cùng bậc 0 hoặc bậc n − 1. Khẳng định được chứng minh. Định lý 2.1.5. Số đỉnh bậc n − 1 trong đồ thị G với n (n > 4) đỉnh, mà 4 đỉnh tùy ý có ít nhất một đỉnh kề với 3 đỉnh còn lại, không nhỏ hơn n − 3. Chứng minh. 1) Nếu G đầy đủ thì khẳng định là hiển nhiên. 18
2) Nếu G có cặp đỉnh duy nhất không kề nhau. Khi đó trong G có n − 2 đỉnh bậc n − 1. 3) Nếu G có 2 cặp đỉnh không kề nhau. Khi đó, 2 cặp đỉnh này phải có đỉnh chung. Thật vậy, giả sử A, B; I, D là hai cặp đỉnh không kề nhau. Nếu hai cặp đỉnh này không có đỉnh chung thì trong 4 đỉnh A, B, I, D không có đỉnh nào kề với 3 đỉnh còn lại, như vậy mâu thuẫn với giả thiết. Do đó, hai cặp A, B; I, D phải có hai đỉnh trùng nhau, giả sử là B ≡ I. Lấy đỉnh C tùy ý khác A, B, D. Trong bộ bốn đỉnh A, B, C, D đỉnh C kề với cả 3 đỉnh A, B, D Loại D ra khỏi bộ bốn đỉnh trên và thay vào đó là đỉnh E tùy ý khác với A, B, C, D. Trong bộ bốn đỉnh A, B, C, E hoặc C hoặc E phải kề với 3 đỉnh còn lại, nếu E kề với 3 đỉnh còn lại thì C kề với E. Do đó C kề với cả 3 đỉnh A, B, E. Do E là đỉnh tùy ý trong n − 4 đỉnh còn lại (khác A, B, C, D), nên C có bậc n − 1. C là đỉnh tùy ý trong n − 3 đỉnh khác A, B, D nên đồ thị có n − 3 đỉnh bậc n − 1. Khẳng định được chứng minh. Định lý 2.1.6. Với mọi số tự nhiên n (n > 2), luôn tồn tại đồ thị n đỉnh mà 3 đỉnh bất kì của đồ thị đều không cùng bậc. Chứng minh. 1) Với n = 3 đồ thị G3 gồm một đỉnh bậc 0 và hai đỉnh bậc 1. 2) Giả sử khẳng định đúng với đồ thị Gn có n đỉnh. Đồ thị Gn+1 được xây dựng như sau: a) Nếu Gn có đỉnh bậc n − 1. Khi đó Gn không có đỉnh bậc 0. Nếu ta ghép vào Gn đỉnh x bậc 0 và được Gn+1 gồm n + 1 đỉnh. Việc ghép thêm đỉnh x vẫn bảo toàn tính chất của Gn : ba đỉnh bất kỳ đều không cùng bậc và đồ thị Gn không có đỉnh bậc 0, nên trong Gn+1 ba đỉnh bất kỳ đều không cùng bậc. 19
b) Nếu Gn không có đỉnh bậc n − 1. Khi đó tất cả các đỉnh của Gn đều có bậc không vượt quá n − 2. Nếu ta ghép vào Gn đỉnh x (không thuộc Gn ) và nối x với từng đỉnh của Gn bằng một cạnh, được Gn+1 gồm n + 1 đỉnh. Đỉnh x có bậc bằng n, còn bậc của mỗi đỉnh thuộc Gn trong Gn+1 được tăng thêm 1 đơn vị, nhưng đều không vượt quá n − 1 và trong bậc mới ba đỉnh bất kỳ của Gn vẫn không cùng bậc. Khẳng định được chứng minh. Định lý 2.1.7. Đồ thị hai mảng G(Y, Z; E) với mọi đỉnh y ∈ Y đều có m(y) > 1, đồng thời có tính chất: bất kỳ hai cặp đỉnh y1 , y2 ∈ Y ; z1 , z2 ∈ Z nào cũng thỏa mãn điều kiện: Nếu y1 kề với z1 , y2 kề với z2 thì trong hai cặp đỉnh y1 , z2 ; y2 , z1 có ít nhất một cặp đỉnh kề nhau. Khi đó trong tập Z có ít nhất một đỉnh kề với tất cả các đỉnh thuộc Y . Chứng minh. Ký hiệu |Y | = m, |Z| = n. Xét ba khả năng có thể xảy ra: 1) m = 1: Do Y có phần tử duy nhất y, mà m(y), nên trong tập Z có ít nhất phần tử z kề với y. Bởi vậy m(z) = 1 = |Y |. 2) m > 1, n = 1, theo giả thiết, với mọi y ∈ Y đều có m(y) > 1, nên đỉnh z duy nhất của tập Z phải kề với tất cả cá đỉnh thuộc Y hay m(z) = |Y |. 3) m > 1, n > 1. Gọi z là đỉnh có bậc lớn nhất trong tập Z. a) Nếu m(z) = |Y |, khẳng định được chứng minh. b) Giả sử m(z) = k < m = |Y |. Ký hiệu y1 , y2 , . . . , yk là các đỉnh kề với z và yk+1 phải kề với đỉnh t ∈ Z và t 6= z. Xét hai cặp đỉnh (z, yi ), (t, yk+1 ) với i = 1, 2, . . . , k ⇒ t kề với y1 , y2 , . . . , yk . Ngoài ra t còn kề với yk+1 nên m(t) = k + 1 > k = m(z). Điều này mâu thuẫn với m(z) cực đại. Khẳng định được chứng minh. Định lý 2.1.8. Trong đồ thị G(X, E) với ít nhất kn + 1 đỉnh, mỗi đỉnh có bậc không nhỏ hơn (k − 1)n + 1, luôn tồn tại một đồ thị con đầy đủ gồm k + 1 đỉnh. 20