bipartiteistä

Bipartiteistä viittaa graph theory -käsitteeseen liittyvään bipartiteihin rakenteisiin, erityisesti bipartiteihin grafiikoihin. Suomenkielessä termiä käytetään yleisesti kuvaamaan kaksijakoisuutta grafissa siten, että kaikki solmujen reunat yhdistävät kahden erillisen osajoukon solmuja. Toisin sanoen grafi määritellään siten, että Solmujoukkoja voidaan merkitä U ja V, joille pätee V = U ∪ V, U ∩ V = ∅ ja jokainen reuna kytkee solmun jostakin U:sta toiseen osajoukkoon V:stä.

Yksi keskeisistä tuntomerkistä on, että pienen grafien ei koskaan muodostuulgod käyrien sisäisiä reunoja, eli ganska kaikki (odd cycles) muodostuu vain, jos grafi ei ole bipartiteinen. Tämän voi havaita myös siten, että grafi voidaan värjätä kahdella eri värillä siten, että naapurisolmut saavat samanvärisenä eri väri. Lisäksi adjacency-matriisi voidaan esittää lohkoformaattina, jonka avulla voidaan permutoida solmujen järjestys siten, että reunat kulkevat vain lohkojen U ja V välillä.

Esimerkkejä bipartiteisista grafiikoista ovat puut (kuten starit ja ketjut), sekä jopa suljetutkin säännölliset even-kierrot. Käytännössä bipartiteiset grafit ovat keskeisiä esimerkiksi tehtäväyhdistämisissä (matching), verkkojen virtaratkaisuissa ja resurssien jako -ongelmissa. Tietoteoreettisesti tärkeitä teoreemoja ovat Hallin ehtolause ja Königin teoreema, jotka liittyvät täydellisiin löytämis- ja pienin kattaviin ratkaisuun bipartiteisissa verkoissa sekä maksimaalisten yhdistelmien ja pienimpien kattavuuksien välisiin suhteisiin.

Bipartiteistä käsite on yleisesti käytetty sekä teoreettisessa että soveltavassa kontekstissa ja se esiintyy laajasti algoritmeissa ja verkostojen mallinnuksessa.