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.[ 1]
Cho
G
=
(
X
,
E
)
{\displaystyle G=(X,E)}
X
1
{\displaystyle X_{1}}
X
2
{\displaystyle X_{2}}
X
{\displaystyle X}
X
1
{\displaystyle X_{1}}
≠
{\displaystyle \neq }
≠
{\displaystyle \neq }
X
2
{\displaystyle X_{2}}
X
1
{\displaystyle X_{1}}
⋂
{\displaystyle \bigcap }
X
2
{\displaystyle X_{2}}
G
{\displaystyle G}
* Với mọi cặp đỉnh(i,j) mà i
∈
{\displaystyle \in }
X
1
{\displaystyle X_{1}}
∈
{\displaystyle \in }
X
2
{\displaystyle X_{2}}
Mối tương quan giữa đồ thị đầy đủ và đồ thị hai phía đầy đủ:[ 2] * Đồ thị đầy đủ
K
n
{\displaystyle K_{n}}
n
.
(
n
−
1
)
2
{\displaystyle {\cfrac {n.(n-1)}{2}}}
K
m
,
n
{\displaystyle K_{m,n}}
Kn; Km,n
Với mọi k,
K
1
,
k
{\displaystyle K_{1,k}}
[ 3] Đồ Thị Hình Sao1 Hay với đồ thị
K
1
,
k
{\displaystyle K_{1,k}}
một cây Đồ Thị Claw hay Tree
K
m
,
n
{\displaystyle K_{m,n}}
Đồ thị hai phía đầy đủ Km,n
K
m
,
n
{\displaystyle K_{m,n}}
Đồ Thị Lưỡng Phân Knn
Định lý Kuratowski [ 4] [ 5]
K
3
,
3
{\displaystyle K_{3,3}}
K
5
{\displaystyle K_{5}}
K
3
,
3
{\displaystyle K_{3,3}}
K
3
,
3
{\displaystyle K_{3,3}}
K3,3 và K5 Một đồ thị hai phía đầy đủ
K
m
,
n
{\displaystyle K_{m,n}}
min
{
m
,
n
}
{\displaystyle \min \lbrace m,n\rbrace }
max
{
m
,
n
}
{\displaystyle \max \lbrace m,n\rbrace }
Đồ thị hai phía đầy đủ
K
4
,
4
{\displaystyle K_{4,4}}
[ 6]
Một đồ thị đủ
K
n
{\displaystyle K_{n}}
H
1
{\displaystyle H_{1}}
H
2
{\displaystyle H_{2}}
H
3
{\displaystyle H_{3}}
H
m
{\displaystyle H_{m}}
m
≥
n
−
1
{\displaystyle m\geq \;n-1}
[ 7] K5 to 4cbg Đồ thị hai phía đầy đủ
K
m
,
n
{\displaystyle K_{m,n}}
n
<
m
m
{\displaystyle n<\;m^{m}}
[ 8] Một đồ thị hai phía đầy đủ
K
m
,
n
{\displaystyle K_{m,n}}
min
{
m
,
n
}
{\displaystyle \min \lbrace m,n\rbrace }
Một đồ thị hai phía đầy đủ
K
n
,
n
{\displaystyle K_{n,n}}
K
n
,
n
+
1
{\displaystyle K_{n,n+1}}
[ 9]
Một đồ thị hai phía đầy đủ
K
m
,
n
{\displaystyle K_{m,n}}
m n −1n m −1cây bao trùm
Ma trận Laplace của đồ thị hai phía đầy đủ
K
m
,
n
{\displaystyle K_{m,n}}
Một đồ thị hai phía đầy đủ
K
n
,
n
{\displaystyle K_{n,n}}
[ 10] Sắc số của đồ thị
K
m
,
n
{\displaystyle K_{m,n}}
[ 11] Số màu cần thiết để tô màu các cạnh của
K
m
,
n
{\displaystyle K_{m,n}}
Đường kính của đồ thị hai phía đầy đủ:
K
1
,
1
{\displaystyle K_{1,1}}
K
m
,
n
{\displaystyle K_{m,n}}
[ 12]
^ Bondy, John Adrian ; Murty, U. S. R. (1976), Graph Theory with Applications ISBN 0-444-19451-7 Bản gốc lưu trữ ngày 13 tháng 4 năm 2010, truy cập ngày 5 tháng 5 năm 2013 ^ Aigner, M. ; Ziegler, G.M. (2010), Proofs from the Book ISBN 9783642010378 ^ Kubale, M. (2004), Graph colorings ISBN 9780821834589 ^ Tutte, W. T. (1963), “How to draw a graph”, Proceedings of the London Mathematical Society , Third Series, 13 : 743–767, MR 0158387 ^ Kuratowski, Kazimierz (1930), “Sur le problème des courbes gauches en topologie” (PDF) , Fund. Math. (bằng tiếng Pháp), 15 : 271–283^ Knauer, Ulrich. Algebraic Graph Theory: Morphisms, Monoids and Matrices. Vol. 41. De Gruyter, 2011. Page 270
^ Aigner, M. ; Ziegler, G.M. (2010), Proofs from the Book ISBN 9783642010378 ^ Kubale, M. (2004), Graph colorings ISBN 9780821834589 ^ Reinhard Diestel . Graph Theory [1] ^ Alon, Noga (2003), “A simple algorithm for edge-coloring bipartite multigraphs”, Information Processing Letters , 85 (6): 301–302, doi :10.1016/S0020-0190(02)00446-5 , MR 1956451 ^ Jimmy Salvatore. (2007), Bipartite Graphs and Problem Solving, ngày 8 tháng 8 năm 2007 , University of Chicago [2] ^ Fogiel, M. (1984), The Finite and Discrete Mathematics Problem Solver ISBN 9780878915590
