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

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

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]

Định nghĩa[sửa | sửa mã nguồn]

Cho G =(X, E) là một đồ thị vô hướng lưỡng phân với hai tập X_1X_2 phân hoạch X (X_1  \ne Ø  \ne X_2X_1  \bigcup 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  \in  X_1 và j  \in  X_2 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 đủ:[2]
     * Đồ thị đầy đủ K_{n} có: n đỉnh,  \cfrac{n.(n-1)}{2}  cạnh
     * Đồ thị hai phía đầy đủ K_{m,n} có: m + n đỉnh, m.n cạnh
Kn; Km,n

Ví dụ[sửa | sửa mã nguồn]

  • Với mọi k, K_{1,k} ta có đồ thị hình sao.[3]
Đồ 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[sửa | sửa mã nguồn]

  • Định lý Kuratowski [4][5] 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 \min \lbrace m,n \rbrace và số phủ cạnh (Edge covering number) bằng \max\lbrace m,n\rbrace
  • Đồ thị hai phía đầy đủ K_{4,4} là một Cayley Graph.[6]
  • 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 \ge \; n - 1 [7]
K5 to 4cbg
  • Đồ thị hai phía đầy đủ K_{m,n} là k-choosable khi và chỉ khi  n < \; m^m [8]
  • 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 \min\lbrace m,n\rbrace
  • Một đồ thị hai phía đầy đủ K_{n,n} hay K_{n,n+1} là một đồ thị Turán.[9]
  • Một đồ thị hai phía đầy đủ K_{m,n}mn−1 nm−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.[10]
  • 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.[12]

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7 , page 5.
  2. ^ Aigner, M.; Ziegler, G.M. (2010), Proofs from the Book, Springer, ISBN 9783642010378 , page 66.
  3. ^ Kubale, M. (2004), Graph colorings, Amer Mathematical Society, ISBN 9780821834589 , page 3.
  4. ^ Tutte, W. T. (1963), “How to draw a graph”, Proceedings of the London Mathematical Society, Third Series 13: 743–767, MR 0158387 .
  5. ^ Kuratowski, Kazimierz (1930), “Sur le problème des courbes gauches en topologie”, Fund. Math. (bằng tiếng Pháp) 15: 271–283 .
  6. ^ Knauer, Ulrich. Algebraic Graph Theory: Morphisms, Monoids and Matrices. Vol. 41. De Gruyter, 2011. Page 270
  7. ^ Aigner, M.; Ziegler, G.M. (2010), Proofs from the Book, Springer, ISBN 9783642010378 , page 65.
  8. ^ Kubale, M. (2004), Graph colorings, Amer Mathematical Society, ISBN 9780821834589 , page 155.
  9. ^ Reinhard Diestel. Graph Theory, Electronic Edition 2005. © Springer - Verlag Heidelberg, New York 1997, 2000, 2005.[1]
  10. ^ 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 
  11. ^ Jimmy Salvatore. (2007), Bipartite Graphs and Problem Solving, August 8, 2007, University of Chicago  [2]
  12. ^ Fogiel, M. (1984), The Finite and Discrete Mathematics Problem Solver, Research and Education Association, ISBN 9780878915590 , page 269, 270.
Các chủ đề chính trong toán học
Nền tảng toán học | Đại số | Giải tích | Hình học | Lý thuyết số | Toán học rời rạc | Toán học ứng dụng |
Toán học giải trí | Toán học tô pô | Xác suất thống kê