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. 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. 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.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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. 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.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. 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.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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ẻ. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Xét một ngũ giác thông thường trên hình 1. 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. 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ị. Bẩy cây cầu ở thành phố Königsberg năm 1736 (theo [1]).
Thành phố Königsberg 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.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Đế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ị.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).
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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.
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).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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 .