Tag: đồ thị

Ramsey numbers


Các bạn đọc lại các bài sau để theo dõi cho dễ:

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

[3] https://nttuan.org/2023/09/01/graph02/

—

Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.

Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau. 

Lời giải. Gọi A là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, A sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là B, C, D, mà A cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng A quen cả ba người B, C, và D. Nếu trong B, C, và D có hai người quen nhau, chẳng hạn là B và C thì ba người A, B, và C đôi một quen nhau. Nếu không, B, C, và D đôi một không quen nhau. \Box

Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.

Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ K_6 trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của K_6 bởi hai màu, luôn có K_3 mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay K_6 bởi K_n với n<6. Kết quả sẽ thay đổi thế nào nếu thay K_3 bởi K_{\alpha}? Ta xét bài toán tổng quát sau:

Bài toán. Cho một số nguyên dương \alpha. Tồn tại hay không số nguyên dương n có tính chất: Với mỗi cách tô màu các cạnh của K_n bởi hai màu, luôn có K_{\alpha} mà các cạnh mang cùng một màu. Số nguyên dương n nhỏ nhất có tính chất này bằng bao nhiêu?

Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được n như một hàm của \alpha trong tình huống tổng quát mà chỉ có thể ước lượng nó.

Định lý 1 (Ramsey). Cho s và t là hai số nguyên lớn hơn 1. Khi đó tồn tại số nguyên dương n có tính chất: Với mỗi cách tô màu các cạnh của K_n bởi hai màu xanh và đỏ, K_n có đồ thị con K_s với các cạnh xanh hoặc có đồ thị con K_t với các cạnh đỏ. Nếu ký hiệu R(s,t) là số nguyên dương n nhỏ nhất có tính chất này thì

R(s,t)\leq R(s,t-1)+R(s-1,t)

mỗi khi s và t lớn hơn 2.

Các số R(s,t) được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết R(3,3)=6. Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số R(k,k), chúng được gọi là các số Ramsey đối xứng.

Chứng minh. Ta chứng minh bằng quy nạp theo s và t. Lập luận đơn giản ta thu được R(k,2), R(2,k) đều tồn tại và bằng k với mọi k>1.

Bây giờ giả sử R(s,t-1) và R(s-1,t) đều tồn tại, ở đây s và t là các số nguyên lớn hơn 2. Đặt \alpha=R(s,t-1)+R(s-1,t). Xét một cách tô màu các cạnh của K_{\alpha} bởi một trong hai màu xanh và đỏ. Gọi v là một đỉnh của K_{\alpha}. Mỗi một trong \alpha-1 đỉnh còn lại của K_{\alpha} được nối với v bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có R(s-1,t) đỉnh được nối với v bởi cạnh xanh, hoặc có R(s,t-1) đỉnh được nối với v bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem R(s-1,t) đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có K_{s-1} với các cạnh xanh hoặc K_t với các cạnh đỏ. Nếu có K_t với các cạnh đỏ thì ta có điều phải chứng minh, nếu có K_{s-1} với các cạnh xanh thì thêm v vào ta có đồ thị con K_s của K_{\alpha} với các cạnh xanh, và ta cũng có điều cần chứng minh. \Box

Định lý 2. Với mỗi số nguyên k>3, ta có R(k,k)>2^{k/2}.

Chứng minh (của Paul Erdos). Xét một số nguyên n thỏa mãn k\leq n\leq 2^{k/2}. Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của K_n bởi hai màu xanh và đỏ, sao cho trong K_n không có K_k với các cạnh cùng màu.

Tô màu mỗi cạnh của K_n bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu \Omega là tập tất cả các cách tô màu, và với mỗi biến cố A, xác suất xảy ra A bằng \mid A\mid /\mid\Omega\mid.

Gọi X là biến cố: trong K_n không có K_k với các cạnh cùng màu. Ta cần chứng \mathbb{P}(X)>0. Với mỗi đồ thị con đầy đủ trên k đỉnh của K_n, gọi Y_{\alpha} là biến cố: \alpha có các cạnh cùng màu. Khi đó

\displaystyle\mathbb{P}(Y_{\alpha})=\frac{\mid Y_{\alpha}\mid }{\mid \Omega\mid}=\frac{2\cdot 2^{C_n^2-C_k^2}}{2^{C_n^2}}=2^{1-C_k^2},

do đó

\mathbb{P}(X)=1-\mathbb{P}(\overline{X}) =1-\mathbb{P}\left(\bigcup_{\alpha}Y_{\alpha}\right)\geq 1-\sum_{\alpha}\mathbb{P}(Y_{\alpha})=1-C_n^k2^{1-C_k^2}.

Mà ta lại có

\displaystyle C_n^k2^{1-C_k^2}<\frac{n^k}{k!}\cdot 2^{1-C_k^2}\leq \frac{2^{k^2/2}}{k!}\cdot 2^{1-C_k^2}=\frac{2^{1+\frac{k}{2}}}{k!}< 1,

suy ra \mathbb{P}(X)>0. \Box

Graph theory: Basic definitions


Đây là bài thứ hai của tôi về lý thuyết đồ thị. Các bạn có thể xem bài trước ở

[1] https://nttuan.org/2023/08/13/graph01/

Với mỗi tập hợp X, ký hiệu [X]^2 là tập gồm tất cả các tập con có 2 phần tử của X.

Định nghĩa 1. Một đồ thị là một cặp G=(V,E) các tập hợp sao cho E\subset [V]^2.

Như vậy, các phần tử của E là các tập con có 2 phần tử của V. Các phần tử của V được gọi là các đỉnh của đồ thị G, các phần tử của E được gọi là các cạnh của G. Đồ thị có tập các đỉnh V được gọi là đồ thị trên V. Cách thông thường để vẽ một đồ thị là mỗi đỉnh biểu thị bởi một dấu chấm và nối hai trong các dấu chấm này bởi một đường cong nếu hai đỉnh tương ứng tạo thành một cạnh.

Trong hình trên ta có một đồ thị trên V=\{1,2,\ldots,6\} với tập cạnh E=\{\{1;2\},\{2;3\},\{6;5\},\{2;4\}\}. Khi vẽ một đồ thị ta không quan tâm các đỉnh hay cạnh được vẽ thế nào, điều quan trọng duy nhất ở đây là hai đỉnh nào được nối với nhau. Tập các đỉnh của một đồ thị G được ký hiệu bởi V(G), trong khi tập cạnh của nó được ký hiệu bởi E(G). Ta thường không phân biệt đồ thị và tập cạnh hoặc tập đỉnh của nó. Chẳng hạn, ta có thể nói đỉnh v thuộc G (thay vì v\in V(G)), một cạnh e của G,…

Số đỉnh của G được gọi là cấp của nó, ký hiệu bởi \mid G\mid. Một đồ thị G được gọi là hữu hạn nếu V(G) và E(G) là hai tập hữu hạn, vô hạn nếu V(G) hoặc E(G) là một tập vô hạn. Trong bài giảng này ta chỉ xét các đồ thị hữu hạn. Khi \mid G\mid =0 ta gọi G là đồ thị rỗng, ký hiệu \emptyset. Nếu cấp của G bằng n thì ta cũng nói G là đồ thị trên n đỉnh.

Định nghĩa 2. Cho một đồ thị G. Đỉnh v của G được gọi là đầu mút của một cạnh e của G nếu v\in e. Nếu hai đầu mút của một cạnh e là x và y thì ta nói e nối x và y, hoặc e kề với hai đỉnh x và y.

Một cạnh \{x;y\} thường được viết là xy hoặc yx.

Định nghĩa 3. Cho một đồ thị G. Hai đỉnh x và y của G được gọi là kề nhau nếu \{x;y\} là một cạnh của G. Trong trường hợp đó ta nói x và y là láng giềng của nhau.

Với mỗi đỉnh x, tập gồm tất cả các đỉnh kề với x được ký hiệu là N(x) hoặc N_G(x). Hai cạnh phân biệt e và f của G được gọi là kề nhau nếu chúng có chung một đầu mút. Nếu tất cả các đỉnh của G là đôi một kề nhau ta nói G là một đồ thị đầy đủ. Một đồ thị đầy đủ trên n đỉnh được ký hiệu bởi K_n. K_3 được gọi là tam giác. Một cặp các đỉnh hay cạnh được gọi là độc lập nếu chúng không kề nhau.

Định nghĩa 4. Cho hai đồ thị G=(V,E) và G^{\prime}=(V^{\prime},E^{\prime}). Một ánh xạ \varphi: V\to V^{\prime} được gọi đồng cấu từ G đến G^{\prime} nếu nó bảo toàn quan hệ kề giữa các đỉnh, nghĩa là \varphi (x) và \varphi (y) kề nhau mỗi khi x và y kề nhau. Nếu đồng cấu \varphi từ G đến G^{\prime} là một song ánh và \varphi^{-1} cũng là một đồng cấu, thì ta nói \varphi là một đẳng cấu hoặc G và G^{\prime} là đẳng cấu.

Ta không phân biệt các đồ thị đẳng cấu, vì thế ta thường viết G=G^{\prime} để chỉ G và G^{\prime} đẳng cấu. Trong một số trường hợp ta cũng nói G^{\prime} là một bản sao của G.

Continue reading “Graph theory: Basic definitions” →

Seven bridges of Konigsberg


Tôi sẽ dịch một đoạn trong bài Leonard Euler’s Solution to the Konigsberg Bridge Problem của Teo Paoletti. Khi tình cờ gặp bài viết này tôi đã quyết định sử dụng nó làm bài mở đầu trong bài giảng về lý thuyết đồ thị của tôi.

Câu chuyện của chúng ta bắt đầu vào thế kỷ 18, tại thị trấn cổ kính Konigsberg, Phổ, bên bờ sông Pregel. Năm 1254, các hiệp sĩ Teutonic thành lập thành phố Konigsberg dưới sự lãnh đạo của Vua Bohemian Ottoker II sau cuộc thập tự chinh thứ hai chống lại quân Phổ. Vào thời Trung cổ, Konigsberg đã trở thành một thành phố và trung tâm thương mại rất quan trọng với vị trí chiến lược bên sông. Các tác phẩm nghệ thuật từ thế kỷ 18 cho thấy Konigsberg là một thành phố thịnh vượng, nơi các đội tàu cập bến Pregel, và hoạt động buôn bán của họ mang lại cuộc sống thoải mái cho cả thương nhân địa phương và gia đình họ. Nền kinh tế phát triển cho phép người dân thành phố xây dựng bảy cây cầu bắc qua sông, hầu hết trong số đó nối với đảo Kneiphof, vị trí của chúng có thể được thấy trong hình dưới đây.

Khi dòng sông chảy quanh Kneiphof và một hòn đảo khác, nó chia thành phố thành bốn vùng độc lập. Theo truyền thuyết, người dân Konigsberg thường dành những buổi chiều Chủ nhật để đi dạo quanh thành phố xinh đẹp của họ. Trong khi đi bộ, người dân thành phố quyết định tạo ra một trò chơi cho chính họ. Mục tiêu là nghĩ ra cách để có thể đi bộ quanh thành phố mà chỉ băng qua mỗi cây cầu đúng một lần. Mặc dù không ai ở Konigsberg có thể phát hiện ra một tuyến đường như vậy, nhưng họ vẫn không thể chứng minh được rằng điều đó là không thể. May mắn cho họ, Konigsberg không quá xa St. Petersburg, quê hương của nhà toán học nổi tiếng Leonard Euler.

Tại sao Euler lại quan tâm đến một vấn đề không liên quan đến lĩnh vực toán học như vậy? Tại sao một nhà toán học vĩ đại như vậy lại dành nhiều thời gian cho một bài toán tầm thường như bài toán cây cầu Konigsberg? Euler rõ ràng là một người bận rộn, đã xuất bản hơn 500 cuốn sách và bài báo trong suốt cuộc đời của mình. Riêng năm 1775, trung bình mỗi tuần ông viết một bài báo toán học, và trong suốt cuộc đời mình, ông viết về nhiều chủ đề khác nhau ngoài toán học bao gồm cơ học, quang học, thiên văn học, hàng hải và thủy động lực học. Không có gì đáng ngạc nhiên khi Euler cảm thấy vấn đề này thật tầm thường, ông viết trong một bức thư năm 1736 gửi cho Carl Leonhard Gottlieb Ehler, thị trưởng của Danzig, người đã nhờ ông đưa ra lời giải cho bài toán:

“…Vì vậy, thưa ngài, ngài thấy đấy, bài toán này ít liên quan đến toán học như thế nào, và tôi không hiểu tại sao ngài lại mong đợi một nhà toán học tìm ra nó chứ không phải bất kỳ ai khác, vì lời giải chỉ dựa trên lý trí và khám phá ra nó. Không phụ thuộc vào bất kỳ nguyên tắc toán học nào. Vì điều này, tôi không biết tại sao ngay cả những câu hỏi ít liên quan đến toán học cũng được các nhà toán học giải nhanh hơn những người khác.”

Mặc dù Euler thấy vấn đề tầm thường nhưng ông vẫn bị hấp dẫn bởi nó. Trong một bức thư viết cùng năm cho Giovanni Marinoni, một nhà toán học và kỹ sư người Ý, Euler nói:

“Câu hỏi này thật tầm thường, nhưng đối với tôi, dường như nó đáng được chú ý bởi cả hình học, đại số, thậm chí cả nghệ thuật đếm cũng không đủ để giải quyết nó.”

Euler tin rằng vấn đề này có liên quan đến một chủ đề mà Gottfried Wilhelm Leibniz đã từng thảo luận và mong muốn được làm việc cùng, chủ đề mà Leibniz gọi là geometria situs, hay hình học vị trí. Cái gọi là hình học vị trí này là cái ngày nay ta gọi là lý thuyết đồ thị.

Continue reading “Seven bridges of Konigsberg” →