Các loại đồ thị đặc biệt

Đồ thị đầy đủ.

Đồ thị đầy đủ n đỉnh, ký hiệu bởi K_n, là đơn đồ thị vô hướngmà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối.

Các đồ thị K₃, K₄, K₅ cho trong hình dưới đây.

Đồ thị đầy đủ K_n có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất.

Đồ thị vòng.

Đồ thị vòng C_n, n≥3. gồm n đỉnh v₁, v₂,. . . .v_n và các cạnh (v₁,v₂), (v₂,v₃) . . . (v_n-1,v_n), (v_n,v₁).

Đồ thị vòng C₃, C₄, C₅, C₆ cho trong hình 2.2

Hình 2.2 Đồ thị vòng C 3 , C 4 , C 5 , C 6 .

Đồ thị bánh xe.

Đồ thị W_n thu được từ C_n bằng cách bổ sung vào một đỉnh mới nối với tất cả các đỉnh của C_n (xem hình 2.3).

Hình 2.3 Đồ thị bánh xe W 3 , W 4 , W 5 , W 6 .

Đồ thị lập phương.

Đồ thị lập phương n đỉnh Q_n là đồ thị với các đỉnh biểu diễn 2ⁿ xâu nhị phân độ dài n. Hai đỉnh của nó gọi là kề nhau nếu như hai xâu nhị phân tương ứng chỉ khác nhau 1 bit. Hình 2.4 cho thấy Q_n với n=1,2,3.

Hình 2.4 Đồ thị lập phương Q 1 , Q 2 , Q 3 .

Đồ thị hai phía.

Đơn đồ thị G = (V, E) được gọi là hai phía nếu như tập đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho mỗi cạnh của đồ thị chỉ nối một đỉnh nào đó trong X với một đỉnh nào đó trong Y. Khi đó ta sẽ sử dụng ký hiệu G = (XY, E) để chỉ đồ thị hai phía với tập đỉnh XY.

Định lý sau đây cho phép nhận biết một đơn đồ thị có phải là hai phía hay không.

Định lý 1

Đơn đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ.

Để kiểm tra xem một đồ thị liên thông có phải là hai phía hay không có thể áp dụng thủ tục sau. Cho v là một đỉnh bất kỳ của đồ thị. Đặt X={v}, còn Y là tập các đỉnh kề của v. Khi đó các đỉnh kề của các đỉnh trong Y phải thuộc vào X. Ký hiệu tập các đỉnh như vậy là T. Vì thế nếu phát hiện T  Y ≠ ∅ thì đồ thị không phải là hai phía, kết thúc. ngược lại, đặt X = X  T. Tiếp tục xét như vậy đối với T’ là tập các đỉnh kề của T,. ..

Đồ thị hai phía G=(X  Y, E) với |X|= m, |Y| = n được gọi là đồ thị hai phía đầy đủ và ký hiệu là K_2,3, K_3,3, K_3,4 được cho trong hình 2.5.

Hình 2.5 Đồ thị hai phía.

Đồ thị phẳng.

Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị.

Ví dụ đồ thị K₄ là phẳng, vì có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh (xem hình 2.6).

Hình 2.6 Đồ thị K 4 là đồ thị phẳng.

Một điều đáng lưu ý nếu đồ thị là phẳng thì luôn có thể vẽ nó trên mặt phẳng với các cạnh nối là các đoạn thẳng không cắt nhau ngoài ở đỉnh (ví dụ xem cách vẽ K₄ trong hình 2.6).

Để nhận biết xem một đồ thị có phải là đồ thị phẳng có thể sử dụng định lý Kuratovski, mà để phát biểu nó ta cần một số khái niệm sau: Ta gọi một phép chia cạnh (u,v) của đồ thị là việc loại bỏ cạnh này khỏi đồ thị và thêm vào đồ thị một đỉnh mới w cùng với hai cạnh (u,w), (w, u) . Hai đồ thị G(V,E) và H=(W,F) được gọi là đồng cấu nếu chúng có thể thu được từ cùng một đồ thị nào đó nhờ phép chia cạnh.

Định lý 2 (Kuratovski).

Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng cấu với K 3,3 hoặc K 5 .

Trong trường hợp riêng, đồ thị K_3,3 hoặc K₅ không phải là đồ thị phẳng. Bài toán về tính phẳng của đồ thị K_3,3 là bài toán đố nổi tiếng về ba căn hộ và ba hệ thống cung cấp năng lượng cho chúng: Cần xây dựng hệ thống đường cung cấp năng lượng với mỗi một căn hộ nói trên sao cho chúng không cắt nhau.

Đồ thị phẳng còn tìm được những ứng dụng quan trọng trong công nghệ chế tạo mạch in.

Biểu diễn phẳng của đồ thị sẽ chia mặt phẳng ra thành các miền, trong đó có thể có cả miền không bị chặng. Ví dụ, biểu diễn phẳng của đồ thị cho trong hình 2.7 chia mặt phẳng ra thành 6 miền R_1, R_2,. . . .R₆.

Các miền tương ứng với biểu diễn phẳng của đồ thị.

Euler đã chứng minh được rằng các cách biểu diễn phẳng khác nhau của một đồ thị đều chia mặt phẳng ra thành cùng một số miền. Để chứng minh điều đó, Euler đã tìm được mối liên hệ giữa số miền, số đỉnh của đồ thị và số cạnh của đồ thị phẳng sau đây.