Đồ 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., page 5.

 Định nghĩa 
Cho  là một đồ thị vô hướng lưỡng phân với hai tập  và  phân hoạch  (  Ø   và    = Ø). Khi đó  được gọi là lưỡng phân đầy đủ nếu:

      * Với mọi cặp đỉnh(i,j) mà i   và j   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 đủ:, page 66.

      * Đồ thị đầy đủ  có: n đỉnh,  cạnh
      * Đồ thị hai phía đầy đủ  có: m + n đỉnh, m.n cạnh

giữa|1000px|Kn; Km,n

 Ví dụ 
 Với mọi k,  ta có đồ thị hình sao., page 3.
giữa|800px|Đồ Thị Hình Sao1

 Hay với đồ thị  ta có đồ thị hình vuốt, hoặc một cây
giữa|500px|Đồ Thị Claw hay Tree

  với m khác n.
giữa|500px|Đồ thị hai phía đầy đủ Km,n

  với m = n.
giữa|500px|Đồ 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à : Đ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  hay . Đồ thị  là đồ thị không phẳng có ít cạnh nhất.

giữa|500px|K3,3 và K5

Một đồ thị hai phía đầy đủ  có số phủ đỉnh (Vertex covering number) bằng  và số phủ cạnh (Edge covering number) bằng 
Đồ thị hai phía đầy đủ  là một Cayley Graph.Knauer, Ulrich. Algebraic Graph Theory: Morphisms, Monoids and Matrices. Vol. 41. De Gruyter, 2011. Page 270
 Một đồ thị đủ  có thể được tách thành 4 đồ thị con, mỗi đồ thị con là một đồ thị hai phía đầy đủ, , , ,... , sao cho , page 65.

giữa|600px|K5 to 4cbg

Đồ thị hai phía đầy đủ  là k-choosable khi và chỉ khi  , page 155.

Một đồ thị hai phía đầy đủ  có cặp ghép hoàn hảo (Perfect matching) kích thước 
Một đồ thị hai phía đầy đủ  hay  là một đồ thị Turán.Reinhard Diestel. Graph Theory, Electronic Edition 2005. © Springer - Verlag Heidelberg, New York 1997, 2000, 2005.
Một đồ thị hai phía đầy đủ  có mn−1 nm−1 cây bao trùm
Ma trận Laplace của đồ thị hai phía đầy đủ  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 đủ  có một cách tô màu cạnh (Edge coloring) đúng đắn, n_Edge = n_color.

Sắc số của đồ thị  là 2. 
Số màu cần thiết để tô màu các cạnh của  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 đủ:  là 1, còn tất cả các  khác đều có đường kính là 2., page 269, 270.

 Xem thêm 
 Đồ thị hai phía
 Đồ thị chu trình
 Đồ thị đầy đủ
 Ma trận kề
Tham khảo

Thể loại:Lý thuyết đồ thị