Bipartíciók megértése a gráfelméletben
A gráfelméletben a gráf bipartíciója a csúcshalmaz két diszjunkt halmazra (az úgynevezett részhalmazokra) való felosztása úgy, hogy minden él összekapcsolja a különböző részhalmazokból származó csúcsokat. Más szóval, ugyanabban a részhalmazban nincsenek élek a csúcsok között.
Például vegyünk egy 4 csúcsú {a,b,c,d} gráfot, és a csúcshalmazt két részre osztjuk: {a,b} és {CD}. A gráf kétrészes, mivel minden él különböző részekből származó csúcsokat köt össze.
A kettéosztással csökkenthető az algoritmusok bonyolultsága olyan gráfproblémák esetén, mint a gráf bejárása, a legrövidebb út keresése és a gráfillesztés.
Ez tetszik
Ez nem tetszik
Tartalmi Hiba jelentése
Megosztás
