Đồ thị phẳng

Kvant 1981, số 7 tr. 11, 13, 14, 15, 16 Thẻ 1T1R

Bản dịch tự động sơ bộ, chất lượng thấp: có thể còn lỗi và câu chữ chưa tự nhiên. Bản này sẽ được thay bằng bản dịch tốt hơn. Bản gốc →

V. Boltyansky

Đồ thị Plockian

Trong bài viết này, chúng tôi tiếp tục nghiên cứu các tính chất tôpô của đồ thị, đã bắt đầu từ số trước của tạp chí. Lần này chúng ta sẽ nói về một số tính chất sâu của đồ thị phẳng. Việc nghiên cứu chúng sẽ đòi hỏi sự kết hợp giữa “con quỷ đại số trừu tượng” và một trong những tay sai của hắn - một bất biến được gọi là chỉ số giao.

Ba ngôi nhà và ba cái giếng

Đồ thị $A$ được cho là có thể nhúng vào mặt phẳng nếu có đồ thị $A'$ trên mặt phẳng có dạng hình học $A$ . Do đó, một đồ thị bao gồm các cạnh của một khối tứ diện và một đồ thị bao gồm các cạnh của hình lập phương đều có thể nhúng được vào mặt phẳng (Hình 1).

Chúng ta hãy đưa ra hai ví dụ về đồ thị không thể nhúng vào một mặt phẳng.

Ví dụ 1 (“nhà và giếng”). Sáu điểm được cho trên mặt phẳng: $D_1, D_2, D_3$ (nhà) và $K_1, K_2, K_3$ (giếng); Có thể vẽ đường nhiệt đới trên mặt phẳng từ mỗi nhà đến từng giếng sao cho không có hai đường nhiệt đới nào giao nhau không?

Hình 1.
Hình 2.

rằng mỗi chu trình là một tập hợp của một số hữu hạn các đường đứt nét, mỗi đường đứt đoạn nằm trên một đường tròn (và các đường đứt nét này theo cặp không có liên kết chung).

Pozny chỉ cần thiết lập một tuyên bố khá có thể chứng minh là đủ trong trường hợp mỗi chu kỳ $x, y$ bao gồm một vòng tròn chia sẻ mái ấm gia đình bị hỏng. Bằng cách di chuyển nhẹ các đỉnh của chu trình $x$ và $y$ , chúng ta có thể đảm bảo rằng chỉ số $I(x, y)$ không thay đổi và không có đoạn nào trong chu trình $x$ song song với bất kỳ đoạn nào có trong $y$ . Chúng ta hãy chọn một đường thẳng $l$ không song song với bất kỳ đường thẳng nào nối bất kỳ đỉnh nào của chu trình $x$ với bất kỳ đỉnh nào của chu kỳ $y$ , và chúng ta sẽ liên tục di chuyển chu trình $x$ (như một tổng thể cứng nhắc) song song với đường thẳng $l$ (Hình 5). Chỉ số giao nhau $I(x, y)$ chỉ có thể thay đổi tại những thời điểm khi các đỉnh của chu trình kép $x$ đi qua các cạnh của chu trình cố định $y$ hoặc khi các cạnh của chu trình $x$ đi qua các đỉnh của chu trình $y$ (các đỉnh của chu trình $x$ không thể đi vào các đỉnh của chu trình $y$ do chọn đường thẳng $l$ ). Tuy nhiên, như Hình 6 cho thấy, tại thời điểm khi một số cạnh $a$ của chu kỳ $x$ đi qua đỉnh $q$ của chu kỳ $y$ , số điểm giao nhau không thay đổi tính chẵn lẻ của nó và do đó chỉ số giao nhau $I(x, y)$ không thay đổi. Điều tương tự cũng xảy ra khi các đỉnh của chu trình $x$ đi qua các cạnh của chu trình $y$ .

Vì vậy, trong toàn bộ chuyển động chỉ số giao nhau không thay đổi và bất biến. Nhưng cuối cùng chu trình $x$ kết thúc ở vị trí không có điểm chung với $y$ (xem Hình 5), do đó chỉ số giao nhau trở thành 0. Do đó, ban đầu nó là $I(x, y) = 0$ .

Không thể nhúng của biểu đồ patvertex hoàn chỉnh

Bây giờ chúng ta có thể chứng minh rằng đồ thị $P_2$ được xem xét trong Ví dụ 2 không thể nhúng vào mặt phẳng. Hãy nối 5 điểm trên mặt phẳng theo cặp bằng các đường đứt nét, tạm thời không chú ý đến các giao điểm. Các mép gãy không có đầu chung gọi là tình trạng không có cuống. Chúng ta hãy biểu thị bằng $J$ tổng các chỉ số giao nhau trên tất cả các tham số của các cạnh RES. Tất nhiên, con số $J$ phụ thuộc vào cách vẽ các cạnh trên mặt phẳng. Nếu chúng có thể được vẽ mà không có giao điểm thì số $J$ sẽ bằng 0. Tuy nhiên, chúng ta sẽ chứng minh rằng với bất kỳ

Cách kiểm tra cạnh là số J lẻ. Điều này sẽ chứng minh rằng đồ thị $P_2$ không thể nhúng vào mặt phẳng.

Giả sử chúng ta thay đổi vị trí của một cạnh, chẳng hạn như $M_1M_2$ . Chúng tôi biểu thị vị trí ban đầu của cạnh này bằng $x$ và vị trí mới của nó bằng $x'$ . Không liền kề với cạnh $M_1M_2$ là ba cạnh ( $M_3M_4$ , $M_4M_5$ , $M_5M_3$ ). Đa tuyến khép kín $M_3M_4M_5$ (có thể giao nhau với chính nó) là một chu trình; hãy biểu thị nó bằng $y$ (Hình 7). Các đường đứt nét $x$ và $x'$ gộp lại với nhau cũng tạo thành một chu trình. Vì chỉ số giao nhau của hai chu kỳ bất kỳ bằng 0:

$I(x \cup x', y) = 0,$

số giao điểm của cạnh $x$ với chu trình $y$ (tức là với tất cả các cạnh không liền kề với nó) có cùng độ chẵn lẻ với số giao điểm của cạnh $x'$ với chu trình $y$ .

Như vậy, khi thay cạnh $x$ bằng cạnh $x'$ thì số $J$ không thay đổi tính chẵn lẻ của nó.

Từ những gì đã được chứng minh, ta suy ra rằng đối với mọi cách sắp xếp các cạnh trên mặt phẳng, số $J$ luôn có cùng tính chẵn lẻ. Thật vậy, nếu đưa ra hai cách sắp xếp các cạnh khác nhau, thì, tuần tự chú ý đến cạnh đầu tiên của cách sắp xếp thứ nhất với cạnh tương ứng của cách sắp xếp thứ hai, sau đó là cạnh khác, cách sắp xếp khác, v.v., chúng ta sẽ dần dần thay thế cách sắp xếp thứ nhất bằng cách sắp xếp thứ hai, và tính chẵn lẻ của số $J$ , theo những gì đã được chứng minh, sẽ không thay đổi.

Vì vậy, đối với tất cả các vị trí cạnh, số $J$ chẵn hoặc lẻ cho tất cả các vị trí. Trong Hình 3 chỉ có một điểm giao nhau (tất nhiên, các cạnh cong trong hình này có thể được thay thế bằng các đường đứt nét). Như vậy trên hình 3 là số $J$ bằng một, và do đó với mọi cách sắp xếp các cạnh thì nó là số lẻ và do đó, $P_2$ Chúng ta đừng đặt nó trong một chiếc máy bay.

Bài toán

Chứng minh rằng đồ thị $P_1$ từ Ví dụ 1 không thể nhúng vào mặt phẳng.
Các cạnh của đồ thị là các cạnh và hầu hết các đường chéo của $n$ -giác đều

$(n > 3)^*$ . Chứng minh rằng thậm chí $n$ đồ thị này có thể được nhúng vào một mặt phẳng, nhưng nếu nó là số lẻ thì không thể.

Các cạnh của đồ thị là các cạnh và hầu hết các đường chéo*) của một $2n$ -giác thông thường. Chứng minh rằng với $n \geqslant 3$ đồ thị này không thể nhúng vào mặt phẳng.
Các cạnh của đồ thị là các cạnh và hầu hết các đường chéo*) ( $2n+1$ đều $(2n+1)$ -giác của chúng. Chứng minh rằng đồ thị này không thể nhúng vào mặt phẳng.

Nó không thể đơn giản hơn sao?

Ở trên (xem Hình 5, 6), chúng ta đã chứng minh rằng chỉ số giao nhau của hai chu trình bất kỳ trên mặt phẳng đều bằng 0. Có lẽ bạn đọc sẽ gợi ý cách chứng minh đơn giản hơn sau: ta sẽ đi theo đường đứt nét kín $x$ ; tại mỗi điểm giao nhau với đường đứt nét kín $y$ chúng ta sẽ đi vào vùng bên trong của đường đứt nét $y$ hoặc để vào vùng bên ngoài; vì điểm vào và điểm thoát đi qua một điểm nên số điểm vào bằng số điểm thoát; Điều này có nghĩa là tổng số giao điểm của các đường đứt nét $x$ và $y$ là số chẵn.

Tuy nhiên, bằng chứng này chỉ có thể được coi là đúng nếu ý nghĩa của khái niệm “khu vực nội bộ” đã rõ ràng và khái niệm này thoạt nhìn không đơn giản chút nào. Ý nghĩa của khái niệm này được làm rõ.

Định lý Jordan

Một đường khép kín đồng phôi với một đường tròn được gọi là đường khép kín đơn giản.

*) Hơn nữa, các “đường chéo” của giáo viên được nâng lên trong không gian và do đó không giao nhau theo cặp.

dòng băm nhỏ. Định lý Jordan là bất kỳ đường khép kín đơn giản nào nằm trên một mặt phẳng đều chia mặt phẳng này thành hai phần (bên trong và bên ngoài). Hãy giải thích ý nghĩa của định lý này. Cho $l$ là một đường khép kín đơn giản trên mặt phẳng. Chúng ta hãy lấy các điểm, $p, q$ , không nằm trên đường thẳng $l$ . Nếu $p$ và $q$ có thể được nối bằng một đường đứt nét không giao nhau với $l$ thì các điểm $p$ và $q$ được coi là nằm trong cùng một vùng so với đường $l$ . Nếu bất kỳ đường đứt đoạn nào nối các điểm $p$ và $q$ nhất thiết phải giao nhau với $l$ thì chúng tôi coi rằng $p$ và $q$ nằm ở các khu vực khác nhau. Định lý Jordan phát biểu rằng đường thẳng $l$ xác định hai vùng mặt phẳng.

Người ta không nên nghĩ rằng định lý Jordan phát biểu điều gì đó hoàn hảo. Mỗi “sự hiển nhiên” của nó chỉ được giải thích bởi thực tế là những đường rất đơn giản thường xuất hiện trong đầu bạn (hình tròn, đường viền của đa giác lồi, v.v.). Trong trường hợp tổng quát, phát biểu

Hình 8.

Phần cuối của định lý Jordan không rõ ràng lắm. Hình 8 cho thấy một đường đa tuyến khép kín đơn giản (có thể kiểm tra điều này bằng cách vẽ một đường bằng bút chì). Tuy nhiên, không hề rõ ràng rằng mặt phẳng bị đường này cắt thành hai vùng; ví dụ, không thể xác định ngay được điểm $a, b, c, d$ nằm ở khu vực nào (bên trong hay bên ngoài).

Chúng ta sẽ chứng minh định lý Jordan dựa trên việc áp dụng chỉ số giao. Trong trường hợp này, chúng tôi giới hạn bản thân trong trường hợp khi $l$ không phải là một đường khép kín đơn giản tùy ý trên mặt phẳng, mà là một đường gãy khép kín đơn giản.

Đặt $b_1, b_2, \dots, b_n$ là các mắt xích liên tiếp của đường đứt nét $l$ . Hãy vẽ một đoạn liên kết giao nhau $b_1$ tại điểm $a$ và lấy hai điểm $p, p'$ trên đoạn này, nằm ở hai phía đối diện của liên kết $b_1$ ở cùng một khoảng cách với nó. Thông qua các điểm $p$ , chúng ta vẽ một đoạn song song với liên kết $b_1$ đến điểm giao nhau của nó với bisertric của góc giữa các liên kết $b_1$ và $b_2$ (Hình 9). Từ điểm giao nhau này, chúng ta vẽ một đoạn song song với $b_2$ cho đến khi nó giao với bisertric của góc giữa các liên kết $b_2$ và $b_3$ , v.v. Kết quả là chúng ta thu được một đường đứt nét $x$ , các liên kết của chúng có cùng khoảng cách với các liên kết tương ứng của đường gãy $l$ . Nếu trong trường hợp này, điểm $p$ được lấy đủ gần với $a$ thì đường được xây dựng $x$ không giao nhau $l$ và việc đi dọc theo đường $l$ sẽ quay trở lại điểm $p$ hoặc tới $p'$ . Tuy nhiên, dễ hiểu là đường đứt nét $x$ thuộc về điểm $p'$ nếu đường đứt nét $x$ nối các điểm $p$ và $p'$ , thì bằng cách thêm đoạn $pp'$ vào $x$ , chúng ta sẽ thu được một chu trình giao với chu trình $l$ tại một điểm duy nhất $a$ , tức là chỉ số giao nhau của hai chu trình này bằng 1, điều này là không thể. Vì vậy, $x$ là một đa tuyến đóng xuất phát từ điểm $p$ , đi một lần dọc theo đường đứt nét $l$ và quay trở lại điểm $p'.$ Tương tự, ta được một đa tuyến đóng $x'$ , đi một lần dọc theo đường đứt nét $p'$ , một lần đi dọc theo đường gãy $l$ và quay trở lại điểm $p'$ .

Bây giờ giả sử $c$ là một điểm tùy ý không nằm trên đường thẳng $l$ . Sau đó, nó có thể được tạo điều kiện thuận lợi mà không cần giao nhau $l$ , với điểm $p$ hoặc với điểm $p'$ : chỉ cần kiểm tra từ điểm $c$ các tia giao nhau với các đường $x, x'$ và từ điểm $c$ đi đến điểm giao nhau đầu tiên của tia này với bất kỳ đường thẳng nào $x, x'$ , rồi dọc theo đường này đến điểm $p$ hoặc $p'$ .

Không khó hiểu khi hai đường đứt nét $y, z$ khác nhau được vẽ từ điểm $c$ , không cắt nhau $l$ và kết thúc tại một trong các điểm $p, p'$ , thì cả hai đều có cùng một điểm. Trên thực tế, nếu đường đứt nét $y$ nối điểm $c$ với $p$ và đường đứt nét $z$ nối điểm $c$ với $p'$ (Hình 10), thì đường đứt nét $y \cup z$ cùng với đoạn $pp'$ sẽ tạo thành một chu trình có chỉ số giao nhau với chu trình $l$ bằng 1, điều này là không thể.

Bây giờ việc chứng minh định lý Jordan không khó. Chúng ta hãy biểu thị bằng $U$ tập hợp tất cả các điểm trên mặt phẳng có thể nối với điểm $p$ mà không cắt nhau $l$ và bằng $V$ là tập hợp các điểm có thể nối với điểm $p'$ mà không cắt nhau $l$ . Khi đó $U$ và $V$ sẽ là hai vùng mà đường $l$ phân chia mặt phẳng. Trong thực tế, nếu điểm

$c_1, c_2$ thuộc cùng một vùng (giả sử $U$ ) thì có các đường đứt nét $y_1, y_2$ , không giao nhau $l$ , nối $c_1$ và $c_2$ với điểm $p$ . Sự kết hợp của họ là một đường đứt đoạn nối $c_1$ và $c_2$ và không giao nhau $l$ . Vì vậy, hai điểm thuộc cùng một vùng có thể được kết nối bằng một đường đa tuyến không giao nhau $l$ (nếu không, như trên, chúng ta sẽ có một chu trình có chỉ số giao nhau là 1 với $l$ ).

Như vậy, định lý Jordan (đối với trường hợp đường đứt nét khép kín đơn giản) đã được chứng minh.

Quét. Tất cả các điểm “xa” của mặt phẳng đều nằm trong cùng một khu vực so với đường $l$ (Hình 11). Do đó, một trong hai vùng được xác định bởi các đường $l$ không bị giới hạn và vùng còn lại bị giới hạn. Vùng không giới hạn được gọi là bên ngoài và vùng giới hạn được gọi là bên trong. Các điểm của vùng bên ngoài được đặc trưng bởi thực tế là từ những điểm này người ta có thể kiểm tra các đường đứt đoạn không giao nhau $l$ và đi xa $l$ như mong muốn; các điểm trong miền nội địa không có tính chất này.

Bài tập.

Nếu đường gãy $l$ rất phức tạp thì rất khó để xác định “bằng mắt” rằng điểm $a$ nằm ở khu vực nào (bên trong hay bên ngoài): để làm được điều này, bạn cần tìm hiểu xem, bắt đầu từ điểm $a$ , có thể thoát ra “mê cung” được hình thành bởi đường $l$ hay không (xem Hình 8). Chứng minh rằng nếu một tia phát ra từ điểm $a$ và không đi qua các đỉnh của đường đứt nét $l$ cắt $l$ tại một số điểm chẵn thì điểm $a$ nằm trong vùng bên ngoài (tức là có thể thoát ra khỏi “mê cung”), còn nếu ở số lẻ thì điểm $a$ nằm trong vùng bên trong.
$k$ các đường đứt nét được vẽ trên mặt phẳng, mỗi đường nối hai điểm cho trước $p$ và $q$ . Chứng minh rằng nếu không có đường đứt nét nào khác theo cặp thì mặt phẳng được chia thành các vùng $k$ .