„Páros gráf” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
Nincs szerkesztési összefoglaló |
||
40. sor:
Legyen <math>M</math> egy olyan [[Gráfelméleti fogalomtár|párositás]], amely [[javitoutak]]kal mar nem bovitheto. Legyen <math>Y = A - Z</math> azoknak az <math>X'</math>-beli pontoknak a halmaza, melyek <math>Y</math>-bol elerhetok [[alternalo]] uton. Ertelemszeruen, <math>X</math> az <math>X'</math> parjainak halmaza. Legyen <math>W = X'</math> <math>\cup</math> <math>(Z - X)</math>. <math>W</math>-nek pontosan <math>|M|</math> pontja van, melyek minden elet lefognak, ugyanis <math>N(X</math> <math>\cup</math> <math>Y) = X'</math> (<math>N(X)</math> jeloli az <math>X</math> halmaz szomszedjait egy paros grafban). Ebbol: <math>\tau(G)</math> <math>\leq</math> <math>|M|</math> <math>\leq</math> <math>\nu(G)</math>, es a segedtetelbol adodik az allitas.
<math>
[[Gallai tétel|Gallai tetelei]] miatt <math>\nu(G) + \rho(G) = \tau(G) + \alpha(G)</math> es mivel <math>\nu(G) = \tau(G)</math>, <math>\alpha(G) = \rho(G)</math> -nek is teljesulnie kell.
| |||