Todelt graf

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 4. oktober 2020; checks kræver 12 redigeringer .

En todelt graf eller bigraf i grafteori er en graf, hvis sæt af toppunkter kan opdeles i to dele på en sådan måde, at hver kant af grafen forbinder et toppunkt fra den ene del med et eller andet toppunkt på den anden del, dvs. ingen kanter mellem hjørnerne af de samme grafdele.

Definition

En urettet graf kaldes todelt, hvis mængden af dens hjørner kan opdeles i to dele , således at: $G=(W,E)$ $U\kop V=W$

ingen toppunkt i er forbundet med toppunkter i $U$ $U$
ingen toppunkt i er forbundet med toppunkter i $V$ $V$

I dette tilfælde kaldes delmængder af toppunkter og dele af en todelt graf . $U$ $V$ $G$

Relaterede definitioner

En todelt graf kaldes en komplet todelt graf (dette koncept er forskelligt fra en komplet graf ; det vil sige en, hvor hvert par af hjørner er forbundet med en kant), hvis der er en kant for hvert par af hjørner . Til $u\i U,v\i V$ $(u,v)\i E$

|U|=i,|V|=j

sådan en graf er angivet med symbolet . $K_{{i,j}}$

Eksempler

Todelte grafer opstår naturligt, når man modellerer forhold mellem to forskellige klasser af objekter. For eksempel grafen over fodboldspillere og klubber: en kant forbinder den tilsvarende spiller og klubben, hvis spilleren spillede i denne klub. Flere abstrakte eksempler på todelte grafer:

Træ .
En simpel cyklus bestående af et lige antal hjørner.
Enhver plan graf, hvis hver side er afgrænset af et lige antal kanter.

Todelte grafer bruges til at beskrive LDPC- koder.

Egenskaber

En graf er todelt, hvis og kun hvis den ikke indeholder en cyklus af ulige længde.
- Især kan en todelt graf ikke indeholde en klike af størrelse større end 2.
En graf er todelt, hvis og kun hvis den er 2-kromatisk; det vil sige, dets kromatiske tal er to.
Grafen er opdelt i par af flerfarvede hjørner, hvis og kun hvis nogen af elementerne i en af andelene er forbundet i det mindste med elementer i den anden ( Bryllupssætning ). $k$ $k$
En komplet todelt graf med mere end 2 spidser i hver del er ikke -plan .
Enhver todelt graf er perfekt .

Kontrollerer for todelt

For at kontrollere grafen for todelthed er det nok at vælge et hvilket som helst toppunkt i hver tilsluttet komponent og markere de resterende toppunkter under gennemgangen af grafen (for eksempel ved bredde-først søgning ) skiftevis som lige og ulige (se illustration) . Hvis der ikke er nogen konflikt, danner alle lige knudepunkter sættet , og alle ulige knudepunkter dannes . $U$ $V$

Ansøgninger

Petri net
Grev Levy
Kodningsteori
- faktor graf
- Jarl af Tanner