Kaksiosainen kaavio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4.10.2020 tarkistetusta versiosta . tarkastukset vaativat 12 muokkausta .

Kaksiosainen graafi tai bigraafi graafiteoriassa on graafi , jonka kärkijoukko voidaan jakaa kahteen osaan siten, että graafin jokainen reuna yhdistää yhdestä osasta peräisin olevan kärjen toisen osan johonkin kärkeen, eli ei reunoja samojen graafiosien kärkien välillä.

Määritelmä

Suuntaamatonta graafia kutsutaan kaksiosaiseksi, jos sen kärkijoukko voidaan jakaa kahteen osaan siten, että: $G=(W,E)$ $U\cup V=W$

yksikään kärki in ei ole yhteydessä pisteisiin in $U$ $U$
yksikään kärki in ei ole yhteydessä pisteisiin in $V$ $V$

Tässä tapauksessa kärkipisteiden ja osajoukkoja kutsutaan kaksiosaisen graafin osiksi . $U$ $V$ $G$

Aiheeseen liittyvät määritelmät

Kaksiosaista graafia kutsutaan täydelliseksi kaksiosaiseksi graafiksi (tämä käsite eroaa täydellisestä graafista , toisin sanoen sellaisesta, jossa jokainen pistepari on yhdistetty reunalla), jos kullekin pisteparille on reuna . varten $u\in U,v\in V$ $(u,v)\in E$

|U|=i,|V|=j

tällainen kaavio on merkitty symbolilla . $K_{{i,j}}$

Esimerkkejä

Kaksiosaiset graafit syntyvät luonnollisesti, kun mallinnetaan kahden eri objektiluokan välisiä suhteita. Esimerkiksi jalkapalloilijoiden ja seurojen kuvaaja: reuna yhdistää vastaavan pelaajan ja seuran, jos pelaaja pelasi tässä seurassa. Lisää abstrakteja esimerkkejä kaksiosaisista kaavioista:

Puu .
Yksinkertainen sykli, joka koostuu parillisesta määrästä pisteitä.
Mikä tahansa tasograafi, jonka jokainen pinta on rajattu parillisella määrällä reunoja.

Kaksiosaisia kaavioita käytetään kuvaamaan LDPC - koodeja.

Ominaisuudet

Graafi on kaksiosainen silloin ja vain, jos se ei sisällä parittoman pituista sykliä .
- Erityisesti kaksiosainen graafi ei voi sisältää klikkausta , jonka koko on suurempi kuin 2.
Graafi on kaksiosainen silloin ja vain, jos se on 2-kromaattinen; eli sen kromaattinen luku on kaksi.
Graafi ositetaan moniväristen kärkien pareiksi, jos ja vain, jos jommankumman osuuden elementit ovat yhteydessä ainakin toisen osakkeen elementteihin ( Häälause ). $k$ $k$
Täydellinen kaksiosainen graafi, jossa on enemmän kuin 2 kärkeä kussakin osassa, ei ole tasomainen .
Mikä tahansa kaksiosainen graafi on täydellinen .

Tarkistetaan kaksiosaista

Graafin kaksiosaisuuden tarkistamiseksi riittää, että valitaan mikä tahansa kärki jokaisessa yhdistetyssä komponentissa ja merkitään loput pisteet graafin läpikäynnin aikana (esimerkiksi leveyshaulla ) vuorotellen parillisiksi ja parittomiksi (katso kuva). . Jos ristiriitaa ei ole, kaikki parilliset kärjet muodostavat joukon ja kaikki parittomat kärjet . $U$ $V$

Sovellukset

Petrin verkot
Kreivi Levy
Koodauksen teoria
- tekijäkaavio
- Earl of Tanner