Obsah:
Definícia - Čo znamená bipartitný graf?
Bipartitný graf je graf, v ktorom je možné množinu vrcholov grafu rozdeliť do dvoch nezávislých množín a žiadne dva vrcholy grafu v tej istej množine nie sú priľahlé. Inými slovami, bipartitné grafy sa môžu považovať za rovné dvom farebným grafom. Bipartitné grafy sa väčšinou používajú v modelovacích vzťahoch, najmä medzi dvoma celými samostatnými triedami objektov.
Dvojstranný graf je tiež známy ako bigraf.
Techopedia vysvetľuje bipartitný graf
Bipartitný graf má dve sady vrcholov, napríklad A a B, s možnosťou, že keď sa nakreslí hrana, spojenie by malo byť schopné spojiť sa s akýmkoľvek vrcholom v A s ktorýmkoľvek vrcholom v B. Ak graf neobsahuje žiadne nepárny cyklus (počet vrcholov v grafe je nepárny), potom je jeho spektrum symetrické. Chromatické číslo, ktoré predstavuje minimálny počet farieb potrebných na vyfarbenie vrcholov bez susedných vrcholov, ktoré zdieľajú rovnaké farby, musí byť v prípade dvojstranného grafu menšie alebo rovné dvom. Príklady bipartitných grafov sú všetky typy acyklických grafov (grafy, ktoré nemajú grafové cykly). Cyklický graf sa považuje za bipartit, ak všetky zúčastnené cykly majú rovnakú dĺžku. Podľa Koningovej vety o farbení čiar sú všetky bipartitné grafy grafy triedy 1.
Bipartitné grafy sa v modernej teórii kódovania široko používajú okrem toho, že sa používajú v modelovacích vzťahoch.
