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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong ngành 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.

Cũng như đồ thị đầy đủ, đồ thị hai phía đầy đủ có các tính chất rất thú vị.

Mục lục

[sửa] Định nghĩa

Một đồ thị hai phía đầy đủ G:=(V_1 + V_2, E) là một đồ thị hai phía sao cho với mọi cặp hai đỉnh v_1 \in V_1v_2 \in V_2, v_1 v_2 là một cạnh của đồ thị G. Một đồ thị hai phía hoàn hảo với các phân hoạch có kích thước \|V_1\|=m\|V_2\|=n được ký hiệu K_{m,n}.

[sửa] Ví dụ

K3,1
K3,2
K3,3


[sửa] Tính chất

[sửa] Xem thêm

Công cụ cá nhân
Không gian tên

Biến thể
Tác vụ
Xem nhanh
Tương tác
Công cụ
In/xuất ra
Ngôn ngữ khác