Đồ thị lưỡng cực là gì? - định nghĩa từ techopedia

Định nghĩa - Đồ thị Bipartite có nghĩa là gì?

Biểu đồ lưỡng cực là một biểu đồ trong đó một tập hợp các đỉnh biểu đồ có thể được chia thành hai tập độc lập và không có hai đỉnh biểu đồ trong cùng một tập hợp liền kề nhau. Nói cách khác, đồ thị lưỡng cực có thể được coi là bằng hai đồ thị có thể tô màu. Đồ thị lưỡng cực chủ yếu được sử dụng trong mô hình hóa các mối quan hệ, đặc biệt là giữa hai lớp đối tượng riêng biệt.

Một đồ thị lưỡng cực còn được gọi là một đồ thị lớn.

Techopedia giải thích đồ thị Bipartite

Một đồ thị lưỡng cực có hai bộ đỉnh, ví dụ A và B, với khả năng khi một cạnh được vẽ, kết nối sẽ có thể kết nối giữa bất kỳ đỉnh nào trong A với bất kỳ đỉnh nào trong B. Nếu đồ thị không chứa bất kỳ đỉnh nào trong B. chu kỳ lẻ (số đỉnh trong đồ thị là số lẻ), sau đó phổ của nó là đối xứng. Số màu, là số màu tối thiểu cần thiết để tô màu các đỉnh không có các đỉnh liền kề có cùng màu, cần nhỏ hơn hoặc bằng hai trong trường hợp đồ thị lưỡng cực. Tất cả các loại biểu đồ chu kỳ (biểu đồ không có chu kỳ biểu đồ), là ví dụ về biểu đồ lưỡng cực. Một đồ thị tuần hoàn được coi là lưỡng cực nếu tất cả các chu kỳ liên quan đều có độ dài bằng nhau. Theo định lý tô màu của Koning, tất cả các đồ thị lưỡng cực là đồ thị loại 1.

Đồ thị lưỡng cực được sử dụng rộng rãi trong lý thuyết mã hóa hiện đại ngoài việc được sử dụng trong các mối quan hệ mô hình hóa.