Sisällysluettelo:
Määritelmä - mitä kaksiosainen kuvaaja tarkoittaa?
Kaksiosainen kuvaaja on kuvaaja, jossa joukko kuvaajapisteitä voidaan jakaa kahteen riippumattomaan joukkoon, eikä samassa ryhmässä ole kahta kuvaajapistettä vieressä. Toisin sanoen kaksiosaisia kuvaajia voidaan pitää yhtä suurena kuin kahdessa värjättävässä kuvaajassa. Kaksipuolisia kuvaajia käytetään enimmäkseen suhteiden mallinnuksessa, etenkin kahden kokonaisen erillisen objektiluokan välillä.
Kaksipuolinen kuvaaja tunnetaan myös nimellä bigraph.
Techopedia selittää kaksisuuntaisen graafin
Kaksipuolisessa kuvaajassa on kaksi kärkikomplektia, esimerkiksi A ja B, sillä mahdollisuudella, että kun reunaa piirretään, yhteyden pitäisi pystyä yhdistämään minkä tahansa A: n kärkipisteen mihin tahansa B: n kärkeen. Jos kuvaaja ei sisällä yhtään pariton jakso (graafin pisteiden lukumäärä on pariton), sen spektri on symmetrinen. Kromaattisen lukumäärän, joka on vähimmäismäärä värien määrää, jota tarvitaan sellaisten kärkien värittämiseen, joissa vierekkäisillä kärkillä ei ole samoja värejä, on oltava pienempi tai yhtä suuri kuin kaksi, jos kyseessä on kaksiosainen kuvaaja. Kaikki tyypit asykliset kuvaajat (kuvaajat, joilla ei ole kuvaajajaksoja) ovat esimerkkejä kaksiosaisista kuvaajista. Syklistä kuvaajaa pidetään kaksiosaisena, jos kaikki osallistuvat syklit ovat pituudeltaan tasaisia. Koningin linjavärityslauseen mukaan kaikki kaksipuoliset kuvaajat ovat luokan 1 kuvaajia.
Kaksipuolisia kuvaajia käytetään laajasti nykyaikaisessa koodausteoriassa lukuun ottamatta niitä, joita käytetään suhteiden mallintamisessa.
