Tartalomjegyzék:
Meghatározás - Mit jelent a kétoldalú gráf?
A kétoldalú gráf egy olyan gráf, amelyben a gráfcsúcsok halmaza két független halmazra osztható, és ugyanazon halmazon belül nincs két gráfcsúcs szomszédos. Más szavakkal, a kétoldalú gráfok úgy tekinthetők, mint két színezhető gráf. A kétoldalú grafikonokat főként a kapcsolatok modellezésénél használják, különösen a két objektum teljes különálló osztálya között.
A kétoldalú gráfot bigraph néven is ismert.
A Techopedia magyarázza a kétoldalú grafikont
A kétoldalas gráfnak két csúcskészlete van, például A és B, azzal a lehetőséggel, hogy egy él húzásakor a kapcsolatnak képesnek kell lennie arra, hogy az A pontok bármelyik csúcsát összekapcsolja a B bármelyik csúcsával. Ha a grafikon nem tartalmaz páratlan ciklus (a csúcsok száma a grafikonon páratlan), akkor spektruma szimmetrikus. A kromatikus számnak, amely a csúcsok olyan színének minimális száma, amely nem igényli az azonos színű szomszédos csúcsok csúcsát, kétoldali grafikon esetén kettőnél kevesebbnek kell lennie. Az aciklusos gráfok minden típusa (olyan gráfok, amelyeknek nincsenek gráfciklusai) a kétoldalú gráfok példái. A ciklikus gráf kétpólusúnak tekinthető, ha az összes érintett ciklus egyenletes hosszúságú. Koning vonalszínező tétele szerint minden kétoldalas grafikon 1. osztályú grafikon.
A kétoldalú grafikonokat széles körben használják a modern kódolási elméletben, a kapcsolatok modellezése mellett.
