Tvådelad graf

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 oktober 2020; kontroller kräver 12 redigeringar .

En tvådelad graf eller bigraf i grafteorin är en graf vars uppsättning av hörn kan delas i två delar på ett sådant sätt att varje kant på grafen förbinder en vertex från en del med någon vertex i den andra delen, det vill säga det finns inga kanter mellan hörnen på samma grafdelar.

Definition

En oriktad graf kallas bipartit om uppsättningen av dess hörn kan delas upp i två delar så att: $G=(W,E)$ $U\kopp V=W$

ingen vertex in är kopplad till hörn in $U$ $U$
ingen vertex in är kopplad till hörn in $V$ $V$

I det här fallet kallas delmängder av hörn och delar av en tvådelad graf . $U$ $V$ $G$

Relaterade definitioner

En tvådelad graf kallas en fullständig tvådelad graf (det här konceptet skiljer sig från en fullständig graf ; det vill säga en där varje par av hörn är förbundna med en kant) om det finns en kant för varje par av hörn . För $u\in U,v\in V$ $(u,v)\i E$

|U|=i,|V|=j

en sådan graf betecknas med symbolen . $K_{{i,j}}$

Exempel

Tvådelade grafer uppstår naturligt när man modellerar relationer mellan två olika klasser av objekt. Till exempel grafen över fotbollsspelare och klubbar: en kant förbinder motsvarande spelare och klubben om spelaren spelade i denna klubb. Fler abstrakta exempel på tvådelade grafer:

Träd .
En enkel cykel som består av ett jämnt antal hörn.
Varje plan graf vars varje yta begränsas av ett jämnt antal kanter.

Tvådelade grafer används för att beskriva LDPC- koder.

Egenskaper

En graf är tvådelad om och endast om den inte innehåller en cykel med udda längd.
- I synnerhet kan en tvådelad graf inte innehålla en klick som är större än 2.
En graf är tvådelad om och endast om den är 2-kromatisk; det vill säga dess kromatiska nummer är två.
Grafen är uppdelad i par av flerfärgade hörn om och endast om några element i en av delarna är sammankopplade åtminstone med element i den andra ( Bröllopssatsen ). $k$ $k$
En komplett tvådelad graf med mer än 2 hörn i varje del är icke- plan .
Alla tvådelade grafer är perfekta .

Söker efter tvådelad

För att kontrollera att grafen är tvådelad räcker det att välja valfritt hörn i varje ansluten komponent och markera de återstående hörnen under genomgången av grafen (till exempel genom sökning på bredden först ) växelvis som jämna och udda (se illustrationen) . Om det inte finns någon konflikt bildar alla jämna hörn mängden och alla udda hörn bildar . $U$ $V$

Applikationer

Petri nät
Greve Levy
Kodningsteori
- faktorgraf
- Earl av Tanner