Kétrészes gráf

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. október 4-én felülvizsgált verziótól ; az ellenőrzések 12 szerkesztést igényelnek .

A kétrészes gráf vagy bigráf a gráfelméletben olyan gráf, amelynek csúcskészlete két részre osztható úgy, hogy a gráf minden éle összeköti az egyik rész egyik csúcsát a másik rész valamelyik csúcsával, azaz vannak ugyanazon gráfrészek csúcsai között nincsenek élek.

Definíció

Egy irányítatlan gráfot bipartitnak nevezünk, ha a csúcsok halmaza két részre osztható úgy, hogy: $G=(W,E)$ $U\cup V=W$

egyetlen in csúcs sem kapcsolódik az in csúcsokhoz $U$ $U$
egyetlen in csúcs sem kapcsolódik az in csúcsokhoz $V$ $V$

Ebben az esetben a és csúcsok részhalmazait egy kétrészes gráf részeinek nevezzük . $U$ $V$ $G$

Kapcsolódó definíciók

A bipartit gráfot teljes bipartit gráfnak nevezzük (ez a fogalom különbözik a teljes gráftól , vagyis attól, amelyben minden csúcspárt egy él köt össze), ha minden csúcspárhoz van egy él . Mert $u\in U,v\in V$ $(u,v)\in E$

|U|=i,|V|=j

egy ilyen gráfot a szimbólummal jelölünk . $K_{{i,j}}$

Példák

Bipartit gráfok természetesen akkor keletkeznek, amikor két különböző objektumosztály közötti kapcsolatokat modelleznek. Például a futballisták és klubok grafikonja: egy él köti össze a megfelelő játékost és a klubot, ha a játékos ebben a klubban játszott. További absztrakt példák kétoldalú gráfokra:

fa .
Egy egyszerű ciklus, amely páros számú csúcsból áll.
Bármely síkgráf , amelynek minden lapját páros számú él határolja.

Az LDPC kódok leírására kétrészes gráfokat használnak .

Tulajdonságok

Egy gráf akkor és csak akkor bipartit, ha nem tartalmaz páratlan hosszúságú ciklust .
- Egy kétrészes gráf nem tartalmazhat 2-nél nagyobb klikket .
Egy gráf akkor és csak akkor bipartit, ha 2-kromatikus; azaz kromatikus száma kettő.
A gráf akkor és csak akkor particionál többszínű csúcspárokra, ha az egyik megosztás bármely eleme legalább a másik elemeihez kapcsolódik ( Esküvői tétel ). $k$ $k$
Egy teljes kétrészes gráf, amelynek mindegyik részében több mint 2 csúcs található, nem síkbeli .
Bármely bipartit gráf tökéletes .

Bipartit ellenőrzése

A gráf kétrészességének ellenőrzéséhez elegendő minden egyes összekapcsolt komponensben kiválasztani egy tetszőleges csúcsot, és a gráf bejárása során (például szélesség-első kereséssel ) felváltva párosként és páratlanként megjelölni a fennmaradó csúcsokat (lásd az ábrát). . Ha nincs ütközés, akkor minden páros csúcs alkotja a halmazt , és minden páratlan csúcs alkotja . $U$ $V$

Alkalmazások

Petri hálók
Levy gróf
Kódoláselmélet
- tényező gráf
- Tanner grófja