✨Đồ thị hai phía đầy đủ

Trong lý thuyết đồ thị, một đồ thị hai phía đầy đủ (tiếng Anh: Complete bipartite graph hoặc biclique) là một dạng đồ thị hai phía đặc biệt, trong đó mỗi đỉnh của tập thứ nhất nối với mọi đỉnh thuộc tập thứ hai và ngược lại.

Định nghĩa

Cho $G\; =(X,\; E)$ là một đồ thị vô hướng lưỡng phân với hai tập $X\_1$ và $X\_2$ phân hoạch $X$ ($X\_1$ $\backslash ne$ Ø $\backslash ne$ $X\_2$ và $X\_1$ $\backslash bigcap$ $X\_2$ = Ø). Khi đó $G$ được gọi là lưỡng phân đầy đủ nếu:

  * Với mọi cặp đỉnh(i,j) mà i <math> \in </math> <math>X_1</math> và j <math> \in </math> <math>X_2</math> thì có đúng một cạnh của G nối i và j.

• Mối tương quan giữa đồ thị đầy đủ và đồ thị hai phía đầy đủ:

  * Đồ thị đầy đủ <math>K_{n}</math> có: n đỉnh, <math> \cfrac{n.(n-1)}{2} </math> cạnh
  * Đồ thị hai phía đầy đủ <math>K_{m,n}</math> có: m + n đỉnh, m.n cạnh

Kn; Km,n

Ví dụ

• Với mọi k, $K\_\{1,k\}$ ta có đồ thị hình sao. Đồ Thị Hình Sao1

• Hay với đồ thị $K\_\{1,k\}$ ta có đồ thị hình vuốt, hoặc một cây Đồ Thị Claw hay Tree

• $K\_\{m,n\}$ với m khác n. Đồ thị hai phía đầy đủ Km,n
• $K\_\{m,n\}$ với m = n. Đồ Thị Lưỡng Phân Knn ## Tính chất *Định lý Kuratowski liên quan giữa tính phẳng của đồ thị và $K\_\{3,3\}$: Điều kiện cần và đủ một đồ thị liên thông G có tính phẳng là G không chứa bất kỳ đồ thị con nào đồng phôi với $K\_5$ hay $K\_\{3,3\}$. Đồ thị $K\_\{3,3\}$ là đồ thị không phẳng có ít cạnh nhất.

K3,3 và K5

Một đồ thị hai phía đầy đủ $K\_\{m,n\}$ có số phủ đỉnh (Vertex covering number) bằng $\backslash min\; \backslash lbrace\; m,n\; \backslash rbrace$ và số phủ cạnh (Edge covering number) bằng $\backslash max\backslash lbrace\; m,n\backslash rbrace$ Đồ thị hai phía đầy đủ $K\_\{4,4\}$ là một Cayley Graph.

• Một đồ thị đủ $K${n} có thể được tách thành 4 đồ thị con, mỗi đồ thị con là một đồ thị hai phía đầy đủ, $H${1}, $H${2}, $H${3},... $H\_\{m\}$, sao cho $m\; \backslash ge\; \backslash ;\; n\; -\; 1$

K5 to 4cbg

*Đồ thị hai phía đầy đủ $K\_\{m,n\}$ là k-choosable khi và chỉ khi

Một đồ thị hai phía đầy đủ $K\_\{m,n\}$ có cặp ghép hoàn hảo (Perfect matching) kích thước $\backslash min\backslash lbrace\; m,n\backslash rbrace$ Một đồ thị hai phía đầy đủ $K${n,n} hay $K${n,n+1} là một đồ thị Turán. Một đồ thị hai phía đầy đủ $K\_\{m,n\}$ có mⁿ⁻¹ n^m−1 cây bao trùm Ma trận Laplace của đồ thị hai phía đầy đủ $K${m,n} có các vectơ n+m, n, m, 0; với các vectơ tương thích 1, m-1, n-1, 1. *Một đồ thị hai phía đầy đủ $K${n,n} có một cách tô màu cạnh (Edge coloring) đúng đắn, n_Edge = n_color.

Sắc số của đồ thị $K\_\{m,n\}$ là 2 . Số màu cần thiết để tô màu các cạnh của $K${m,n} là max{m.n} để không có 2 cạnh nào cùng màu mà lại có chung đỉnh. *Đường kính của đồ thị hai phía đầy đủ: $K${1,1} là 1, còn tất cả các $K\_\{m,n\}$ khác đều có đường kính là 2.