Frakční shoda - Fractional matching

v teorie grafů, a zlomková shoda je zobecněním a vhodný ve kterém lze intuitivně každý vrchol rozdělit na zlomky, které se shodují s různými sousedními vrcholy.

Definice

Vzhledem k graf G = (PROTI, E), zlomková shoda v G je funkce, která přiřadí každé hraně E v E, frakce F(E) v [0, 1], takže pro každý vrchol proti v PROTI, součet zlomků hran sousedících s proti je maximálně 1:^[1]

Shoda v tradičním smyslu je speciální případ zlomkové shody, ve které je zlomek každé hrany buď 0 nebo 1: F(E) = 1 pokud E je ve shodě a F(E) = 0, pokud není. Z tohoto důvodu se v kontextu zlomkových shody někdy nazývají obvyklé shody integrální párování.

Velikost integrálního párování je počet hran v párování a odpovídající číslo ${ displaystyle nu (G)}$ grafu G je největší velikost odpovídající v G. Analogicky velikost zlomkové shody je součet zlomků všech hran. The zlomkové odpovídající číslo grafu G je největší velikost zlomkové shody v G. To je často označováno ${ displaystyle nu ^ {*} (G)}$.^[2] Protože shoda je speciální případ zlomkové shody, pro každý graf G jeden má ten integrální odpovídající počet G je menší nebo rovno zlomkovému shodnému počtu G; v symbolech:

Graf, ve kterém ${ displaystyle nu (G) = nu ^ {*} (G)}$ se nazývá a stabilní graf.^[3] Každý bipartitní graf je stabilní; to znamená, že v každém bipartitním grafu je zlomkové shodné číslo celé číslo a rovná se integrální shodnému číslu.

V obecném grafu ${ displaystyle nu (G)> { frac {2} {3}} nu ^ {*} (G).}$ Částečné shodné číslo je celé číslo nebo poloviční celé číslo. ^[4]

Maticová prezentace

Pro bipartitní graf G = (X+Y, E) lze zlomkovou shodu prezentovat jako matici s |X| řádky a |Y| sloupce. Hodnota položky v řádku X a sloupec y je hmotnost na hraně (X,y).

Perfektní dílčí shoda

Frakční shoda se nazývá perfektní pokud je součet vah sousedících s každým vrcholem přesně 1. Velikost dokonalého párování je přesně |PROTI|/2.

V bipartitní graf G = (X+Y, E), nazývá se zlomková shoda X-perfektní pokud je součet hmotností sousedících s každým vrcholem X je přesně 1. Velikost X-perfektní zlomková shoda je přesně |X|.

Pro bipartitní graf G = (X+Y, E), ekvivalentní jsou následující:

• G připouští X- perfektní integrální shoda,
• G připouští X-dokonalé zlomkové shody a
• G splňuje podmínku Hallova věta o manželství.

První podmínka implikuje druhou, protože integrální shoda je zlomková shoda. Druhá implikuje třetí, protože pro každou podmnožinu Ž z X, součet hmotností poblíž vrcholů Ž je |Ž|, takže hrany sousedící s nimi nutně sousedí alespoň s |Ž| vrcholy Y. Podle Hallova věta o manželství, poslední podmínka implikuje první.^{[5][je zapotřebí lepší zdroj ]}

Algoritmické aspekty

Největší zlomkovou shodu v grafu lze snadno najít podle lineární programování, nebo alternativně a algoritmus maximálního toku. V bipartitním grafu je možné převést maximální frakční shodu na maximální integrální shodu stejné velikosti. To vede k jednoduchému algoritmu polynomiálního času pro nalezení maximální shody v bipartitním grafu.^[6]

Li G je bipartitní graf s |X| = |Y| = n, a M je dokonalá zlomková shoda, pak maticová reprezentace M je dvojnásobně stochastická matice - součet prvků v každém řádku a každém sloupci je 1. Birkhoffův algoritmus lze použít k rozložení matice maximálně na konvexní součet n²-2n+2 permutační matice. To odpovídá rozkladu M na konvexní součet maximálně n²-2n+2 perfektní shody.

Frakční odpovídající polytop

Daný graf G = (PROTI,E), frakční odpovídající mnohostěn z G je konvexní mnohostěn který představuje všechny možné zlomkové shody G. Je to polytop v R^|E| - |E| -dimenzionální euklidovský prostor. Každý bod (X₁,...,X_{| E |}) v mnohostěnu představuje shodu, ve které váha každého okraje E je X_E. Mnohostěn je definován |E| omezení negativity (X_E ≥ 0 pro všechny E v E) a |PROTI| omezení vrcholů (součet X_E, pro všechny hrany E které sousedí s vrcholem proti, je maximálně 1).

Reference

Viz také

• Frakční zbarvení