Beställd graf

En ordnad graf är en graf med en total ordning över dess noder.

I en ordnad graf är föräldrarna till en nod de noder som ligger intill den och föregår den i ordningen. Mer exakt $n$ en förälder till $m$ i den ordnade grafen $\langle N,E,<\rangle$ if $(n,m)\in E$ och $n<m$ . Bredden på en nod är numret på dess föräldrar, och bredden på en ordnad graf är den maximala bredden på dess noder.

Den inducerade grafen för en ordnad graf erhålls genom att lägga till några kanter till en beställningsgraf, med den metod som beskrivs nedan. Den inducerade bredden av en ordnad graf är bredden på dess inducerade graf.

Givet en ordnad graf är dess inducerade graf en annan ordnad graf som erhålls genom att sammanfoga några par av noder som båda är föräldrar till en annan nod. I synnerhet betraktas noder i tur och ordning enligt beställningen, från sista till första. För varje nod, om två av dess föräldrar inte är sammanfogade av en kant, läggs den kanten till. Med andra ord, när man överväger nod $n$ , om både $m$ och $l$ är föräldrar till den och inte är sammanfogade av en kant, kanten ${\ displaystyle (m,l)}$ läggs till i grafen. Eftersom föräldrarna till en nod alltid är förbundna med varandra, är den inducerade grafen alltid ackordal .

Som ett exempel beräknas den inducerade grafen för en ordnad graf. Ordningen representeras av positionen för dess noder i figurerna: a är den sista noden och d är den första.


Den ursprungliga grafen.	Edge lade till med tanke på föräldrarna till $a$	Edge lade till med tanke på föräldrarna till $b$

Nod $a$ betraktas först. Dess föräldrar är $b$ och $c$ , eftersom de båda är kopplade till $a$ och båda föregår $a$ i ordningen. Eftersom de inte är sammanfogade av en kant läggs en till.

Nod $b$ anses vara andra. Även om denna nod bara har $d$ som en förälder i den ursprungliga grafen, har den också $c$ som en förälder i den delvis byggda inducerade grafen. I själva verket ${\displaystyle c}$ kopplat till $b$ och föregår även $b$ i ordningen. Som ett resultat läggs en kant som förenar $c$ och ${\displaystyle d} till.$

Att betrakta $d$ ger ingen förändring, eftersom denna nod inte har några föräldrar.

Bearbetning av noder i ordning spelar roll, eftersom de införda kanterna kan skapa nya föräldrar, som sedan är relevanta för införandet av nya kanter. Följande exempel visar att en annan ordning ger en annan inducerad graf av samma ursprungliga graf. Ordningen är densamma som ovan men $b$ och $c$ byts om.


Samma graf, men ordningen för $b$ och $c$ byts	Graf efter att ha övervägt $a$

Som i föregående fall är både $b$ och ${\displaystyle c} föräldrar till$ $a$ . Därför läggs en kant mellan dem. Enligt den nya ordningen är den andra noden som övervägs $c$ . Denna nod har bara en förälder ( ${\displaystyle b} )$ . Därför läggs ingen ny kant till. Den tredje betraktade noden är $b$ . Dess enda förälder är $d$ . Faktum är att $b$ och $c$ inte är sammanfogade denna gång. Som ett resultat introduceras ingen ny kant. Eftersom $d$ inte heller har någon förälder, är den slutliga inducerade grafen den ovan. Denna inducerade graf skiljer sig från den som producerades av föregående beställning.

Se även

Dechter, Rina (2003). Constraint Processing . Morgan Kaufmann. ISBN 1-55860-890-7