Obsah
- Definice - Co znamená bipartitní graf?
- Úvod do Microsoft Azure a Microsoft Cloud | V této příručce se dozvíte, o čem cloud computing je a jak vám může Microsoft Azure pomoci migrovat a řídit podnikání z cloudu.
- Techopedia vysvětluje bipartitní graf
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 rámci stejné sady 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.
Úvod do Microsoft Azure a Microsoft Cloud | V této příručce se dozvíte, o čem cloud computing je a jak vám může Microsoft Azure pomoci migrovat a řídit podnikání z cloudu.
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í schopné 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ů.