Struktúratételek a párosításelméletben

Írta: Tóth Ádám V. matematikus Témavezető: Dr. Szegő László tanársegéd

2003. június 17.

Tartalomjegyzék

1. Bevezetés 3

2. Maximális párosítások és a Gallai–Edmonds-féle struktúratétel 3 2.1. Gallai–Edmonds-féle struktúratétel . . . . . . . . . . . . . . . 3 2.2. A Gallai–Edmonds-struktúratétel következményei . . . . . . . 5

3. Lovász párosítási algoritmusa 6

4. Törtpárosítások és 2-párosítások 7

4.1. A maximális törtpárosítás keresésének visszavezetése a maxi-

mális párosítás problémájára . . . . . . . . . . . . . . . . . . . 8 4.2. Az U-párosítások. Pulleyblank struktúratétele . . . . . . . . . 8 4.3. A struktúratétel következményei. A törtpárosításokra vonat-

kozó minimax tételek . . . . . . . . . . . . . . . . . . . . . . . 10

5. f-párosítások és f-faktorok 11

5.1. A maximális f-párosítások és f-faktorok keresésének vissza-

vezetése a maximális párosítási problémára . . . . . . . . . . . 11 5.2. Az f-faktorok struktúratétele . . . . . . . . . . . . . . . . . . 12

6. f-törtpárosítások és 2f-párosítások 18

1. Bevezetés

Dolgozatomban a párosításelmélet legfontosabb struktúratételeit veszem számba.

A második fejezetben ismertetem Gallai és Edmonds struktúratételének Lovásztól származó bizonyítását. A tétel szokásos, tanult bizonyítása Edmonds párosítási algoritmusán alapszik [8]. Itt azt fogjuk megvizsgálni, hogy mi történik, ha a Gallai–Edmonds-felbontás egyik részéből csúcsokat hagyunk el. A struktúratétel következményeképp számos, korábbról ismert párosításelméleti eredmény adódik, például Tutte tétele és a Berge–Tutte formula. Ezután ismertetem Lovász maximális párosítást keeső algoritmusát, amely a struktúratételre alapul.

A harmadik fejezetben a törtpárosításokat ismertetem. A maximális törtpárosítások nagyságának meghatározása önmagában igen egyszerű, mert a probléma visszavezethető egy páros gráfbeli maximális párosítás keresésére. Így azonban a maximális törtpárosítások szerkezetére nem derül fény. Ismertetjük Pulleyblank struktúratételét, amely az U-párosításokat (azon maximális párosításokat, amelyek törtrésze tartalmazásra nézve minimális) jellemzi. A tétel a Gallai–Edmonds-struktúratételen alapszik és számos, maximális törtpárosítokra vonatkozó eredmény következik belőle.

A negyedik fejezetben a párosítások egy általánosítását, az f-faktorokat jellemzem. Az f-faktorok létezésének problémája is visszavezethető a maximális párosítás problémájára. Tutte 1952-ből származó tétele választ ad arra, hogy mikor van a gráfban f-faktor. Ismertetjük Lovász f-faktorokról szóló struktúratételét, amelyből ez az eredmény azonnal következik.

Végezetül a maximális f-törtpárosításokat jellemzem.

Megköszönöm témavezetőmnek, Szegő Lászlónak a dolgozat írása közben nyújtott segítségét és tanácsait.

2. Maximális párosítások és a Gallai–Edmondsféle struktúratétel

A G gráfra M ⊆ E(G) párosítás, ha G minden pontját M legfeljebb egy éle fedi. Kérdés, hogy mekkora lehet a párosítás elemszáma. A G gráf maximális elemszámú párosításának méretét ν(G)-vel jelöljük. Ha a gráfban van teljes, vagyis minden pontot fedő páros tás, akkor ν(G) = |V (G)|/2. A gráf hiánya a fedetlen pontok minimális száma: def(G) = V (G) − 2ν(G) Maximális párosítás létezésére az alábbi jól ismert tétel ad szükséges és elégséges feltételt.

2.1. tétel. (Tutte-tétel) A G gráfban akkor és csak akkor létezik teljes párosítás, ha tetszőleges x ⊆ V (G)-re az X elhagyásával keletkező gráf páratlan kompnenseinek q(X) számára q(X) ≤ |X|.

A következő tétel pedig a maximális párosítás méretét adja meg.

2.2. tétel. A G gráfban a maximális párosítás mérete

ν(G) = max_{X⊆V (G)}(|V (G) − q(X) + |X|)/2

Ezek a tételek azonban nem szólnak arról, hogy milyen egy teljes párosítás. Az alábbiakban bebizonyítjuk Gallai és Edmonds tételét Ehhez először bevezetünk néhány definíciót

2.1. definíció. G faktorkritikus, ha bármely pontját elhagyva van teljes párosítása.

2.2. definíció. Majdnem teljes párosításnak nevezzük G olyan párosítását, mely egy pont kivételével G összes csúcsát lefedi.

2.1. Gallai–Edmonds-féle struktúratétel

Az alábbiakban ismertetjük Lovász bizonyítását a struktúratételre [1].

2.3. definíció. Legyen G = (V, E) gráf. Jelöljük D(G)-vel azon csúcsok halmazát, melyeket G legalább egy párosítása nem fed. Legyen A(G) azon V (G) − D(G)-beli csúcsok halmaza, melyek legalább egy D(G)-beli csúccsal szomszédosak. Végül legyen C(G) = V (G) − A(G) − D(G). A gráf ilyen módon való felosztását Gallai–Edmonds-felbontásnak nevezzük.

2.3. tétel. (Gallai–Edmonds-struktúratétel) Legyen G gráf és D(G), A(G), C(G) a fent definiált csúcshalmazok. Ekkor a következőket állíthatjuk.

(a) A D(G) által feszített részgráf komponensei faktorkritikusak

(b) A C(G) által feszített részgráfnak van teljes párosítása.

(c) Ha C(G) pontjait és az A(G) által feszített éleket kitöröljük, továbbá A(G) komponenseit egy-egy csúccsá húzzuk, akkor az így kapott páros gráfra teljesül a szigorú Hall-feltétel (az A(G) által meghatározott színosztályra nézve).

(d) Legyen M a G gráf egy tetszőleges párosítása. Ekkor M a D(G) rész minden komponensén majdnem teljes párosítást határoz meg, C(G) minden komponensén teljes párosítást határoz meg, és A(G) minden komponensét összepárosítja D(G) egy-egy, egymástól diszjunkt komponensével.

(e) ν(G) = \frac{1}{2} (|V (G)| − c(D(G)) + |A(G)|), ahol c(D(G)) a D(G) által feszített részgráf komponenseinek számát jelöli.

A tétel belátásához szükségünk van két fontos lemmára.

2.1. lemma. (Gallai-lemma) Legyen G olyan összefüggő gráf, melynek bármely pontját elhagyva ν(G) csökken. Ekkor G faktorkritikus.

Bizonyítás.

A második, úgynevezett stabilitási lemma arról szól, hogy hogyan változik a Gallai–Edmonds felbontás, ha az egyes csúcshalmazokból eltörlünk egy pontot. Valójában csak az (a) részt fogjuk használni, így csak azt bizonyítjuk.

2.2. lemma. (a) Legyen u ∈ A(G). Ekkor A(G−u) = A(G)−u, C(G−u) = C(G) és D(G − u) = D(G).

(b) Legyen u ∈ C(G). Ekkor A(G − u) ⊇ A(G), C(G − u) ⊆ C(G) − u és D(G − u) ⊇ D(G).

(c) Legyen u ∈ D(G). Ekkor A(G − u) ⊆ A(G), C(G − u) ⊇ C(G) és D(G − u) ⊆ D(G) − u

Bizonyítás. Nyilván elegendő belátni, hogy D(G − u) = D(G). Legyen M a G gráf egy maximális párosítása. Ekkor M lefedi u-t, hisz u ∉ D(G), így ν(G − u) = ν(G) − 1. Továbbá, G bármely N maximális párosítására N − u a G − u gráf egy maximális párosítása.

Először belátjuk, hogy D(G) ⊆ D(G − u). Ehhez válasszunk egy v ∈ D(G) csúcsot. Legyen M_{v} a G gráf egy v-t elkerülő maximális párosítása. Ekkor a fenti megállapítás szerint M_{v}−u maximális párosítása lesz G−u-nak. M_{v} − u elkerüli v-t, így v ∈ D(G − u), tehát ezt a tartalmazást beláttuk.

A másik irányú tartalmazás igazolásához vegyünk egy v ∈ D(G − u) pontot. Ekkor van G − u-nak olyan M′ maximális párosítása, amely elkerüli v-t. Legyen w ∈ D(G) tetszőleges olyan pont, amely G-ben szomszédos uval, és legyen M G-nek egy w-t elkerülő maximális párosítása. Ha M elkerüli v-t, akkor v ∈ D(G) teljesül, tehát feltehetjük, hogy M fedi v-t. Vegyük a két párosítás unióját, M ∪ M′-t. Mivel M′ elkerüli v-t, M ∪ M′-nek a v-t fedő komponense egy olyan P alternáló út, amely v-nél M − M′-beli éllel kezdődik.

Tegyük fel most, hogy a P út utolsó éle M′-beli. Ekkor véve M és E(P) szimmetrikus differenciáját, egy olyan M′′ párosítást kapunk, amely elkerüli v-t, ráadásul |M′′| = |M|, tehát M′′ maximális párosítás és így v ∈ D(G).

A másik esetben a P út utolsó éle M − M′-beli, tegyük fel, hogy ez nem u-nál végződik. . Legyen M_{3} = M′△E(P), ekkor erre a párosításra |M_{3}| > |M′|, így M′ maximalitása miatt M_{3} ⊈ E(G − u). Tehát P az u csúcsnál végződik. Vegyük az M△E(P + uw) párosítást, ez G-nek egy v-t elkerülő maximális párosítása lesz, tehát v ∈ D(G).

Most már bebizonyíthatjuk Gallai és Edmonds struktúratételét.

Bizonyítás. Töröljük ki egyesével a gráfból A (a továbbiakban nem írjuk ki, hogy a csúcshalmazok G-hez tartoznak) pontjait. Ekkor a stabilitási lemma (a) része miatt minden egyes kitörölt pont az A csúcshalmazhoz tartozik az aktuális gráfban és minden egyes lépésben eggyel csökken a párosítási szám, tehát

ν(G − A) = ν(G) − A  (1)

És persze

C(G − A) = C(G) és D(G − A) = D(G).  (2)

Legyen M a G gráf egy tetszőleges maximális párosítása, ekkor M ∩E(G−A) G − A-nak egy párosítása.

Jelöljük G_{1}, …, G_{t}-vel G − A D-ben fekvő komponenseit. Mivel D és C között nem mennek élek, az eredeti G gráfban a D által feszített gráfnak is ezek lesznek a komponensei. Legyen H a G gráfban a C által feszített részgráf.2 miatt G−A minden maximális párosítása lefedi H-t, D-nek viszont minden pontját elkerüli maximális párosítás. Így véve G − A egy maximális párosítását, ez H-n teljes párosítást határoz meg, a G_{i} komponenseken pedig egy-egy M_{i} majdnem teljes párosítást. Tehát H-nak van teljes párosítása, ezzel (b)-t beláttuk. Mivel G_{i} minden csúcsához van G_{i}-nek egy azt elkerülő maximális párosítása, így a Gallai-lemma miatt a G_{i} komponensek faktorkritikusak.

Most belátjuk (d)-t. Az M ∩ E(G − A) élhalmaz G − A maximális párosítását adja, ezért M ∩ E(H) teljes párosításű H-n, M ∩ (G_{i}) pedig G_{i}-n majdnem teljes párosítás. 2-ból azonnal következik, hogy |M ∩ E(G − A)| = |M|−|A|, és így M nem tartalmaz A által feszített élet. Mivel az M párosítás A minden pontját lefedi, így A összes pontját összeköti valamely G − A-beli ponttal. De A egyetlen pontját sem kötheti össze C(G)-beli ponttal, és A semelyik két pontját nem kötheti össze ugyanazzal a G_{i} komponenssel. Ezzel (d)-t beláttuk.

A (c) állítás megmutatásához be kell látnunk, hogy tetszőleges X ⊆ A részhalmaz legalább |X| + 1 darab G_{i} komponenssel szomszédos???. Mivel X ⊆ A, ezért legalább egy G_{i}-vel szomszédos, jelöljük az egyiket G_{h}-val. Vegyük ennek egy csúcsát, u-t, és vegyük G-nek egy ezt elkerülő M_{1} maximális párosítását. A tétel imént bizonyított (d) részéből következik, hogy az M_{1} párosítás X minden csúcsát különböző G_{i} komponenssel köti össze. Mivel M_{1} elkerüli u ∈ V (G_{h})-t és M ∩ E(G_{h}) a G_{h} gráf majdnem teljes párosítását adja, így az említett |X| számú G_{i} komponens egyike sem G_{h}, tehát X legalább |X| + 1 darab G_{i} komponenssel szomszédos, vagyis (c)-t beláttuk.

Végezetül (e) belátásához felhasználjuk a 1 egyenlőséget és az (a) és (b) állításokat:

\begin{aligned}ν(G) = ν(G − A) + |A| & = ∑_{i=1}^{t} \frac{|V (G_{i})| − 1}{2} + \frac{|C|}{2} + |A| \\ & = \frac{1}{2} (|V (G)| − c(D) + |A|) . \end{aligned}

2.2. A Gallai–Edmonds-struktúratétel következményei

A tételből számos következmény azonnal adódik. Ezeket a szokásos felépítésben a struktúratétel bizonyítása előtt látjuk be, itt azonban nem használjuk őket, így következményként szerepelhetnek.

Az (e) állításból azonnal következik, hogy G hiányára teljesül def(G) = c (D(G)) − |A(G)|, vagyis a hiány pont D(G) azon a komponenseinek a számával egyezik meg, amelyeket G egy tetszőleges maximális párosítása nem párosít össze A(G)-vel.

Tutte tételének nehéz iránya is azonnal következik a tételből. Tegyük fel ugyanis, hogy minden X ⊆ V (G)-re teljesül c_{0} (D(G)) ≤ |X|, ekkor A(G)- re is áll, hogy c_{0} (G − A(G)) ≤ |A(G)|. Ekkor ezt behelyettesítve az (e) egyenlőtlenségbe, azt kapjuk, hogy

ν(G) = \frac{1}{2} (|V (G)| − c (D(G)) + |A(G)|) ≥ \frac{1}{2}|V (G)|,

tehát G-nek van teljes párosítása. Hasonlóan kaphatjuk meg a Tutte–Bergeformula nemtriviális irányát is.

Ha G-nek nincs teljes párosítása, akkor minden, D(G) valamely pontjára illeszkedő él benne van maximális párosításban. Ez D(G) definíciójából következik. Legyen ugyanis uv egy ilyen él (u ∈ D(G)). Definíció szerint létezik olyan M maximális párosítás, amely elkerüli u-t. M maximalitása folytán van M-ben egy v-t fedő vw él. De ekkor M − vw + uv éppen megfelelő párosítás.

Másrészt az tétel (d) részéből az is következik, hogy semelyik A(G) által feszített vagy A(G) és C(G) között menő él nincs benne maximális párosításban.

Ha G faktorkritikus, akkor a Gallai–Edmonds-felbontás egy elfajult esetével állunk szemben: D(G) = V (G) és A(G) = C(G) = ∅.

Ha G-nek van teljes párosítása, akkor egy másik elfajult eset áll fenn: D(G) = ∅, így A(G) = ∅, és ekkor C(G) = V (G).

Ha G = (A, B) páros gráf, és az A színosztály teljesíti a szigorú Hallfeltételt, akkor A(G) = A és D(G) = B. Ugyanis nyilvánvalóan ν(G) = |A|, és a Hall-tétel miatt minden v ∈ B-re G − v-nek van egy A-t fedő maximális párosítása, ami így az eredeti G-ben is maximális párosítás, tehát D(G) = B, és így A = A(G).

Tehát a Gallai–Edmonds-felbontás faktorkritikus és teljes párosítást tartalmazó gráfokra, tovább a Hall-feltételt szigorúan teljesítő gráfokra triviális. Másrészről az alábbiakban megmutatjuk, hogy tetszőleges gráf felépíthető ebből a három fajta gráfból.

Legyen G_{0} = (U, W) páros gráf és az U színosztályra teljesüljön a szigorú Hall-feltétel. Minden w ∈ W -re legyen G_{w} faktorkritikus gráf. Legyen H egy olyan gráf, amelynek létezik teljes párosítása. ?factorizable?? Az alábbiakban definiálunk egy G gráfot a V (G) = U ∪ V (H) ∪ ⋃_{w∈W} V (G_{w}) csúcshalmazon. Tartsuk meg a H és a G_{w} gráfok éleit. G_{0} minden uw élére (u ∈ U, w ∈ W), vegyünk a gráfunkba egy u-ból G_{w} egy tetszőleges csúcsába menő élet. Vegyünk fel továbbá tetszőleges U-ból V (H)-ba menő, illetve U-n belüli éleket.

2.4. tétel. A fent megkonstruált gráf Gallai–Edmonds-felbontása: A(G) = U, C(G) = V (H), D(G) = ⋃_{w∈W} V (G_{w}). Minden gráf egyértelműen előáll ezen a módon.

Bizonyítás. Nyilván def(G) ≥ c_{0}(G_{U}) − |U| = |W | − |U|. Másrészt legyen M_{0} a G_{0} egy U-t fedő párosítása és legyen az ennek megfelelő élhalmaz G-ben M′_{0}. Minden w ∈ W -re legyen x_{w} ∈ V (G_{w}) a következőképpen definiálva: ha M′_{0} lefedi G_{w} egy pontját, akkor legyen ez a pont, különben G_{w} egy tetszőleges pontja. Minden w ∈ W -re legyen M_{w} a G_{w} − x_{w} gráf egy majdnem teljes párosítása. Legyen M′′ H egy teljes párosítása. Ekkor M = M′_{0} ∪ M′′ ∪ ⋃_{w∈W} G egy olyan párosítása, melynek hiánya |W | − |U|, tehát def(G) = |W | − |U| és M maximális párosítás. Így könnyen látható (ez eleg???), hogy tetszőleges u ∈ v(G) csúcsot pontosan akkor kerül el valamilyen maximális párosítás, ha u ∈ ⋃_{w∈W} V (G_{w}), tehát D(G) = ⋃_{w∈W} V (G_{w}), és mivel U minden pontja össze van kötve valamely ⋃_{w∈W} V (G_{w})-beli ponttal, viszont H egyetlen pontja sincs összekötve ezen pontok egyikével sem, így a tétel első állítását beláttuk.

A második állítás a Gallai–Edmonds strúktúratétel közvetlen következménye.

3. Lovász párosítási algoritmusa

A Gallai-Edmonds-struktúratételt általában Edmonds párosítási algoritmusának segítségével bizonyítjuk. Most azonban a tételt nem algoritmikusan bizonyítottuk, ismertetjük viszont Lovász maximális párosítási algorítmusát, mely a Gallai–Edmonds-struktúratételt használja [1].

Tegyük fel, hogy már találtunk néhány k méretű párosítást. Találni szeretnénk egy nagyobbat vagy meg szeretnénk mutatni, hogy k-nál nagyobb maximális párosítás nem létezik. Jelöljük az eddig megtalált k méretű párosításokat L = (M_{1}, …, M_{t})-vel. Definiáljuk továbbá a gráf ponthalmazának alábbi felosztását:

D(L) = {x ∈ V (G)|x ∉ V (M_{i}) valamely i = 1, …, t-re}
A(L) = {x ∈ v(G) − D(L)|x szomszédos D(L) valamely csúcsával}
C(L) = V (G) − D(L) − A(L)

Vegyük észre, hogy abban az esetben, ha k = ν(G) és L tartalmazza G összes párosítását, akkor ez a Gallai–Edmonds-felbontással egyezik meg: D(L) = D(G), A(L) = A(G), C(L) = C(G).

3.1. lemma. Legyen L a G gráf k elemű párosításainak egy részhalmaza???, és legyen M ∈ L. Tegyük fel, hogy M-ben nincs A(L)-ből A(L) ∪ c(L)-be menő él és M a D(L) által meghatározott gráf komponensein majdnem teljes párosítás. Ekkor M maximális párosítás.

Bizonyítás. A feltételből következően egyrészt D(L) minden komponense páratlan elemszámú, másrészt minden ilyen komponensben pontosan egy olyan pont van, amely nincs lefedve M-beli éllel vagy M olyan éle fedi le, amelynek másik pontja A(L)-beli. ????Ez igy ertheto? Az Is következik, hogy az M párosítás A(L) és D(L) között menő élei lefedik A(L)-t. Így D(L)-nek pontosan A(L)| + |V (G) − V (M)| számú komponense van, és ebből következően:

def(G) ≥ c_{)}(G − A(L))∥A(L)| = |V (G) − V (M)|,

tehát M maximális párosítás.

Most már ismertethetjük az algoritmust. Kezdetben legyen k = 0 és L = ∅. Az általános lépésben válasszuk ki L egyik elemét, M_{1}-et, ha ez teljesítia 3.1. lemma feltételeit, akkor megállunk. Ebben az esetben M_{1} maximális párosítás.

Tegyük fel, hogy az M_{1} párosítás nem teljesíti a 3.1. lemma egyik feltételét. A célunk az, hogy olyan párosítást találjunk, amelynek mérete k-nál nagyobb vagy olyat, amely nem fedi (A(L)) vagy C(L) egy pontját. Két eset lehetséges annak megfelelően, hogy M_{1} a lemma melyik feltételét nem teljesíti.

1. eset. Tegyük fel, hogy M_{1} egyik xy élére x ∈ A(L) és y ∈ A(L)∪C(L). A(L) definíciója szerint az x csúcs szomszédos valamely z ∈ D(L) csúccsal. D(L) definíciója szerinte van olyan M_{2} ∈ L párosítás, amely elkerüli z-t. Ha M_{1} is elkerüli z-t, akkor M_{1}−xy∪xz olyan k méretű párosítás, amely elkerüli y-t. Ha tehát ezt a párosítást hozzávesszük L-hez, akkor D(L) mérete megnő. Ha M_{1} nem kerüli el z-t, akkor tekintsük egy olyan P (M_{1}, M_{2})-alternáló utat, mely z-nél kezdődik. Ha a P út M_{1}-beli éllel kezdődik, akkor véve M_{2}△P -t, k + 1 méretű párosítást kapunk. Ha M_{2}-beli éllel kezdődik, és nincs rajta az xy él, akkor P_{1} = P + zx + xy-ra M_{1}△P_{1} olyan k méretű párosítás, amely elkerüli y-t, tehát D(L) ismét növelhető. Végül ha xy ∈ P, akkor van olyan P_{2} ⊆ P, melyre M′_{1} = M_{1}△P_{1} olyan k mlretű párosítás, amely elkerüli x-et vagy y-t. M′_{1}-t hozzávéve L-hez D(L) nő.

2. eset Tegyük fel, hogy G[d(L)]-nek van olyan T komponense, amelyre M_{1} ∩ e(T) nem majdnem teljes párosítása T -nek.

2/a eset Tegyük fel, hogy M_{1} ∩ E(T) elkerüli T legalább két pontját, mondjuk xy pontokat (x ≠ y), és M_{1} is elkerüli az egyiket, mondjuk x-et. Ha x és y szomszédosak, akkor vegyük M-hez az xy élt, és ha y-t fedi M_{1} valamelyik éle, akkor töröljük azt el. Így vagy egy k + 1 elemű párosítást kaptunk, vagy egy olyan k eleműt, amely elkerül egy A(L)-beli pontot. Mind a két esetben készen vagyunk.

Tegyük fel tehát, hogy x és y nem szomszédosak, legyen T az őket összekötő legrövidebb utak egyike. Legyen ezen az úton az x után következő pont z. D(L) definíciójából következően van olyan M_{i} ∈ L párosítás, amely elkerüli z-t. Jelöljük Q-val a z-nél kezdődő (M_{1}, M_{2})-alternáló utat. Ha Q nem x-szel végződik, akkor Q paritásától függően Q vagy Q + xz növelő út M_{1}-re illetve M_{i}-re nézve. Ha a Q alternáló út x-nél végződik és keresztülmegy y-n, akkor tartalmaz legalább egy A(L)-beli pontot. De ekkor M_{1}-ben kicseréljük Q + xy élét???? úgy, hogy a kapott párosítás kihagyja ezt az A(L)-beli pontot, akkor, ezt a párosítást hozzáadva L-hez, D(L) mérete megnő.

Végezetül ha a Q alternáló út x-ben végződik, de nem halad keresztül y-n, akkor az M′_{1} = M_{1}△Q olyan párosítás, amely elkerüli z-t, továbbá M′_{1}∩E(T) elkerüli y-t. Mivel T -ben z és y távolsága kisebb mint x és y távolsága, ezért ezt az eljárást ismételve a fenti esetek egyikéhez jutunk.

2/b eset Tegyük fel, hogy M_{1} ∩ E(T) T legalább két pontját, x-et és y-t elkerüli, de M_{1} nem kerüli el T egy pontját sem. Ebben az esetben x és y össze van párosítva két A(L)-beli ponttal u-val és v-vel. Legyen M_{i} ∈ L egy x-et elkerülő párosítás és jelöljön Q egy x-nél kezdődő (M_{1}, M_{i})-alternáló utat. Ha Q utolsó éle M_{1}-beli, akkor M_{1}△Q k + 1 méretű párosítás, tegyük fel tehát, hogy Q utolsó éle M_{i}-beli. Ha Q nem halad át az y ponton, akkor M′_{1} = M_{1}△Q olyan k méretű párosítás, amely elkerüli x-et, és amelyre M′_{1} ∪ E(T) elkerüli y-t. Tehát ekkor ismét az (a) esettel állunk szemben. Ha Q keresztülhalad y-n, és y páros távolságra van Q végpontjaitól, akkor Q megfelelő részének és M_{1}-nek a szimmetrikus differenciája olyan k méretű M′_{1} párosítás, amely elkerüli y-t és M′_{1} ∩ E(T) elkerüli x-t. Ez tehát megint a 2/a eset.

Végül, ha y páratlan távolságra van Q végpontjaitól, akkor Q megfelelő részének és M_{1}-nek a szimmetrikus differenciája olyan k méretű M′_{1} párosítás, amely valamely v ∈ A(L) pontot elkerül. Az M′_{1} párosítást hozzáadva L-hez, D(L) mérete megnő.

2/c eset. Tegyük fel, hogy M_{1} ∩ E(T) a T komponens teljes párosítását adja. Ekkor |T | páros. Tegyük fel, hogy M_{i} ∈ L elker-li T egy pontját. Mivel |T | páros, M_{i} ∩ E(T) a T komponens egy másik pontját is elkerüli, ez tehát megint a 2/a eset.

4. Törtpárosítások és 2-párosítások

4.1. definíció. Adott G gráfra egy x ∈ ℝ^{E}(G) vektort törtpárosításnak nevezünk, ha teljesíti a következő feltételeket:

x(δ(v)) ≤ 1 minden v ∈ V -re  (3)
x ≥ 0 minden e ∈ E-re  (4)

Ezek a feltételek meghatároznak egy poliédert, a törtpárosítási poliédert.

Abban a speciális esetben, ha x egészértékű, a G gráf egy párosítását kapjuk.

4.1. tétel. A törtpárosítások P poliéderének minden csúcsa félegész (vagyis olyan vektor, melynek elemeit kettővel szorozva egész számokat kapunk).

Bizonyítás. Legyen x a P törtpárosítási poliéder egy csúcsa. Ha a gráf valamely e élére x_{e} = 0, akkor G − e-re indukciót alkalmazhatunk, így feltehetjük, hogy x_{e} > 0 minden e élre. Ebből következően x_{e} < 1 is teljesül minden e élre, és a gráf minden csúcsának legalább kettő a foka.

Mivel x a poliédernek csúcsa, ezért a (4) feltételek közül |E(G)| darab egyenlőséggel teljesül, tehát |E(G)| ≤ |V (G)|, így G 2-reguláris. A (4) feltételeket az x_{e} = \frac{1}{2} vektor kielégíti, és a megoldás egyértelmű (hisz x csúcs), így a tétel állítását kapjuk.

Vegyük észre, hogy a poliéder csúcsai olyan x törtpárosítások, melyek előállnak a következő alakban: egy M párosítás és tőle és egymástól diszjunkt C_{1}, C_{2}, …, C_{n} körök uniója. e ∈ M-re x_{e} = 1, a körök élein \frac{1}{2}. Nevezzük ezeket a törtpárosításhoz tartozó párosításnak, illetve törtköröknek.

Mivel max_{x∈P} x1x, a maximális törtpárosítás értéke a P poliéder csúcsán is felvétetik, ezek után elég csak ilyen alakú törtpárosításokkal foglalkozni, ezeket elemi törtpárosításnak vagy egyszerűen törtpárosításnak nevezzük a továbbiakban. Az x törtpárosítás tartója E azon éleiből áll, amelyeken x értéke \frac{1}{2} vagy 1, ezt S(x)-szel jelöljük. Telített, nem telített csúcs. Az x-hez tartozó törtrészgráf azon élekből áll, amelyeken a x értéke \frac{1}{2}. Ha a v ∈ V (G) csúcsra x(δ(v)) = 1, akkor azt mondjuk, hogy csúcs telítve van, különben nincs telítve. A törtpárosítást teljesnek nevezzük, ha minden csúcsot telít; ha egy kivételével minden csúcsot telít, akkor majdnem teljesnek nevezzük. Legyen x maximális törtpárosítás a G gráfban Ekkor G törtpárosítási száma, ν_{f}(G), a telített csúcsok számának fele (vagyis 1x), G törtpárosítási hiánya def_{f}(G) pedig a telítetlen csúcsok száma.

4.1. A maximális törtpárosítás keresésének visszavezetése a maximális párosítás problémájára

Tetszőleges G gráfra a G-ben levő izolált pontok számát jelöljük i(G)-vel.

4.2. tétel. Legyen G gráf. Ekkor

def_{f}(G) = max_{S⊆V (G)} i(G − S) − |S|.

Bizonyítás. A ≥ irány triviális. A másik irány igazolásához definiáljuk az alábbi G′ = (A, B) páros gráfot: feleltessünk meg minden u ∈ V pontnak két pontot: u′-t és u′′-t. és minden uv élnek két élet az új gráfban: u′v′′-t és u′′v′-t. Vegyünk ezen egy maximális párosítást, legyen ez M, az ennek megfelelő vektor x′ (x′_{e} = 0, ha e ∉ M, x′_{e} = 1, ha e ∈ M. Legyen ezek után

x_{uv} = (x′_{u′v′′} + x′_{u′′v′})/2.

Ez nyilván törtpárosítás az eredeti gráfban, így def_{f}(G) ≤ V (G) − |M|. A Kőnig-tétel szerint G′-ben van |M| méretű lefogó ponthalmaz, ennek egyik színosztálybeli része legyen T, és legyen S az eredeti gráf T -nek megfelelő ponthalmaza. Ekkor az eredeti gráfból elhagyva S-et, az izolált pontok számára i(G − S) ≥ |V (G)| − |M| + |S|. Ezzel állításunkat beláttuk.

Mivel páros gráfokra jóval egyszerűbb a maximális párosítási probléma, mint nem páros gráfokra, ezért azt mondhatjuk, hogy a törtpárosítási probléma bizonyos értelemben jóval egyszerűbb, mint a párosítási probléma. A fenti visszavezetés azonban nem ad választ (vagy csak nem túl jól használható választ ad) arra a kérdésre, hogy milyenek a maximális törtpárosítások. Ennek megválaszolásához az eredeti gráfot kell megvizsgálnunk.

4.2. Az U-párosítások. Pulleyblank struktúratétele

Először belátunk két lemmát a faktorkritikus gráfokról.

4.1. lemma. Legyen G legalább három pontú faktorkritikus gráf. Ekkor van benne olyan páratlan hosszú kör, melyet ha összehúzunk, a kapott gráf szintén faktorkritikus lesz.

Bizonyítás. Legyen uv a gráf egy éle. Mivel G faktorkritikus, ezért G − unak és G−v-nek is van teljes párosítása, jelöljük ezeket M_{1}-gyel illetve M_{2}-vel. Ekkor van olyan P (M_{1}, M_{2})-alternáló út, amely összeköti u-t és v-t. Nyilván P páros és M_{1} − E(P) a G − V (P) gráf teljes párosítását adja. Így P + uv megfelelő kör lesz.

4.2. lemma. Legyen G faktorkritikus. Ekkor G-nek van olyan teljes törtpárosítása, amelyre F (x) egyetlen körből áll

Bizonyítás. Mivel G faktorkritikus, ezért az előző lemma szerint van benne egy C páratlan kör, melynek összehúzásával a kapott G × C gráf is faktorkritikus lesz. Jelöljük a C összehúzásából keletkező csúcsot C̃-vel. G × C faktorkritikus, így van olyan majdnem teljes párosítása, mely C̃-t hagyja ki. G − C-n ezt a párosítást, C élein \frac{1}{2}-et véve a tétel állításának megfelelő teljes törtpárosítást kapunk.

4.2. definíció. U-párosítás (Uhry francia matematikusról) Olyan maximális törtpárosítás, melyre F (x) tartalmazásra nézve minimális.

Vegyünk egy x törtpárosítást és legyenek a hozzá tartozó F (x)-ben a diszjunkt páratlan körök C_{1}, C_{2}, … C_{n}. Ebből a törtpárosításból az alábbi, újrapárosításnak nevezett eljárással könnyedén kaphatunk egy párosítást. Vegyünk egy kört C_{i}-k közül és vegyük egy tetszőleges csúcsát, v_{j}-t, majd innen indulva menjünk végig a kör élein és felváltva növeljük meg illetve csökkentsük 1/2-del x értékét. Végezzük ezt el minden körre. Így egy olyan párosítást kapunk, amely a kiindulási pontok kivételével minden pontot telít. Be fogjuk látni, hogy U-párosítás esetén ezzel az eljárással maximális párosítást kapunk. Ehhez először belátunk egy lemmát.

4.3. lemma. Tetszőleges x maximális törtpárosításhoz létezik olyan M maximális párosítás, amely elkerül minden telítetlen csúcsot.

Bizonyítás. Legyen x maximális törtpárosítás G-ben és M pedig olyan maximális párosítás, amelyre a lehető legkevesebb telítetlen csúcs illeszkedik. Tegyük fel, hogy van legalább egy ilyen csúcs, jelöljük ezt u-val.

Legyen N azon élek halmaza, ahol x = 1, ezek G egy párosítását alkotják. Jelöljük P -vel N ∪N-nek azt a komponensét, amely tartalmazza u-t. P tehát egy olyan út, melynek egyik végpontja u, jelöljük a másik végpontot w-vel.

Ha P páros hosszú, akkor M△P olyan maximális párosítás, amely kevesebb telítetlen csúcsot tartalmaz, mint M, így ellentmondáshoz jutunk. Tehát P páratlan hosszú, és mivel x maximális törtpárosítás, w rajta van valamelyik C_{j} törtkörön. Ekkor azonban x megnövelhető az alábbi módon: C_{j}-t párosítsuk újra w-ből kiindulva, továbbá legyen x_{e} := 0, ha e ∈ P ∩ N, x_{e} := 1, ha e ∈ P ∩ M.

4.3. tétel. Legyen x U-párosítás. Ekkor x tartója, S(x) tartalmaz maximális párosítást.

Bizonyítás. Az lemma alapján feltehetjük, hogy minden csúcs telített, hiszen a telítetlen csúcsok elhagyása nem csökkenti a maximális párosítás méretét.

Legyen N az x U-párosításhoz tartozó párosítás, M pedig egy olyan párosítás, amely a lehető legkevesebb x_{e} = 0 élet tartalmazza. Vegyük M ∪ N egy P komponensét, ekkor P nem lehet kör vagy vagy legalább 2 hosszú páros út, mert ebben az esetben M△P olyan maximális párosítás lenne, amely kevesebb olyan élet tartalmazna, amelyre x_{e} = 0, és ez ellentmond M választásának.

Ha tehát P nem egy pontból áll, akkor páratlan hosszú út, legyenek a végpontjai u és w. Mivel P nem M-növelő út, így u és w is valamely törtkörön van rajta, jelöljük ezeket C_{u}-val illetve C_{w}-vel. Ha C_{u} ≠ C_{w}, akkor az egyik újrapárosításával olyan törtpárosítást kapunk, melynek törthalmaza kisebb szigorúan tartalmazza az eredetiét, tehát x nem volt U-párosítás. Tehát C_{u} = C_{w}.

Ebből következően x minden C_{j} törtkörön azoknak a csúcsoknak a száma, amelyeket fed M, páros, az M által fedetlen csúcsok száma pedig páratlan. Így felírhatjuk az alábbi egyenlőtlenséget (n-nel jelöljük a törtkörök számát):

2|M| ≤ |V | − n = 2|N| + ∑_{j=1}^{n}(|C_{j}| − 1)

Így ha minden törtkört újrapárosítunk, akkor kapunk egy olyan M′ párosítást, mely benne van x tartójában, és |M′| ≥ |M|.

4.1 következmény. Legyen x U-párosítás. Ekkor minden törtkörét újrapárosítva maximális párosítást kapunk.

Ezek után már kimondhatjuk Pulleyblank U-párosításokra vonatkozó struktúratételét [5], mely a Gallai–Edmonds-féle felbontáson alapszik.

4.4. tétel. Az U-párosítások struktúratétele. Legyen a G = (V, E) gráf Gallai–Edmonds-felbontása (D, A, C) és legyen x elemi törtpárosítás. Ekkor x pontosan akkor U-párosítás, ha az alábbiak teljesülnek. (a) F (x) ⊆ γ(O)

(b) x C-n teljes párosítás

(c) Minden v ∈ A-ra létezik egy w ∈ D, hogy x_{(v,w)} = 1

(d) Legyen K(V_{K}, E_{K}) D egy tetszőleges komponense. K F (x)-nek legfeljebb egy körét tartalmazza, ha egy körét tartalmazza, akkor x teljes törtpárosítás K-n; ha egyet sem, akkor x majdnem teljes párosítás K-n, és ha a K komponens nem triviális (több mint egy pontja van), akkor van olyan u pontja, melyre létezik v ∈ I, hogy x_{(u.v)} teljesül.

(e) D triviális (egypontú) komponenseit O^{1}-gyel, ennek szomszédait N(O^{1})- gyel jelölve x maximális párosítás G[O^{1} ∪ N(O^{1})]-en.

Bizonyítás. Legyen x olyan törtpárosítás, amely teljesíti a fenti (a)–(e) tulajdonságokat teljesíti. Először belátjuk, hogy x maximális törtpárosítás.

A (d) és (e) állítások alapján G x által nem telített pontjainak Õ halmaza O^{1}-ben van. (e)-ből a Kőnig tétel miatt az következik, hogy van olyan S ⊆ N(O^{1}) ponthalmaz, hogy ezt kitörölve G[O^{1} ∪ N(O^{1})]-ben |S| + |Õ| darab telítetlen csúcs keletkezik. De ekkor S-et elhagyva G-ből úgyszintén |S| + |Õ| darab telítetlen csúcs lesz. Így 4.2. tételünk alapján x maximális törtpárosítás.

Most belátjuk, hogy F (x) tartalmazásra nézve minimális, tehát azt, hogy x U-párosítás. Legyen x̄ az x törtpárosítás újrapárosításával kapott párosítás. ??? tételünket használjuk, ?? (b)-ből, (a)-ből és (d)-ből illetve (c)-ból következik, tehát x̄ maximális párosítás. Tegyük fel, hogy F (x) nem minimális, ekkor létezik egy olyan x′ maximális törtpárosítás, melyre F (x′) ⊆ F (x). Párosítsuk újra x′-t, ekkor egy olyan x̄′ (egész) párosítást kapunk, mely ellentmond x̄ maximalitásának.

Megfordítva, most tegyük fel, hogy x U-párosítás. Belátjuk, hogy ekkor a fenti (a)–(e) tulajdonságok teljesülnek rá.

Minden olyan v csúcsra, mely F (x) egyik páratlan körén van, létezik xnek egy olyan x̄ újrapárosítása, mely nem telíti v-t. Uhry tétele (4.3.) alapján x̄ maximális párosítás, tehát v ∈ O, így F (x) ⊆ γ(O); ezzel beláttuk (a)-et. Az x̄ párosításra alkalmazva a refged tételt (b) és (c) állítások közvetlenül következnek refgeda és refgedc-ből. Legyen K D egy komponense. A refged tétel alapján x̄ K-nak legfeljebb egy pontját nem telíti. Így F (x)-nek legfeljebb egy köre tartozik K-hoz. Ha van egy ilyen kör, akkor (d) azonnal következik. Ha nincs, és K nem triviális komponens, akkor x a K komponens minden csúcsát telíti. Ugyanis tegyük fel, hogy nem így van, ekkor a 4.2. tételt alkalmazva kaphatnánk egy olyan párosítást, amely ellentmondana x maximalitásának. Tehát (d) ebben az esetben is teljesül.

Már csak az utolsó (e) tulajdonságot kell belátnunk. Az eddig elmondottakból következik, hogy minden olyan csúcs, amit nem telít x, O^{1}-ben van. Konstruálni fogunk egy olyan x̂ törtpárosítást, mely csak O^{1}-beli csúcsokat telít, és fennáll rá (e). Ekkor, mivel x maximális, ezért legalább annyi pontot telít, mint x̂, ezért rá is teljesül (e). Vegyünk G[O^{1} ∪ N(O^{1})] egy tetszőleges maximális párosítását, legyen ez x̃. Edmonds és Fulkerson egy tétele szerint F = {S ⊆ V : Ge valamely párosítása telíti S minden csúcsát} definícióval (V, F) matroidot alkot. Ebből következik, hogy van G-nek egy olyan x′ párosítása, mely G[O^{1} ∪ N(O^{1})] minden x̃. Vegyük észre, hogy ha O^{1} egy csúcsa telítve van, akkor G[O^{1} ∪ N(O^{1})] egy éle telíti. Legyen K = (V_{K}, E_{K}) egy komponense. Ha |V (K)| > 1 és K-nak van egy olyan csúcsa, amelyet nem telít x′, akkor 4.2. szerint K-nak van egy teljes törtpárosítása, K élein definiáljuk eszerint x̂-ot. Minden más j élre legyen x̂_{j} = x′_{j}. Az így definiált x̂ megfelel a kívánalmainknak és ezzel a tétel állítását beláttuk.

4.3. A struktúratétel következményei. A törtpárosításokra vonatkozó minimax tételek

Vizsgáljuk ismét a G gráf Gallai–Edmonds-féle felbontását, Vegyük D(G) egy komponensét, G_{i}-t, és egy tetszőleges M maximális párosítást. Azt mondjuk, hogy G_{i} M-teli, ha G_{i} valamely pontját összeköti M egy éle A(G) egy pontjával, különben G_{i} majdnem M-teli.refged szerint M lefedi az M-teli komponensek minden csúcsát, és minden majdnem M-teli komponens csúcsai közül egy-egy kivételével az összeset. Tehát D(G)-nek def(G) darab majdnem M-teli komponense van. Jelöljük nc(M)-mel D(G) nemtriviális majdnem M-teli komponenseinek számát, nc-vel pedig ezek maximumát minden maximális párosításra.

Pulleyblank struktúratételéből azonnal következik Yan Liu és Guizhen Liu eredménye [6].

4.5. tétel. ν_{f}(G) = ν(G) + \frac{nc}{2}

Bizonyítás. Vegyünk egy olyan maximális törtpárosítást, amelynek törthalmaza tartalmazásra nézve minimális, tehát egy U-párosítást. Ennek értéke megegyezik a maximális párosítás értékének és a törtkörök száma felének összegével, vagyis

∑_{e∈E} x_{e} = ν + \frac{n}{2}

(a) szerint a törtkörök D(G)-ben vannak, (d) szerint pedig egy komponensben csak egy kör lehet. Legyen M az x újrapárosításával keletkező párosítás. Ekkor (d) szerint n = nc(M), ezzel megkaptuk, hogy ∑_{e∈E} x_{e} ≤ ν(G) + \frac{nc}{2}.

Ez alapján választ kaphatunk, az alábbi, természetesen felvetődő kérdésekre is. Mikor teljesül ν_{f} = ν (vagyis mikor nem nagyobb a maximális törtpárosítási értéke, mint a maximális törtpárosításé)? Mikor lesz ν_{f} = |V |/2 (vagyis mikor van teljes törtpárosítás)?

4.6. tétel. Egy G gráfra ν_{f}(G) = ν(G) pontosan akkor teljesül, ha D(G) stabil??? halmaz.

Bizonyítás. Ha D(g) stabil, akkor nc = 0 nyilvánvalóan. Ha nem stabil, akkor mivel van egy olyan M párosítás, hogy D(G) minden komponense majdnem M-teli ?????

4.2 következmény. Páros gráfokra a maximális törtpárosítás értéke megegyezik a maximális párosítás értékével.

4.7. tétel. G = (V, E)-nek pontosan akkor van teljes törtpárosítása, ha van olyan maximális párosítása, mely lefedi D(G) minden triviális komponensét.

Bizonyítás. 4.5. alapján elég azt belátni, hogy nc = def(G) pontosan akkor teljesül, ha G-nek van D(G) minden triviális komponensét lefedő maximális párosítása. Ez pedig nyilvánvaló, hisz def(G) tetszőleges M-re a majdnem M-teli komponensek száma, nc(M) pedig ezek közül a nemtriviálisoké.

5. f-párosítások és f-faktorok

A párosítások egy másik általánosítása a f-párosítás: Legyen G = (V, E) egy gráf és f ∈ ℤ_{+}^{V}. f-párosításnak nevezünk egy olyan x ∈ ℤ_{+}^{V} függvényt, amelyre teljesül, hogy

x(δ(v)) ≤ f(v).

Ha x minden egyenlőtlenséget egyenlőséggel teljesít, akkor teljes f-párosí-tásról beszélünk. Ha a teljes f-párosításról még azt is megköveteljük, hogy x(e) ≤ 1 teljesüljön, akkor f-faktorról beszélünk. Ebben az esetben tehát G olyan G′ részgráfjait keressük, melyek eleget tesznek a deg′_{G}(v) = f(v) fokszámfeltételeknek.

Ahogy a törtpárosítások esetében, itt is két lehetőségünk van. Egyrészt visszavezethetjük a problémát egy segédgráf segítségével a maximális párosítás problémájára, másrészt vizsgálhatjuk közvetlenül az eredeti gráfot. Az első megközelítés gyorsan választ ad arra a kérdésre, hogy mekkora a maximális f-párosítás, de a másik, jóval nehezebb megközelítésre van szükségünk ahhoz, hogy a megállapításokat tehessünk a maximális f-párosítások szerkezetéről.

5.1. A maximális f-párosítások és f-faktorok keresésének visszavezetése a maximális párosítási problémára

Legyen adva egy G = (V, E), és a csúcsain egy f ≥ 0 egészértékű függvény. Vegyük az alábbi G′ gráfot. Minden v ∈ V -re vegyünk f(v) darab pontot, legyen ezek halmaza U_{v}. A G gráf minden egyes (v, w) élére húzzuk be U_{v} minden pontjából U_{w} minden pontjába az éleket.

5.1. tétel. G maximális f-párosításának értéke megegyezik G′ maximális párosításának értékével. Speciálisan: G-nek pontosan akkor van teljes f-páro-sítása, ha G′-nek van teljes párosítása.

Bizonyítás. Legyen G′ egy maximális párosítása M. Minden (v, w) ∈ E-re legyen az U_{v} és U_{w} között menő élek száma x(vw). Egy v csúcsra felírhatjuk:

x(δ(v)) = ∑_{w} x(v, w) ≤ f(v).

Az egyenlőség x definíciójából következik, az egyenlőtlenség pedig abból, hogy M párosítás, így U_{v}-ből legfeljebb annyi él mehet ki, ahány pontból áll. Tehát ez az x vektor f-párosítás. Hasonlóan láthatjuk be, hogy G egy maximális f-párosításának megfeleltethetünk egy ugyanolyan értékű párosítást G′-ben.

Vizsgáljuk most az f-faktorok problémáját. Legyen adva egy G gráf és egy f egészértékű függvény a csúcsokon, és el kell döntenünk, hogy van-e benne f-faktor. Összuk fel G minde élét ket ponttal, legyen az így kapott gráf G′′. Terjesszük ki f-et úgy, hogy az új pontokon az értéke 1 legyen.

5.2. tétel. G-nek pontosan akkor van f-faktora, ha a fenti módon megkonstruált G′′-nek van teljes f-párosítása.

Bizonyítás. Vegyük észre, hogy G′′ minden teljes f-párosítása egyben ffaktor is. Elég tehát megmutatnunk, hogy G-nek pontosan akkor van f-fak-tora, ha G′′-nek van f-faktora.

Legyen F a G gráf egy f-faktora. Legyen F′′ a következőképpen definiálva: G minden F -ben lévő e élére vegyük bele F′′-be a G′′ gráf e-hez tartozó három éle közül a két szélsőt. G azon e éleire pedig, amelyek nincsenek F - ben, vegyük bele F′′-be a G′′ e-hez tartozó 3 éle közül a középsőt. Az így kapott F′′ élhalmaz nyilván G′′ egy f-faktora lesz.

Ugyanezt az eljárást fordítva végrehajtva G′′ tetszőleges f-faktorából kaphatunk G-nek egy f-faktorát.

5.2. Az f-faktorok struktúratétele

Az alábbiakban ismertetjük Lovász f-faktorokról szóló struktúratételét [1]. Először is általánosítjuk az f-faktorok fogalmát: eddig olyan részgráfot kerestünk, eleget tettek bizonyos felső fokszámkorlátoknak, most a fokszámokat alulról is korlátozni fogjuk.

Legyen adva két egészértékű függvény, f_{1} és f_{2} a G gráf csúcshalmazán (f_{1} ≥ f_{2}), és keresünk G éleinek egy olyan H részhalmazát (a továbbiakban H élhalmaz)??hogy is nevezzelek??, amelyre

f_{1}(v) ≥ deg_{H}(v) ≥ f_{2}(v).

Egy kicsit más alakban fogjuk felírni a problémát. Legyen f = f_{1}, g = f̂_{2} = deg_{G} −f_{2} és a H ⊆ E(G) részhalmazra jelölje H̄ = E(G) − E(H). Ekkor a fenti feltétel így írható:

deg_{H} ≤ f és degH̄ ≤ G.

A triviális esetek kizárása érdekében a továbbiakban mindig feltételezni fogjuk, hogy

f, g ≥ 0 és f + g ≥ deg_{G}.

Legyen H ⊆ E(G) tetszőleges élhalmaz. Definiáljuk a következő mennyiségeket:

δ(v; H; f, g) = max{0, deg_{H}(v) − f(v), degH̄ −g(v)}  (5)
δ(H; f, g) = ∑_{v∈V (G)} δ(v; H; f, g)  (6)
δ(f, g) = min_{H}δ(H; f, g).  (7)

Nyilvánvalóan pontosan akkor létezik a 5.2 feltételeket kielégítő élhalmaz, ha δ(f, g) = 0. Az ilyen élhalmazokat (f, g)-faktoroknak fogjuk nevezni. Speciálisan pontosan akkor létezik f-faktor, ha δ(f, f̂) = 0. Megfigyelhetjük továbbá, hogy δ(H; f, g) = δ(H̄; g, f), és így δ(f, g) = δ(g, f). A H élhalmazt (f, g)-optimálisnak hívjuk, ha δ(H; f, g) = δ(f, g). A továbbiakban az a célunk, hogy minimax formulát kapjunk a δ(f, g)-re és leírjuk az (f, g)-optimális élhalmazokat.

ITT kihagytam egy adag megjegyzest

Most definiáljuk a G gráf pontjainak egy felbontását, mely hasonlít a Gallai–Edmonds-felbontásra. A párosítások esetében a felosztás azon alapult, hogy egy pontot lefed-e minden maximális párosítás. Most aszerint megy a felbontás, hogy a 5.2 egyenlőtlenségeket egy-egy pontban teljesíti-e az összes (f, g)-optimális élhalmaz.

C =C(G; f, g) = {v ∈ V (G)| deg_{H}(v) ≤ f(v) és

degH̄(v) ≤ g(v)minden (f, g)-optimálisH élhalmazra}

A =A(G; f, g) = {v ∈ V (G)| degH̄(v) ≤ g(v)

minden (f, g)-optimálisHélhalmazra}

C =C(G; f, g) = {v ∈ V (G)| deg_{H}(v) ≤ f(v)

minden (f, g)-optimálisHélhalmazra}

D =D(G; f, g) = V (G) − A − B − C.

Amikor világos, hogy mely G gráfról van szó, akkor azt fogjuk írni, hogy C(f, g), A(f, g), B(f, g) illetve D(F, g). Vegyük észre, hogy C = V (G) pontosan akkor teljesül, ha G-nek van (f, g)-faktora.

A fenti halmazoknak a következőképpen felelnek meg a Gallai–Edmondsfelbontás részei: C(G; f, g) = C(G), A(G; f, g) = A(G), B(G; f, g) a D(G) rész triviális komonenseinek uniója D(G; f, g) a D(G) rész nemtriviális komponenseinek uniója.

Mielőtt megállapításokat tennénk a most definiált felosztásról, vizsgáljuk meg, hogyan változik meg a δ(H; f, g) mennyiség a H élhalmaz bizonyos éleinek elhagyásánál, illetve bizonyos élek hozzávételénél. Legyen tehát H ⊆ E(G) élhalmazés v ∈ V (G) egy olyan csúcs, melyre deg_{H}(v) > f(v). Töröljünk el H-ból egy tetszőleges vw ∈ H élet. Jelöljük a kapott élhalmazt H′-vel, erre

δ(v; H′; f, g) = δ(v; H; f, g) − 1,  (8)
δ(w; H′; f, g) ≤ δ(w; H, f, g) + 1és  (9)
δ(u; H′; f, g) = δ(u; H; f, g)minden u ≠ v, w-re  (10)

Így δ(H′; f, g) ≤ δ(H; f, g). Tehát ha speciálisan H (f, g)-optimális, akkor H′ is, és a fenti egyenlőtlenség (miért van többes szám?????) egyenlőséggel teljesül, vagyis degH̄(w) ≥ g(w).

Hasonlóan, ha degH̄(v) > g(v), akkor H-hoz H̄ egy tetszőleges, v-re illeszkedő élét hozzávehetjük, a kapott H′ gráfra δ(H′; f, g) ≤ δ(H; f, g). Ennek alapján megfogalmazzuk a következő definíciót.

5.1. definíció. Ha a H élhalmazból úgy hagyunk el élet vagy úgy veszünk hozzá egyet, hogy δ(v; H; f, g) legalább egy v pontnál szigorúan nő, akkor az élhalmaznak ezt a megváltoztatását v-nél való lokális növelésnek nevezzük ((f, g)-re nézve).

Vegyük észre, hogy ha H (f, g)-optimálisés H′-t H-ból egy lokális növeléssel kaptuk, akkor H-t is megkaphatjuk H′-ből egy lokális növeléssel. Továbbá, ha H (f, g)-optimális, akkor egyetlen lokális növelés sem változtatja a C résszel szomszédos??? éleket. Az előző megjegyzésekből pedig az következik, hogy lokális növelésekkel tetszőleges élhalmazból olyanhoz juthatunk, amelyre deg_{H} ≤ f. Tehát a következőt kaptuk.

5.3. tétel. Tetszőleges G gráfra és f és g 5.2 feltételeket kielégítő függvényekre van olyan (f, g)-optimális H élhalmaz, melyre deg_{H} ≤ f

A lokális növelések a párosításelméletben szereplő növelő utaknak felelnek meg. A következő lemma nagyon hasznos lesz a későbbiekben.

5.1. lemma. Legyen J (f, g)-optimális élhalmaz és H tetszőleges élhalmaz. Ekkor H lokális növelésekkel olyan (f, g)-optimális H élhalmazzá alakítható, melyre J△???H_{0} csak C által feszített éleket tartalmaz.

Bizonyítás. Vegyünk két olyan élhalmazt, H′-t és J′-t, melyekre: (a) H′ megkapható H-ból lokális növelésekkel.

(b) J′ megkapható J-ből lokális növelésekkel.

(c) H′△J′ minimális.

Az alábbiakban belátjuk ezen élhalmazpár néhány tulajdonságát.

(1) Minden v ∈ V (G) csúcsra δ(v; H′; f, g) ≤ δ(v; J′; f, g). Tegyük fel ugyanis, hogy δ(v; H′; f, g) > δ(v; J′; f, g) valamely v csúcsra. Tegyük fel, hogy deg_{H′} > f(v)??, ekkor nyilván deg′_{J}(v) < deg′_{H}(v). Így H′ − J′-nek van egy v-re illeszkedő e éle. Az e él törlése H′-ből lokális növelés és csökkenti H′△J′-t, ami ellentmond (c)-nek.

(2) Minden v ∈ V (G) csúcsra δ(v; H′; f, g) = δ(v; J′; f, g) és H′ (f, g)-op-timális.

Ez az előző pontból és abból következik, hogy J′ (f, g)-optimális(hisz (f, g)-optimális élhalmazból kaptuk lokális növelésekkel).

(3) Minden olyan v pontra, melyre δ(v; J′; f, g) > 0, deg_{H′}(v) = deg_{J′}(v)

Tegyük fel ugyanis, hogy az egyenlőség nem teljesül, mondjuk deg_{H′} : deg_{J′}(v). A (2) tulajdonság miatt deg_{J′}(v) ≤ ĝ(v), f(v) ≤ deg_{H′}(v). Töröljük ki H′−J′ egy élét, ez egy lokális növelés, ami ellentmond a minimalitásnak (c).

(4) Ha δ(v; H′; f, g) > 0, akkor H′△J′ egyetlen éle sem illeszkedik v-re.

Tegyük fel ugyanis, hogy mondjuk e ∈ H′−J′, és e a v csúcsra illeszkedik. A (3) tulajdonság miatt deg_{H′}(v) = deg_{J′}(v), továbbá az állítás feltétele miatt deg_{H′}(v) > f(v) vagy degH̄′ > g(v). Az első esetben töröljük el et a H′ élhalmazból, a második esetben vegyük hozzá e-t a J élhalmazhoz. Mind a két esetben lokális növelést hajtottunk végre és |H′△J′| csökkent. Ez ellentmond a (c) minimalitási tulajdonságnak.

(5) Ha v ∉ C, akkor H′△J′ egyetlen éle sem illeszkedik v-re.

Vegyünk olyan H′ és J′ élhalmazokat, melyek teljesítik az (a), (b) és (c) tulajdonságokat, az (5) tulajdonságot nem és egy olyan K (f, g)-optimális élhalmazt, amelyre δ(v; K; f, g) > 0 (ilyen van, hisz v ∉ C), mindezt úgy, hogy a |H′△K| minimális (d).

Ekkor H′-n nem lehet olyan lokális növelést végrehajtani, amely csökkentené |H′△J′|-t. Ha lenne ugyanis ilyen lokális növelés, akkor ugyanannál a pontnál, ahol végrehajtottuk, a (4) tulajdonság miatt végre lehetne hajtani J′-n is, ennek eredményeképp kapnánk egy (H′′, J′′) élhalmazpárt, amely (a)-t, (b)-t és (c)-t teljesítené, de (5)-öt nem (hisz H′′△J′′ = H′△J′.

Az (1) és (2) tulajdonságok bizonyításához hasonlóan látható, hogy δ(v; H; f, g) = δ(v; K; f, g) > 0. Ez azonban ellentmond (4)-nek. Ezzel az (5) állítás bizonyítását befejeztük.

Tehát a H′ és J′ élhalmazok (f, g)-optimálisak és H′△J′ a gráf C részében van. A lemma előtti megjegyzés szerint J′-ből megkaphatjuk J-t lokális növelésekkel. Ugyanezeket a lokális növeléseket azonban (5) miatt H′- n is végrehajthatjuk, és kapunk egy H_{0} (f, g)-optimális élhalmaz.t, melyre H_{0}△J = H′△J a C részben van. Ezzel a lemma állítását beláttuk.

A lemmából azonnal adódik az alábbi két következmény.

5.1 következmény. Minden élhalmaz (f, g)-optimális élhalmazzá alakítható lokális növelésekkel.

5.2 következmény. Két (f, g)-optimális élhalmaz pontosan akkor alakítható egymásba lokális növelésekkel, ha minden C által feszített él vagy mind a kettő élhalmazhoz hozzátartozik vagy egyikhez sem tartozik hozzá.

5.4. tétel. Legyen G tetszőleges gráf és f_{1} ≤ f_{2} … ≤ f_{k} illetve g_{1} ≤ g_{2} ≤ … ≤ g_{k} olyan egészértékű függvények a gráf csúcshalmazán, melyekre teljesül f_{1} + g_{1} ≤ deg_{G}, f_{1} ≤ 0 és g_{1} ≤ 0. Ekkor G-nak van egy olyan élhalmaza, amely minden i1 … k-ra (f_{i}, g_{i})-optimális

Bizonyítás. A bizonyítás k szerinti indukcióval megy, k = 1-re az állítás triviális. Legyen H′ a G gráf olyan élhalmaza, mely (f_{i}, g_{i})-optimális minden i = 1..k − 1-re. A 5.1 következmény miatt H′-t (f_{k}, g_{k})-optimálissá tudjuk tenni (f_{k}, g_{k}) szerinti??? lokális növelésekkel. A f_{k}, g_{k} szerinti lokális növelések azonban nyilvánvalóan f_{i}, g_{i} (i = 1, …, k − 1) szerinti lokális növelések is. Így H i = 1, …, k − 1-re is (f_{i}, g_{i})-optimális.

5.5. tétel. Tetszőleges v ∉ C csúcs foka az (f, g)-optimális élhalmazokban egy intervallum egész számai közül veheti fel értékét???ez így érthető???.

Bizonyítás. Tegyük fel, hogy a = deg_{H}(v), b = deg_{J}(v) valamely H és J (f, g)-optimális élhalmazokra. A 5.1. lemma miatt H átalakítható lokális növelésekkel egy H′ élhalmazzá, mely szintén (f, g)-optimális és deg_{H′}(v) = deg_{J}(v). Mivel a lokális növelések v fokát legfeljebb eggyel változtatják, így az egyes lépéseknél kapott élhalmazokkal minden a és b közti egész számot megkapunk. ???ez így kicsit zavarosan van leírva az utolsó mondat

Megjegyezzük, hogy a fenti tétel állítása nem feltétlenül igaz C pontjaira. valami szoveg Legyen f a G ponthalmazán definiált egészértékű függvény, továbbá v ∈

V (G). Bevezetjük az alábbi függvényt, mely f értékét egy pontban eggyel megnöveli:

f^{v}(w) = \begin{cases}f(w) + 1, & ha v = w \\ f(w), & ha v ≠ w \end{cases}

Ezeket a függvényeket persze komponálni is lehet (f^{u})^{v}-t f^{uv}-vel jelöljük. Gyakran fogjuk használni f^{vv}-t.

5.6. tétel. Legyen G tetszőleges gráf, f és g pedig a V (G)ün értelmezett a 5.2 egyenlőtlenségeket kiegyenlítő függvények. Ekkor a következők igazak:

(a) Ha v ∈ A, akkor deg_{H}(v) ≥ f(v) minden H (f, g)-optimális élhalmaz-ra.

(b) Ha v ∈ B, akkor deg_{H}(v) ≥ g(v) minden H (f, g)-optimális élhalmazra.

(c) Ha v ∈ D, akkor f(v) = ĝ(v) és a v foka (f, g)-optimális élhalmazokban f(v) − 1, f(v) vagy f(v) + 1 lehet.

Bizonyítás. (a) Tegyük fel indirekt módon, hogy létezik egy olyan H (f, g)- optimális élhalmaz, melyre deg_{H}(v) < f(v). Mivel A definíciója szerint deg_{H}(v) ≥ ĝ(v), azt kapjuk, hogy f(v) > ĝ(v). A 5.3. tétel szerint H át tudjuk alakítan lokális növelésekkel olyan J (f, g)-optimális élhalmazzá, melyre δ(v; J; f, g) > 0, és így A definíciója szerint deg_{J}(v) > f(v). A lokális növelések végrehajtása során v foka f(v) − 1-ről f(v)-re nő, ez azonban nem lehetséges, hisz (f, g)-optimális élhalmazból indultunk ki.

A (b) résznek és (c) rész első állításának a bizonyítása hasonlóan megy. D definíciójából és a 5.5. tételből az is világos, hogy f(v)−1, f(v) és f(v)+1 előfordul v fokaként valamely (f, g)-optimális élhalmazokra. Azt kell tehát csak belátnunk (ismét csak a 5.5. tételre hivatkozva), hogy v foka sem f(v)−2, sem f(v) + 2 nem lehet (f, g)-optimális élhalmazban.

Tegyük fel indirekt módon, hogy valamely (f, g)-optimális élhalmazra mondjuk deg_{H}(v) = f(v) + 2. Ekkor δ(H; f^{vv}, g^{v}) = δ(H; f, g) − 2, és így

δ(f^{vv}, g^{v}) ≤ δ(f, g) − 2.

Hasonlóan

δ(f, g^{v}) ≤ δ(f, g) − 1.

A 5.4. tétel miatt van egy olyan J élhalmaz, amely egyszerre (f, g)-, (f, g^{v})- és (f^{vv}, g^{v})-optimális. Ekkor miatt

δ(J; f^{vv}, g^{v}) ≤ δ(J; f, g) − 2,

miatt pedig

δ(J; f, g^{v}) ≤ δ(J; f, g) − 1.

Ez utóbbi szerint azonban deg_{J}(v) < f(v), és az egyenlőtlenség egyenlőséggel teljesül, így ekkor δ(J; f^{vv}, g^{v}) = δ(J; f, g^{v}) = δ(J; f, g) − 1, ami ellentmond -nek.

5.7. tétel.

5.8. tétel. Legyen adva a G gráf, és a 5.2 egyenlőtlenségeket teljesítő f és g függvény. Legyen (A, B, C, D) a gráf pontjainak felosztása. Ekkor a következők teljesülnek:

(a) Egyetlen A és C között menő vagy A által feszített él sincs benne (f, g)-optimális élhalmazban.

(b) Minden B és C k0z0tt menő és B által feszített él benne van minden (f, g)-optimális élhalmazban.

(c) C és D között nem megy él.

Bizonyítás. (a) Legyen uv olyan él, melyre u ∈ C és v ∈ A ∪ C és tegyük fel az állítással ellentétben, hogy van olyan H (f, g)-optimális élhalmaz, amely tartalmazza az uv élet. A definíciójából és a 5.1. lemmából következik, hogy H lokális növelésekkel olyan J (f, g)-optimális élhalmazzá alakítható, amelyre deg_{J}(u) > f(u)??????. Legyen K tetszőleges (f, g)-optimális élhalmaz. Vegyük észre, hogy A és C definíciójából következően uv eltörlése K-ból nem növelheti sem δ(K; u; f, g)-t, sem δ(K; v; f, g)-t????, tehát nem lokális növelés. Tehát uv ∈ J. De ekkor deg_{J}(u) > f(u) miatt uv eltörlése J-ből lokális növelés, ami ellentmond az észrevételünknek.

A (b) és (c) állításokat hasonló gondolatmenettel bizonyíthatjuk be.

A következő lemma a stabilitási lemmához hasonlít.

5.2. lemma. Legyen G gráf és f_{1}, f_{2}, g_{1}, g_{2} a ponthalmazán értelmezett egészértékű függvények. Tegyük fel továbbá, hogy f_{1} ≤ f_{2}, g_{1} ≤ g_{2} és f_{1}+g_{1} ≥ deg_{G}. Ekkor az alábbi tartalmazások teljesülnek:

\begin{matrix}A(f_{1}, g_{1}) ⊇ & A(f_{2}, g_{2}) \\ B(f_{1}, g_{1}) ⊇ & B(f_{2}, g_{2}) \\ D(f_{1}, g_{1}) ⊇ & D(f_{2}, g_{2}) \end{matrix}

Bizonyítás. Azt fogjuk megmutatni, hogy v ∉ C esetén akkor és csak akkor létezik olyan (f_{1}, g_{1})-optimális élhalmaz, melyre deg_{H_{1}}(v) > f_{1}(v), ha létezik olyan (f_{2}, g_{2})-optimális élhalmaz, melyre deg_{H_{2}}(v) > f_{2}(v). Ebből a lemma állítása nyilván következik.

⟸ Tegyük fel, hogy létezik olyan H_{2} (f_{2}, g_{2})-optimális élhalmaz, melyre deg_{H_{2}}(v) > f_{2}(v). Ekkor nyilván δ(f_{2}^{v}, g_{2}) ≤ δ(f_{2}, g_{2}) − 1. Mivel f_{1} ≤ f_{2}^{v} és g_{1} ≤ g_{2}, ezért a 5.4. lemma miatt van olyan H élhalmaz, amely egyszerre (f_{1}, g_{1})-optimális és f_{2}^{v}, g_{2})-optimális. Ekkor azonban:

δ(H; f_{2}^{v}, g_{2}) = δ(f_{2}^{v}, g_{2}) ≤ δ(f_{2}, g_{2}) − 1 ≤ δ(H; f_{2}, g_{2}) − 1.

Ebből pedig következik, hogy deg_{H}(v) > f_{2}(v) ≤ f_{1}(v).

⟹ Tegyük fel most, hogy létezik olyan H_{1} (f_{1}, g_{1})-optimális élhalmaz, melyre deg_{H_{1}}(v) > f_{1}(v). Ekkor

δ(f_{1}^{v}) ≤ δ(f_{1}, g_{1}) − 1.

Feltételünk szerint v ∉ C(f_{2}, g_{2}), tehát

δ(f_{2}^{v}, g_{2}^{v}) ≤ δ(f_{2}, g_{2}) − 1.

Használjuk ismét a 5.4. lemmát és vegyünk egy olyan H élhalmazt, amely egyszerre (f_{1}^{v}, g_{1})-optimális és f_{2}^{v}, g_{2}^{v})-optimális. Ekkor a következőt kapjuk:

δ(H; f_{1}^{v}, g_{1}) = δ(f_{1}^{v}, g_{1}) ≤ δ(f_{1}, g_{1}) − 1 ≤ δ(H; f_{1}, g_{1}) − 1,

és így deg_{H}(v) > f_{1}(v). Hasonlóan

δ(H; f_{2}^{v}, g_{2}^{v}) = δ(f_{2}^{v}, g_{2}^{v}) ≤ δ(f_{2}, g_{2}) − 1 ≤ δ(H; f_{2}, g_{2}) − 1),

Tehát deg_{H}(v) ∉ [g_{2}(v), f_{2}(v)]. De mivel deg_{H}(v) > f_{1}(v) ez azt jelenti, hogy deg_{H}(v) > f_{2}(v).

Most már csak azt kell megmutatnunk, hogy a H élhalmaz (f_{2}, g_{2})-optimális. Ez azonban nyilvánvaló, hisz

δ(J; f_{2}^{v}, g_{2}^{v}) ≥ δ(J; f_{2}, g_{2}) − 1,

bármely J élhalmazra, tehát -ben egyenlőség áll.

A szokásos (f, g) függvénypárunkhoz most bevezetünk további, a G gráf ponthalmazán értelmezett egészértékű függvényeket.

f̄(v) = \begin{cases}deg_{G}(v), & ha v ∈ B ∪ C \\ f(v), & ha v ∈ A ∪ D \end{cases}

ḡ(v) = \begin{cases}deg_{G}(v), & ha v ∈ A ∪ C \\ g(v), & ha v ∈ B ∪ D \end{cases}

f′(v) = \begin{cases}deg_{G}(v), & ha v ∈ B ∪ C \\ 0, & ha v ∈ A \\ f(v), & ha v ∈ D \end{cases}

g′(v) = \begin{cases}deg_{G}(v), & ha v ∈ A ∪ C \\ 0, & ha v ∈ B \\ g(v), & ha v ∈ D \end{cases}

5.3. lemma. Legyen G tetszőleges gráf. Ekkor a fenti jelölésekkel A(f′, g′) = A(f̄, ḡ) = A(f, g), B(f′, g′) = B(f̄, ḡ) = B(f, g),C(f′, g′) = C(f̄, ḡ) = C(f, g), D(f′, g′) = D(f̄, ḡ) = D(f, g) . Továbbá teljesül a következő:

δ(f, g) = δ(f̄, ḡ) = δ(f′, g′) − f(A) − g(A).

Bizonyítás. Vegyünk egy olyan H élhalmazt, amely egyszerre (f, g)-op-timális és (f̄, Barg)-optimális. (Ilyen ismét csak a 5.3. lemmát használva létezik.) Ekkor:

δ(f, g) = δ(f̄, Barg)

Előző (5.2.) lemmánk szerint A(f̄, ḡ) ⊆ A(f, g), B(f̄, ḡ) ⊆ B(f, g), D(f̄, ḡ) ⊆ D(f, g). Most belátjuk, hogy C(f̄, ḡ) ⊆ C(f, g) is teljesül. Tegyük fel, hogy v ∉ C(f, g). Ekkor van olyan J (f, g)-optimális élhalmaz, hogy mondjuk deg_{J}(v) > f(v). Ekkor azonban f̄ definíciója szerint f̄(v) = f(v). Nyilván a J élhalmaz (f̄, ḡ)-optimális is, tehát v ∉ C(f̄, ḡ).

Most vegyünk egy olyan I élhalmazt, amely egyszerre (f′, g′)-optimális és (f̄, ḡ)-optimális. Ekkor

δ(f̄, ḡ) = δ(f′, g′) − g(A) − f(B).

Ismét az előző lemmát használva kapjuk:

A(f̄, ḡ) ⊆ A(f′, g′), B(f̄, ḡ) ⊆ B(f′, g′), D(f̄, ḡ) ⊆ D(f′, g′).

Továbbá, ha v ∈ C(f̄, ḡ), akkor f′(v) = g′(v) = deg_{G}(v), és így C definíciója miatt C(f̄, ḡ) ⊆ C(f′, g′). Tehát C(f̄, ḡ) = C(f′, g′).

Már csak D szerkezetét kell leírnunk. Ehhez bevezetjük a párosításelméletből ismert faktorkritikus gráf fogalmának analogonját.

5.2. definíció. A G gráf (f, g)-kritikus, ha összefüggő és A = B = C = ∅

Megfigyelhetjük, hogy ilyen gráfra a 5.6. tétel (c) állítása miatt f = ĝ. Könnyű megmutatni, hogy G pontosan akkor (f, g)-kritikus, ha összefüggő és δ(f^{v}, g), δ(f, g^{v}) < δ(f, g) minden v ∈ V (G)-re.

Most belátunk egy olyan tételt, amely a Gallai-lemmának felel meg.

5.9. tétel. Legyen g (f, g)-kritikus. Ekkor δ(f, g) = 1.

Bizonyítás. Legyen v ∈ V (G) tetszőleges, és vizsgáljuk meg az (f^{v}, g) párt. A 5.2. lemma miatt

V (G) = D(f, g) = D(f^{v}, g) ∪ (f^{v}, g).

A 5.8. tétel miatt viszont D(f^{v}, g) és C(f^{v}, g) között nem megy él, tehát D(f^{v}, g) = V (G) vagy C(f^{v}, g) = V (G). Az első eset nem fordulhat elő, hisz f^{v}(v) = f(v) + 1 > ĝ(v). Tehát C(f^{v}, g) = V (G) vagyis δ(f^{v}, g) = 0. Ekkor azonban

δ(f, g) ≤ δ(f^{v}, g) + 1 = 1.

Mivel δ(f, g) ≠ 0, a tétel bizonyítását befejeztük.

5.3 következmény. Ha G (f, g)-kritikus, akkor f(V (G)) páratlan.

Most már beláthatjuk fő struktúratételünket. Definiáljuk az f_{A} és g_{B} függvényeket a következő módon: f_{B}(v) = f(v)−|▽(v, B)|, g_{A}(v) = g(v)−|▽(v, A)|, ahol ▽(v, B) a v és B közt menő élek számát jelöli ???. Vegyük észre, hogy f_{B} + g_{A} = deg_{G[C∪D]}.

5.10. tétel. Legyen G tetszőleges gráf, legyenek f és g a ponthalmazán értelmezett olyan egészértékű függvények, melyekre f + g ≤ deg_{G}. Legyen A, B, C, D a gráf fent definiált felosztása és legyenek D_{1}, …, D_{t} a G(D) rész összefüggő komponensei. Ekkor minden D_{i} (f_{B}, g_{A})-kritikus és G(C)-nek van (f_{B}, g_{A})-faktora. Továbbá

δ(f, g) = t + |▽(A, B)| − f(A) − g(B).

Bizonyítás. Feltehetjük, hogy f(v) = 0 minden v ∈ A-ra és g(v) = 0 minden v ∈ B-re, ugyanis máskülönben a 5.3. lemma alapján tekinthetnénk az f′ és g′ függvényeket.

Legyen a H élhalmaz (f, g)-optimális. Tudjuk a 5.8. tételből, hogy H nem tartalmaz A-t és C-t összekötő illetve A által feszített élet, viszont benne van minden B és C között menő él és minden B által feszített él. Mivel minden v ∈ A-ra f(v) = 0, az A-ra illeszkedő élek elhagyása lokális növelés, feltehetjük, hogy H nem tartalmaz A-ra illeszkedő élet. Hasonlóan feltehetjük, hogy H minden B és D között menő élt tartalmaz. Egyszerű számolás mutatja, hogy

δ(H; f, g) = δ(H[D]; f_{B}, g_{A}) + |▽(A, B)|.  (11)

Megfordítva, legyen J_{0} a G(D) rész tetszőleges (f_{B}, g_{A})-optimális élhalmaza. és legyen

J = J_{0} ∪ g(B) ∪ ▽(B, D) ∪ ▽(B, C) ∪ H[C],  (12)

ahol H tetszőleges (f, g)-optimális élhalmaz. Ekkor a fenti számolás mutatja, hogy

δ(J; f, g) = δ(J_{0}; f, g) + |∥▽(A, B)|.

A 11 és 12 egyenlőtlenségek miatt

δ(f, g) = δ(f_{B}, g_{A})∥▽(B, C)|.  (13)

A 11 és 13 egyenlőtlenségekből következik, hogy ha a H élhalmaz (f, g)-op-timális, akkor H[D] (f_{B}, g_{A})-optimális élhalmaz.

Most belátjuk, hogy minden v ∈ D benne van D(G[D]; f_{B}, g_{a}). Ehhez legyen H olyan (f, g)-optimális élhalmaz, melyre deg_{H}(v) > f(v). Vegyük hozzá H-hoz ▽(B, D) összes élét. A hozzávételek mind lokális növelések, tehát kapunk egy másik (f, g)-optimális élhalmazt, H′-t, és erre még mindig áll deg_{H′} > f(v). Töröljük ki H′ összes A-ra illeszkedő élét, ezzel megint lokális növeléseket hajtottunk végre.és mivel a „hiány” ??? az A rész pontjainál csökken, tehát ezen élek másik végpontjánál nőnie kell, tehát deg_{H′′}(v) > f(v). Ekkor azonban:

deg_{H′′[D]}(v) = deg_{H′′}(v) − |▽(v, B)| > f(v) − |▽(v, B)| = f_{B}(v).

Továbbá H′′[D] (f_{B}, g_{A})-optimális a fenti megfigyelés alapján. Hasonlóan tudunk konstruálni olyan (f_{B}, g_{A})-optimális élhalmazt, amelyre v foka kisebb, mint f(v)???. Ezzel tehát beláttuk, hogy D(G[D]; f_{B}, g_{A}) + D. Ebből következően G(D) minden komponense (f_{B}, g_{A})-kritikus. Tehát δ(f_{B}, g_{A}) = t, és így a 13 egyenlőség felhasználásával készen vagyunk.

Következő célunk az, egy δ(f, g)-re vonatkozó minimax erdmény bebizonyítása, amelyből az f-faktorok létezésének szükséges és elégséges feltétele azonnal következik.

5.3. definíció. Legyen G gráf, f és g a ponthalmazán értelmezett nemnegatív, egészértékű függvények, és legyen X, Y ⊆ V (G) diszjunkt. Azt mondjuk, hogy G − X − Y egy K komponense (X, Y)-páratlan ((f, g)-re nézve), ha (a) f(v) = ĝ(v) minden v ∈ V (K) és (b) f(V (K)) + |▽(V (K), Y)| páratlan.

Könnyen ellenőrizhető, hogy K pontosan akkor (X, Y)-páratlan (f, g)-re nézve, ha (Y, X)-páratlan (g, f)-re nézve. G − X − Y (X, Y)-páratlan komponenseinek számát τ(X, Y)-nal jelöljük. Vegyük észre, hogy D[G] minden komponense (A, B)-páratlan, így τ(A, B) a D(G) rész komponenseinak a száma.

5.11. tétel. Legyen G gráf, f és g két nemnegatív egészértékű függvény a ponthalmazán, melyekre f + g ≥ deg_{G}. Ekkor

δ(f, g) = max_{X,Y ⊆V (G),X∩Y =∅}{τ(X < Y) + |▽(X, Y)| − f(X) − g(Y)}.

Bizonyítás. Legyen egy tetszőlegesH élhalmazt és X, Y ⊆ V (G) diszjunkt. Megmutatjuk, hogy

δ(H; f, g) ≥ τ(X, Y) + |▽(X, Y)| − f(X) − g(Y).  (14)

Legyen Z = v(G) − X − Y, ekkor tudjuk, hogy

δ(H; f, g) ≥ ∑_{v∈X}(deg_{H}(v) − f(v)) + ∑_{v∈Y}(degH̄(v)) + ∑_{v∈Y}(degH̄(v) − g(v))

(15)

+ ∑_{v∈Z} δ(v; H; f, g).  (16)

Legyen K G − X − Y tetszőleges (X, Y)-páratlan komponense. Ekkor egyszerűen meggondolható, hogy vagy K tartalmaz olyan v pontot, melyre δ(v; h; f, g) ≠ 0 vagy H-nak van K és X között menő vagy H̄-nek van K és Y között menő éle. Így

∑_{v∈Z} δ(v; H; f, g) ≥ τ(X, Y)|▽_{H}(Z, X)| − |▽H̄(Z, Y)|,

és ebből

δ(H; f, g) ≥ degH̄(X) + deg_{H}(Y) − f(X) − g(Y)  (17)
+τ(X, Y) − |▽_{H}(Z, X)| + |▽H̄(Z, Y)|.  (18)

Tudjuk, hogy

deg_{H}(X) + degH̄(Y) ≥ |▽_{G}(X, Y)| + ▽_{H}(Z, X)| + |▽H̄(Z, Y)|,

így 14 valóban fennáll. Előző (5.10.) tételünk szerint tetszőleges H (f, g)-op-timális élhalmazra X = A és Y = B esetén 14-ben egyenlőség áll, tételünk bizonyítását befejeztük.

Ha f = ĝ, akkor megkapjuk az alábbi tételt.

5.12. tétel. (Tutte tétele az f-faktorokról) A G gráfnak pontosan akkor van f-faktora, ha bármely X, Y ⊆ V (G) diszjunkt csúcshalmazra igaz, hogy G − X − Y -ban azon K komponensek száma, melyekre f(V (K)) + |▽(V (K), Y)| páratlan, legfeljebb f(C) + f̂(Y) − |▽(X, Y)|.

6. f-törtpárosítások és 2f-párosítások

A f-párosítás definíciójának mintájára definiálhatjuk a f-törtpárosításokat. A fenti jelölésekkel y ∈ ℝ_{+}^{E(G)} f-törtpárosítás, ha y(δ(v)) ≤ f(v). A maximális f-törtpárosítás problémája visszavezethető a maximális törtpárosítás problémájára. Vegyünk ugyanis egy G′(V′, E′) segédgráfot: minden v ∈ V -re re vegyünk f(v) darab pontot, és minden (u, v) = e ∈ E élre kössünk össze minden, u-hoz rendelt V′-beli pontot minden v-hez rendelt V′-beli ponttal. A segédgráf törtpárosításaiból az eredeti gráfban f-törtpárosítás kapható és viszont.

A maximális f-törtpárosítást a folyamproblémára is vissza lehet vezetni. Legyen G′′ = (V′′, E′′) segédgráf a következő rendeljünk minden egyes v ∈ V ponthoz egy v′ és egy v′′ pontot, tavábbá legyen s forrás és t nyelő. Az eredeti gráf minden (u, v) eléhez húzzuk be a segédgráfban a (u, v′) és a (u′, v) éleket, ezeken legyen a kapacitás 1, húzzunk be továbba minden s és v′, továbbá v′′ és t közti élet, ezeken legyen a kapacitás f(v). A maximális folyam pont a maximális törtpárosítás kétszerese lesz. Ezzel beláttuk azt is, hogy maximális f-törtpárosítás (és így a maximális törtpárosítás) értéke félegész vektoron is felvétetik, tehát elég csak ilyen alakú f-törtpárosításokkal foglalkozni.

Az x f-törtpárosítás tartója, S(x), azon élek halmaza, ahol x > 0. Az f-törtpárosítások P poliéderének csúcsait a következőképpen jellemezhetjük [3, 4]:

6.1. tétel. Az x törtpárosítás pontosan akkor csúcs, ha S(x) egyik komponense sem tartalmaz páratlan kört és legfeljebb egy kört vagy telítetlen csúcsot tartalmaz.

Felvetődik a kérdés, hogy ilyen f-törtpárosításokra adható-e a Pulleyblankéhoz hasonló struktúratétel.

Hivatkozások

[1] L. Lovász, M. D. Plummer: Matching Theory, Akadémiai Kiadó, Budapest, 1986

[2] A. Schrijver: Combinatorial Optimization, Springer, Berlin, 2003

[3] A. Schrijver személyes közlése

[4] E. L. Johnson: Network Flows, Graphs and Integer Programming (PhD. dolgozat), Operations Research Center, University of Berkeley, California, 1965

[5] W. R. Pulleyblank: Fractional Matchings and the Edmonds–Gallai theorem, Discrete Applied Mathematics 16, 1987 51–58.

[6] Yan Liu and Guizhen Liu: The Fractional Matching Numbers of Graphs, NETWORKS, Vol. 40(4), 2002, 228–231.

[7] J. P. Uhry: Sur le problème du couplage maximal, Revue Française d’Automatique, Informatique et Recherche Opérationelle, 9 (V–3), 1975, 13–20.

[8] A. Frank: Kombinatorikus algoritmusok, sokszorosított jegyzet