Bipartitionien ymmärtäminen graafiteoriassa
Graafiteoriassa graafin bipartitio on sen kärkijoukon jakaminen kahdeksi disjunktijoukoksi (kutsutaan osajoukoiksi) siten, että kaikki reunat yhdistävät pisteitä eri osiojoukoista. Toisin sanoen, saman osajoukon kärkien välillä ei ole kulmia.
Otetaan esimerkiksi graafi, jossa on 4 kärkeä {a,b,c,d} ja jaamme kärkijoukon kahteen osaan: {a,b} ja {CD}. Graafi on kaksiosainen, koska kaikki reunat yhdistävät pisteitä eri osista.
Bipartition avulla voidaan vähentää algoritmien monimutkaisuutta graafiongelmissa, kuten graafin läpikulku, lyhimmän polun etsiminen ja graafin sovitus.
Tykkään tästä
En tykkää tästä
Ilmoita sisältövirheestä
Osake
