Obsah:
Definice - Co znamená bipartitní graf?
Bipartitní graf je graf, ve kterém lze sadu vrcholů grafu rozdělit na dvě nezávislé sady a žádné dva vrcholy grafu v téže sadě nesousedí. Jinými slovy, bipartitní grafy lze považovat za rovné dvěma barevným grafům. Bipartitní grafy se většinou používají při modelování vztahů, zejména mezi dvěma celými samostatnými třídami objektů.
Dvoustranný graf je také známý jako bigraf.
Techopedia vysvětluje bipartitní graf
Dvoustranný graf má dvě sady vrcholů, například A a B, s možností, že když je hrana nakreslena, mělo by být spojení schopno spojit jakýkoli vrchol v A s jakýmkoli vrcholem v B. Pokud graf neobsahuje žádný lichý cyklus (počet vrcholů v grafu je lichý), potom je jeho spektrum symetrické. Chromatické číslo, což je minimální počet barev potřebných k zabarvení vrcholů bez sousedních vrcholů sdílejících stejné barvy, musí být v případě bipartitního grafu menší nebo rovno dvěma. Příkladem bipartitních grafů jsou všechny typy acyklických grafů (grafy, které nemají grafové cykly). Cyklický graf je považován za bipartit, pokud všechny zúčastněné cykly mají stejnou délku. Podle Koningovy věty o barvení čar jsou všechny bipartitní grafy grafy třídy 1.
Bipartitní grafy jsou široce používány v moderní teorii kódování, kromě toho, že se používají v modelování vztahů.
