Зміст:
Визначення - Що означає Біпартітний графік?
Двосторонній графік - це графік, у якому набір вершин графів може бути розділений на два незалежні множини, а жодні дві вершини графіка в межах одного набору не є суміжними. Іншими словами, двосторонні графіки можна вважати рівними двом кольоровим графам. Біпартітні графіки в основному використовуються при моделюванні відносин, особливо між двома цілими окремими класами об'єкта.
Двосторонній графік також відомий як біграф.
Техопедія пояснює біпартитовий графік
Двосторонній графік має два набори вершин, наприклад, A і B, з можливістю, що коли намальовано ребро, з'єднання повинне бути здатне з'єднуватися між будь-якою вершиною в A до будь-якою вершиною в B. Якщо графік не містить жодної непарний цикл (кількість вершин на графіку непарна), то його спектр симетричний. Хроматичне число, яке є мінімальною кількістю кольорів, необхідних для забарвлення вершин, без суміжних вершин, що мають однакові кольори, у випадку двоскладового графа має бути меншим або рівним двом. Усі типи ациклічних графіків (графіки, які не мають циклів графіків), є прикладами двопартійних графіків. Циклічний графік вважається двостороннім, якщо всі задіяні цикли мають рівну довжину. Відповідно до теореми фарбування ліній Конінга, всі двопартійні графіки є графами 1 класу.
Біпартитові графіки широко використовуються в сучасній теорії кодування, крім того, що використовуються при моделюванні відносин.
