Съдържание:
Определение - Какво означава Bipartite Graph?
Двустранен график е графика, в която набор от графични върхове може да бъде разделен на два независими множества, а няма две графични върхове в рамките на един и същи набор. С други думи, двустранните графики могат да се считат за равни на две цветни графики. Бипартитовите графики се използват най-вече при моделиране на връзки, особено между два цели отделни класа обект.
Двустранен график е известен също като биграф.
Техопедия обяснява Бипартитна графика
Двустранен график има два набора от върхове, например A и B, с възможност, че когато е начертан ръб, връзката трябва да може да се свързва между всеки връх в A с който и да е връх в B. Ако графиката не съдържа нечетен цикъл (броят на върховете в графиката е нечетен), тогава спектърът му е симетричен. Хроматичното число, което е минималният брой цветове, необходими за оцветяване на върховете без съседни върхове, споделящи едни и същи цветове, трябва да бъде по-малък или равен на два в случай на двустранен график. Всички видове ациклични графики (графики, които нямат цикли на графиката), са примери за двучастични графики. Цикличната графика се счита за двустранна, ако всички включени цикли са с равномерна дължина. Според теоремата за оцветяване на линията на Конинг всички двучастични графики са графики от клас 1.
Бипартитовите графики са широко използвани в съвременната теория на кодирането, освен че се използват при моделиране на връзки.
