planar graphs

You are currently browsing articles tagged planar graphs.

Đồ thị phẳng là một trong những đồ thị đặc biệt nhận được nhiều sự quan tâm trong lý thuyết đồ thị do cấu trúc đặc biệt và ứng dụng rộng khắp của nó.

Planar graphs: Đồ thị phẳng là đồ thị mà ta có thể vẽ nó trên một mặt phẳng sao cho cho các cạnh chỉ giao nhau tại các đầu mút.

 
Ví dụ 1: đồ thị đầy đủ $K_4$ là một đồ thị phẳng và đồ thị Petersen không phải là một đồ tị phẳng. Xem Figure 1.
petersen
Figure 1: (a) Đồ thị đầy đủ $K_4$. (b) Một cách vẽ $K_4$ trên mặt phẳng sao cho không có hai cạnh nào cắt nhau. Do đó $K_4$ là một đồ thị phẳng. (c) đồ thị Petersen. Ta không thể vẽ đồ thị Petersen sao cho các cạnh chỉ cắt nhau tại các đầu mút do đó, đồ thị Petersen không phải là một đồ thị phẳng.
Ví dụ 2: đồ thị phẳng còn được dùng trong xử lí ảnh. Coi mỗi pixel là một đỉnh của đồ thị và ta thêm cạnh giữa hai đỉnh nếu hai pixel tương ứng kề nhau. Một bài toán thường gặp trong xử lí ảnh là phân vùng ảnh (image segmentation). Bài toán này có thể quy về tìm một lát cắt cực tiểu của đồ thị (phẳng). Xem Figure 2.

Figure 2: (a) một ảnh số có kích thước 3x3 và (b) một đồ thị phẳng biểu diễn bức ảnh đó.
img-processing

Ví dụ 3: Mạng giao thông, nếu không có cầu vượt, có thể coi là một đồ thị phẳng. Mỗi khi hai đường giao nhau thì nó giao tại một nút giao thông. Ta sẽ coi mỗi nút giao thông là một đỉnh và đường nói giữa hai nút giao thông tương ứng với cạnh nói hai đỉnh đó.

Hai đồ thị đặc biệt mà ta quan tâm trong bài này là $K_5$ và $K_{3,3}$. $K_5$ là đồ thị đầy đủ có 5 đỉnh còn $K_{3,3}$ là đồ thị hai phía đầy đủ có $6$ đỉnh. (Xem Figure 3.) Hai đồ thị này đều không phải là đồ thị phẳng và ta sẽ chứng minh tính chất này trong phần tiếp theo.

kuratowski
Figure 3: (a) đồ thị đầy đủ $K_5$ và (b) đồ thị hai phía đầy đủ $K_{3,3}$.

Remark: Trước khi đọc tiếp, mình khuyến khích bạn đọc xem lại bài giới thiệu về đồ thị để làm quen với một số khái niệm cơ bản. Ta sẽ không nhắc lại các khái niệm đó ở đây.

Công thức Euler

Gọi $G$ là một đồ thị phẳng có $n = |V(G)|$ đỉnh và $m = |E(G)|$ cạnh. Cố định một cách vẽ $G$ trên mặt phẳng. Nếu ta xóa tất cả các điểm của mặt phẳng nằm trên cạnh và đỉnh cùa đồ thị, ta sẽ thu được một số các vùng (regions) của mặt phẳng, trong đó có đúng một vùng vô hạn (infinite region). Ta gọi mỗi vùng đó là một mặt (face) của đồ thị, và mặt tương ứng với vùng vô hạn ta gọi nó là một mặt vô hạn (infinite face) của đồ thị. Gọi $f$ là số mặt của đồ thị. Ta có:

Euler's formula: Mọi đồ thị phẳng và liên thông $G$ đều thoải mãn:

$n - m + f = 2 \qquad (1)$

 
Chứng minh: Ta chứng minh bằng quy nạp trên số cạnh của đồ thị. Chú ý, đồ thị liên thông và có ít cạnh nhất là một cây. Gọi $T$ là một cây khung bất kì của $G$. Dễ thấy $T$ có $n$ đỉnh, $n-1$ cạnh và 1 mặt. Do đó, (1) đúng.

Giả sử $(1)$ đúng với mọi đồ thị con $G'$ của $G$ có cùng số đỉnh và số cạnh $m-1$. Gọi $f(G')$là số mặt của $G'$. theo giả thiết quy nạp, ta có:

$n - (m-1) + f(G') = 2 \qquad (2)$

Gọi $e = E(G)\setminus E(G')$. Do khi ta thêm $e$ vào một mặt nào đó của $G'$, $e$ chia mặt đó ra làm $2$ mặt mới. Do đó, $f(G) = f(G') +1$. Thay vào $(2)$, ta được:

$n - (m-1) + f(G)-1 = 2$

Từ đó suy ra dpcm.


Ví dụ 4: Trong Figure 1(b), đồ thị $K_4$ có 4 đỉnh, 6 cạnh và khi vẽ trên mặt phẳng đồ thị này có 4 mặt. Dễ dàng thấy rằng công thức Euler đúng trong trường hợp này.

Đồ thị phẳng là một đồ thị thưa

Ta định nghĩa độ dài của một mặt (length of a face) $f$, kí hiệu $\ell(f)$, là số cạnh của đồ thị nằm trên biên của mặt $f$. Do mỗi cạnh nằm trên biên của tối đa hai mặt, ta có:

Observation 1: Nếu mọi mặt $f$ của $G$ đều thỏa mãn $\ell(f) \geq d$ thì $f \leq \frac{2}{d}m$.

 

Từ Observation 1 và công thức Euler, ta có:

Lemma 1: Mọi đồ thị phẳng, đơn (simple) có ít nhất $3$ đỉnh thỏa mãn:

$m \leq 3n-6 \qquad (3)$

 
Chứng minh: Do đồ thị là đơn, mỗi mặt có ít nhất $3$ cạnh. Do đó, theo Observation 1 ($d = 3$), $f \leq \frac{2}{3}m$. Áp dụng công thức Euler, ta có:

$2 \leq n - m + \frac{2}{3}m$

Từ đó ta suy ra dpcm.


Lemma 1 cho ta biết đồ thị phẳng là một đồ thị rất thưa. Do đó, một cách kiểm tra đơn giản xem một đồ thị có thể là đồ thị phẳng hay không bằng cách kiểm tra xem số cạnh $m$ có vượt quá $3n-6$ hay không. Một trong số đồ thị có nhiều cạnh như vậy là $K_5$. Do $K_5$ có 5 đỉnh và $10$ cạnh, ta có:

Corollary 1: $K_5$ không phải là đồ thị phẳng.

 

Cũng từ Observation 1 và công thức Euler, ta có:

Lemma 2: Gọi $G$ là đồ thị đơn có ít nhất 4 đỉnh. Nếu mọi chu trình (cycle) trong $G$ đều có ít nhất 4 cạnh thì:

$m \leq 2n-4 \qquad (4)$

 
Chứng minh Lemma 2 tương tự như chứng minh Lemma 1, mình coi đây là bài tập cho bạn đọc. Do $K_{3,3}$ có $6$ đỉnh, $9$ cạnh và mọi chu trình đều có $4$ cạnh, theo Lemma 2, ta có:

Corollary 2: $K_{3,3}$ không phải là một đồ thị phẳng.

 

Các khối Plato

Một đa diện (polyhedron) được gọi là đều nếu các mặt là các đa giác đều và các đỉnh của đa diện đều có cùng bậc. Một khối Plato (Platonic solid) là một đa diện lồi và đều. Trong thực tế, chúng ta chỉ có đúng 5 khối Plato: tứ diện đều (tetrahedron), hình lập phương (hexahedron), bát diện đều (octahedron), thập nhị diện đều (dodecahedron) và nhị thập diện đều (icosahedron). Xem Figure 4.

platonic-solids
Figure 4: 5 khối Plato, với số đỉnh, mặt và cạnh. Hình vẽ được cắt từ wikipedia.

Tất cả các khối Plato đều là đồ thị phẳng, do đó, nó cũng tuân theo công thức Euler ở trên. Sử dụng công thức Euler, ta sẽ chứng minh chỉ có đúng 5 khối Plato.

Lemma 2: Chỉ tồn tại đúng 5 khối Plato.

 
Chứng minh: Gọi $p$ và $q$ lần lượt là chiều dài mặt và bậc của đỉnh của khối Plato. Do mỗi cạnh chỉ nằm trên đúng 2 mặt, ta có:

$pf = 2m \qquad \mbox{and} \qquad qn = 2m \qquad (5)$

Thay phương trình $(5)$ vào công thức Euler, ta được $2m/q - m + 2m/p = 2$. Từ đó ta suy ra:

$\frac{1}{p} + \frac{1}{q} \mbox{>} \frac{1}{2} \qquad (6)$

Chú ý, $p,q \geq 3$. Từ $(6)$ ta suy ra $\min(p,q) = 3$ và $ 3 \leq \max(p,q) \leq 5$. Do đó, tồn tại đúng 5 cặp $(p,q) \in \{(3,3), (3,4), (3,5), (4,3), (5,3)\}$ tương ứng với 5 khối Plato mô tả trong Figure 4.


(còn tiếp)

Tags: , , ,

« Older entries § Newer entries »