Cấu trúc liên kết đồ thị

5

V. Boltyansky

Cấu trúc liên kết đồ thị

Nhà toán học nổi tiếng người Pháp Andre Weil từng nói rằng “ác quỷ của đại số trừu tượng và thiên thần của cấu trúc liên kết” đang đấu tranh giành lấy tâm hồn của mỗi nhà toán học. Trong bài viết về đồ thị này, chúng ta sẽ chủ yếu lắng nghe tiếng nói của thiên thần cấu trúc liên kết, mặc dù ác quỷ dễ giúp đỡ cũng sẽ có tiếng nói của mình.

Đồ thị (hữu hạn) là tập hợp các điểm (đỉnh của đồ thị) được kết nối - trên mặt phẳng hoặc trong không gian - bởi một số hữu hạn các cung (cạnh của đồ thị) và các cung chỉ cắt nhau tại các đỉnh *) (Hình 1).

Trong hầu hết bài viết, điều quan trọng đối với chúng ta là đồ thị là một hình nhất định (tập hợp tất cả các điểm của các cung); các điểm được chọn của hình này là

*) Trong lý thuyết đồ thị nói chung, một định nghĩa hơi khác - “trừu tượng” - về đồ thị được chấp nhận (xem «Kvant», 1981, Số 3, trang 18).

các đỉnh - chúng ta thường bỏ qua chúng.

Những đồ thị nào giống nhau?

Thiên thần của cấu trúc liên kết coi các đồ thị hình học là giống hệt nhau - những đồ thị như vậy $G_1$ và $G_2$ trong đó có ánh xạ liên tục (không có điểm gián đoạn) và nghịch đảo (không có sclive) $h$: $G_1 \rightarrow G_2$ đặt $G_1$ trên toàn bộ tập hợp $G_2$ (ánh xạ như vậy được gọi là hình học*)).

*) Khi xác định tính hình học của một hình tùy ý, tính liên tục của ánh xạ nghịch đảo $h^{-1}$ cũng được yêu cầu (đối với đồ thị hữu hạn, nó được thực hiện tự động, điều mà thiên thần của cấu trúc liên kết đã bảo chúng ta để lại mà không cần chứng minh).

6

Từ định nghĩa này, ta suy ra rằng hai đồ thị hình học, đặc biệt, nếu, bằng cách uốn cong và kéo dài các cạnh như mong muốn, nhưng không cho phép ngắt quãng và các đồ thị slivian, thì một trong số chúng có thể được xếp chồng lên nhau. Hình 2, $a$ cho thấy cách chuyển một hình tròn thành hình số tám; tuy nhiên, điều này không có nghĩa là hình tròn và số tám là hình học (xét cho cùng, trong quá trình biến đổi này, hai điểm đã bị nén lại với nhau). Một hình tròn cũng có thể biến thành nửa hình tròn, nhưng để làm được điều này, nó cần phải được xé ra và chỉ sau đó mới làm thẳng lại. Vì không được phép có sự gián đoạn nên sự biến đổi như vậy sẽ không có tính chất hình học; Ngoài ra, semiperval không phải là một biểu đồ. Và đây là đường viền của một hình tam giác và đường viền của hình vuông, và cả hai đều là hình học của một hình tròn, như trong Hình 2, $6$.

Lưu ý rằng không phải lúc nào cũng có thể, như trong ví dụ này, nhận ra ánh xạ hình học $h$: $G_1 \rightarrow G_2$ bằng cách uốn cong, kéo dài và cuộn các đồ thị trong chính không gian. Do đó, một cặp vòng tròn lồng vào nhau (Hình 3) không được lồng vào nhau, mặc dù trong không gian không thể tách chúng ra mà không làm gãy chúng.

Như ví dụ về hình tam giác và hình vuông cho thấy, trong hình học, đỉnh không nhất thiết phải biến thành đỉnh. Chúng ta sẽ quay lại vấn đề này sau.

Ví dụ 1. Hãy tưởng tượng các chữ cái trong bảng chữ cái tiếng Nga ở dạng dòng. Các chữ cái G, L, M, P, S có tính chất hình học với nhau. Các chữ cái E, U, T, Ch, Sh, C, E cũng có tính hình học với nhau, nhưng không hình học với các chữ cái đã đề cập trước đó. Chữ O không phải là hình học

không có chữ cái nào khác trong bảng chữ cái tiếng Nga *).

Thật tôn trọng khi so sánh khái niệm hình học hóa và khái niệm khả năng xây dựng của các hình. Trong hình học, các chuyển vị được xem xét, tức là các ánh xạ bảo toàn khoảng cách giữa các điểm. Hai hình được chuyển đổi thành một hình khác (“kết hợp”) bằng cách dịch chuyển được gọi là tắc nghẽn và được coi là giống hệt nhau (theo quan điểm hình học). Các nhà tôpô xem xét các ánh xạ tổng quát hơn các chuyển vị, cụ thể là các ánh xạ hình học, có thể không bảo toàn khoảng cách mà chỉ bảo toàn tính liên tục của việc sắp xếp các điểm trong hình (không cho phép ngắt quãng và phân đoạn). Do đó, hai hình hình học được coi là giống hệt nhau (từ quan điểm tôpô).

Những bất biến đơn giản nhất

Các tính chất của hình được bảo toàn trong quá trình chuyển đổi từ hình sang hình hình học được gọi là tính chất tôpô của hình, hay bất biến tôpô (từ tiếng Latin bất biến - không thay đổi). Cấu trúc liên kết là nghiên cứu về các đặc tính cấu trúc liên kết của các hình.

Thông thường, các bất biến tôpô là số (hoặc các đối tượng đại số khác) được sử dụng, vì

7

thật thuận tiện để xử lý những bất biến như vậy. Chúng được sử dụng chủ yếu cho lời giải bài toán dường như vô vọng: để chứng minh rằng hai hình $A$ và $B$ không phải là hình học.

Thật vậy, để chứng minh rằng điều gì đó có thể được tha thứ (trong trường hợp của chúng tôi là phép hình học $h: A \rightarrow B$), chỉ cần đưa ra một phiên bản của cách xây dựng này là đủ. Làm thế nào bạn có thể chứng minh rằng một cái gì đó không thể được xây dựng? Để làm điều này, bạn cần phải xem qua tất cả các phương án xây dựng có thể có (đối với chúng tôi - ánh xạ $h: A \rightarrow B$) và kiểm tra xem không có phương án nào phù hợp (không phải là hình học). Nhưng có vô số ánh xạ chung $h: A \rightarrow B$, không thể kiểm tra hết được. Nó sẽ như thế nào?

Đây là lúc các bất biến số sẽ giúp ích. Đặt mỗi hình $A$ của lớp đang được xem xét được gán một số $q(A)$ và số tương tự được gán cho các hình địa khí tượng. Đặt các số $A$ và $B$ sao cho $q(A) \neq q(B)$. thì chúng không thể là hình học, không thể xây dựng được hình học $h: A \rightarrow B$!

Sự đơn giản đáng kinh ngạc của lý luận này ẩn chứa chiều sâu và tầm quan trọng của nó. Một bản in đang được tạo ra rằng anh ta đã lừa dối chúng tôi bằng cách giấu độ khó bài toán ở một nơi không xác định. Điều này không có gì đáng ngạc nhiên: những bất biến đã xuất hiện - những con số ẩn giấu đằng sau con quỷ đại số trừu tượng, một kẻ xảo quyệt và chơi khăm vĩ đại.

Ví dụ 2. Chữ $B$ là một hình gồm có hai phần không liên quan với nhau. Hầu hết các chữ cái còn lại của bảng chữ cái tiếng Nga bao gồm một phần mạch lạc (ngoại trừ các chữ cái $I$, $E$). Số lượng kết nối của các “mảnh” trong đó một hình bao gồm (còn gọi là số thành phần của một hình) là một bất biến tôpô. Do đó, chữ cái $B$ không có tính chất hình học, chẳng hạn như chữ cái $O$, chữ cái $П$, chữ cái $Ц$, v.v.

Ví dụ 3. Trên hình 8 (Hình 4, $a$) có một điểm $x$ mà sau khi loại bỏ nó (Hình 4, $b$) chúng ta được một hình không mạch lạc (chứa nhiều hơn một thành phần). Điểm có thuộc tính này được gọi là điểm phân tách của hình. Không có điểm nào của hình tám ngoài $x$ là điểm phân tách (Hình 4, $b$).

Nếu điểm $x$ của hình $A$ là điểm phân vùng, thì nó vẫn như vậy đối với bất kỳ hình học nào của hình $A$, tương tự đối với điểm không phân vùng. Do đó, số điểm chia của một hình đã cho là bất biến tôpô của nó và số điểm không chia cũng là bất biến tôpô.

Bài toán

1. Đối với mỗi chữ cái trong bảng chữ cái tiếng Nga, hãy cho biết nó chứa bao nhiêu dấu chấm ngắt và không ngắt. Chứng minh rằng các chữ cái $O$, $Г$, $T$, $B$ không phải là hình học theo cặp.

2. Chứng minh rằng với mọi số tự nhiên $n$ đều tồn tại một hình chứa số điểm chia $n$ bằng nhau và một hình chứa số điểm không chia bằng $n$.

Ví dụ 4. Cho $A$ là một đồ thị và $x$ đỉnh của nó. Số cạnh của đồ thị $A$ hội tụ thành $x$ được gọi là chỉ số của đỉnh $x$ trong đồ thị $A$ (trong trường hợp này, netla - một cạnh có đầu và cuối ở cùng một đỉnh $x$ - được tính là hai cạnh hoặc được bao gồm trong $x$ với cả hai đầu của nó). Trong Hình 5, các đỉnh $a, b, c, d$ có chỉ số lần lượt là 1, 2, 3, 4. Số đỉnh có chỉ số $n \neq 2$ có trong đồ thị là bất biến tôpô. Tại sao chúng ta phải loại trừ các đỉnh ở chỉ số 2?

Bài toán

3. Chứng minh rằng các chữ cái $IO$ và $Ф$ không phải là hình học. Không được chỉ định. Lợi dụng thực tế là số đỉnh tại chỉ số $k (k \neq 2)$ là bất biến.

4. Hình thành điều kiện cần và đủ điều kiện, theo đó một hình gồm một số hữu hạn cung là hình học của một đường tròn.

5. Đặt $G$ là một đồ thị. Bằng $a_k(G)$ chúng ta biểu thị số đỉnh của biểu đồ này có chỉ số $k$. Chứng minh rằng số cạnh của đồ thị là $G$

8

Phải

$$\frac{1}{2} (a_1(G) + 2a_2(G) + 3a_3(G) + \dots).$$

6. Chứng minh rằng trong mọi đồ thị số đỉnh có chỉ số lẻ là số chẵn.

Địa điểm Königsberg

Một đồ thị được gọi là một đường (hoặc Euler) nếu nó có thể được “vẽ bằng một nét”, nghĩa là, nó có thể được đi khắp nơi trong một chuyển động liên tục mà không đi qua cùng một cạnh hai lần. Tính chất của đồ thị là đơn hướng rõ ràng là một bất biến tôpô. Tuy nhiên, bất biến tôpô này không phải là mới mà được thể hiện thông qua khái niệm chỉ số đỉnh (xem bài toán 9).

Bài toán

7. Chứng minh rằng nếu mỗi đỉnh của đồ thị có chỉ số không thay đổi bằng 2 thì từ các cạnh của đồ thị này có thể dựng được một đường thẳng đồng cấu thành một đường tròn.

8. Chứng minh rằng nếu tất cả các đỉnh của một đồ thị liên thông có chỉ số chẵn thì đồ thị này có thể được “vẽ bằng một nét”, bắt đầu từ một đỉnh tùy ý và quay về cùng một đỉnh đó.

9. Chứng minh rằng một đồ thị liên thông là một đồ thị khi và chỉ khi nó chứa nhiều nhất hai đỉnh có chỉ số lẻ.

Liên quan đến đồ thị một chiều là bài toán về các địa điểm ở Königsberg, được Euler xem xét. Vào thời điểm đó ở Königsberg có bảy địa điểm bên kia sông Pregel (Hình 6, a). Bài toán là để tìm hiểu xem liệu có thể, khi đi dạo quanh thành phố, đi qua mỗi nơi đúng một lần hay không. Hãy so sánh một biểu đồ nhất định với quy hoạch thành phố: đỉnh L biểu thị bờ trái, Π - bờ phải, A và B - đảo và các cạnh của biểu đồ tương ứng với các địa điểm (Hình 6, b). Trong biểu đồ này, cả bốn đỉnh đều có chỉ số lẻ. Do đó, đồ thị không phải là đồ thị đơn hướng và do đó tuyến đường yêu cầu không tồn tại.

Bài toán

10. Chứng minh rằng bằng cách thêm một địa điểm nữa (nơi góc nằm trong sơ đồ Hình 6, a), chúng ta sẽ có được một bản đồ thành phố mà theo đó chúng ta có thể đi qua từng địa điểm một lần.

11. Đồ thị đầy đủ là đồ thị không có vòng lặp trong đó hai đỉnh bất kỳ được nối với nhau bằng đúng một cạnh. Trong trường hợp nào một đồ thị hoàn chỉnh là đơn hướng?

Cách xây dựng biểu đồ được kết nối

Bất kỳ đồ thị nào cũng có thể được “xây dựng” bằng cách thêm hết cạnh này đến cạnh khác (tất nhiên, các đỉnh của đồ thị cũng cần được đánh dấu). Việc đánh số các cạnh của đồ thị ở Hình 7 được chọn sao cho khi vẽ đồ thị theo cách đánh số này luôn thu được các đồ thị liên thông. Tuy nhiên, nếu chúng ta đánh số các cạnh theo thứ tự ngược lại thì khi vẽ, ban đầu chúng ta sẽ có một biểu đồ không mạch lạc. Hóa ra trong mọi đồ thị liên thông đều có cách đánh số các cạnh nên khi vẽ đồ thị theo cách đánh số này, luôn thu được các đồ thị liên thông. Tuyên bố này có thể được gọi là “định lý vẽ đồ thị liên thông”.

Bài toán

12. Chứng minh rằng bất kỳ đồ thị liên thông nào cũng có thể được “vẽ bằng một nét” nếu bạn cho phép mỗi đồ thị được duyệt theo chiều dọc trong một thời gian.

13. Suy ra phát biểu trước bài toán định lý về vẽ đồ thị liên thông.

9

14. Chứng minh rằng hai đỉnh bất kỳ của một đồ thị liên thông $G$ có thể được nối với $G$ bằng một chuỗi các cạnh đơn giản—một chuỗi sao cho phần giao của các cạnh của chuỗi này là một đường thẳng đồng cấu với một đoạn.

Trong rừng có bao nhiêu cây?
Đường viền trong biểu đồ là một chuỗi các cạnh khép kín, sự kết hợp của chúng được biểu thị bằng một đường đồng cấu với một đoạn (Hình 8). Biểu đồ được kết nối không chứa một đường viền duy nhất được gọi là cây (Hình 9). Hãy chứng minh rằng trong một cây bất kỳ số đỉnh và số cạnh $P$ liên hệ với nhau bởi hệ thức

$$B - P = 1.$$ (1)

Để chứng minh điều này, ta dùng quy nạp theo số cạnh $P$. Đối với $P = 1$ (cây chỉ có một cạnh và có hai đỉnh), quan hệ (1) là hợp lệ. Giả sử rằng đối với bất kỳ cây nào có $n$ cạnh, mối quan hệ (1) đã được chứng minh và đặt $G$ là cây có $n + 1$ cạnh. Vì đồ thị $G$ được kết nối nên có thể thu được nó từ một số đồ thị liên thông $G'$ bằng cách thêm một cạnh $r$. Đồ thị $G'$ chứa $n$ cạnh và cũng là một cây (tại sao?). Theo giả thuyết quy nạp, hệ thức (1) đúng với đồ thị $G'$, và do đó nó có các đỉnh $n + 1$. Bây giờ chúng ta lưu ý rằng chỉ một trong các cạnh được thêm $r$ là đỉnh của đồ thị $G'$ (nói cách khác, nhờ bài toán 14, khi thêm cạnh $r$ một đường viền sẽ xuất hiện trong đồ thị $G$ - xem Hình 10). Do đó, khi thêm cạnh $r$, một cạnh mới và một đỉnh mới sẽ xuất hiện trong biểu đồ $G$. Nói cách khác, đồ thị $G$ có $n + 2$ đỉnh và $n + 1$ cạnh, và do đó hệ thức (1) là hợp lệ cho nó. Phép quy nạp được thực hiện chứng tỏ đẳng thức (1) cho bất kỳ cây nào.

Hiệu $B - P$ được gọi là đặc tính Euler của đồ thị $G$ và được ký hiệu là $\chi(G)$. Do đó, đẳng thức (1) có nghĩa là đặc tính Euler của bất kỳ cây nào đều bằng 1.

Bài tập

15. Biểu đồ không chứa đường viền được gọi là rừng. Rõ ràng là nếu đồ thị $G$ là một khu rừng thì mỗi thành phần của nó là một cây. Chứng minh rằng nếu $G$ là rừng thì số cây “mọc” trong rừng (tức là số thành phần của đồ thị $G$) là $\chi(G)$.

16. Chứng minh rằng nếu đồ thị $G$ là một cây thì mỗi hai đỉnh của nó chỉ có thể được nối bằng một chuỗi đơn giản. Điều ngược lại có đúng không?

Cây tối đa và hệ thống hiện tại

Bây giờ giả sử $G$ là một đồ thị liên thông không phải là cây. Khi đó $G$ có đường viền; đặt $r_1$ là cạnh bất kỳ có trong đường viền này (Hình 11, a). Bằng cách loại bỏ cạnh $r_1$ khỏi $G$, chúng ta thu được một biểu đồ được kết nối $G'$ (vì các đầu của biểu đồ bị loại bỏ