Páros gráfok
| 1. sor: | 1. sor: | ||
| − | Akkor nevezunk egy <math>G</math> | + | Akkor nevezunk egy <math>G</math> gráfot párosnak, ha <math>G</math> csucsainak halmazát fel tudjuk ugy osztani egy <math>A</math> és <math>B</math> halmazra, hogy az osszes <math>G</math>-beli élre teljesul hogy az egyik végpontja <math>A</math>-ban van, a másik pedig <math>B</math>-ben. Egy <math>G</math> páros gráfot kovetkezoképpen jelolunk: <math>G</math> <math>=</math> <math>(A,B)</math>. |
| − | Teljes | + | Teljes páros gráfnak nevezunk egy olyan páros gráfot melyben minden <math>A</math>-beli pont ossze van kotve minden <math>B</math>-beli ponttal. Jelolés: <math>K_{a,b}</math>, ahol <math>a</math> <math>=</math> <math>|A|</math> és <math>b</math> <math>=</math> <math>|B|</math>. |
| − | == | + | == Tétel == |
| − | Egy G | + | Egy <math>G</math> gráf akkor és csak akkor páros, ha minden <math>G</math>-beli kor páros hosszuságu. |
| + | |||
| + | ====Bizonyitas:==== | ||
| + | |||
| + | Az elso irány nyilvánvalo, ugyanis ha <math>C</math> egy kor a <math>G</math> páros gráfban, akkor <math>C</math> pontjai alternálnak <math>A</math> és <math>B</math> kozott. Tehát világos hogy <math>C</math>-nek páros sok csucsa van. | ||
| + | |||
| + | A másik irányhoz megmutatjuk, hogy ha <math>G</math> minden kore páros sok pontbol áll, akkor meg tudunk adni megfelelo <math>A</math> és <math>B</math> halmazokat. Tekintsunk egy tetszoleges <math>x</math> pontot a gráfban. Ezt rakjuk <math>A</math>-ba. Most, <math>x</math> minden szomszédját rakjuk <math>B</math>-be, és az osszes olyan <math>B</math>-beli pont szomszédját amelyet még nem helyeztunk el, rakjuk <math>A</math>-ba. Ezt folytassuk amig minden pontot el nem helyeztunk <math>A</math>-ba vagy <math>B</math>-be. Ez az algoritmus azért lesz jo, mert ha egy halmazban lenne két szomszédos csucs, akkor a gráfban lenne páratlan kor is, ez viszont ellentmondas. | ||
A lap jelenlegi, 2007. április 30., 22:57-kori változata
Akkor nevezunk egy G gráfot párosnak, ha G csucsainak halmazát fel tudjuk ugy osztani egy A és B halmazra, hogy az osszes G-beli élre teljesul hogy az egyik végpontja A-ban van, a másik pedig B-ben. Egy G páros gráfot kovetkezoképpen jelolunk: G = (A,B).
Teljes páros gráfnak nevezunk egy olyan páros gráfot melyben minden A-beli pont ossze van kotve minden B-beli ponttal. Jelolés: Ka,b, ahol a = | A | és b = | B | .
Tétel
Egy G gráf akkor és csak akkor páros, ha minden G-beli kor páros hosszuságu.
Bizonyitas:
Az elso irány nyilvánvalo, ugyanis ha C egy kor a G páros gráfban, akkor C pontjai alternálnak A és B kozott. Tehát világos hogy C-nek páros sok csucsa van.
A másik irányhoz megmutatjuk, hogy ha G minden kore páros sok pontbol áll, akkor meg tudunk adni megfelelo A és B halmazokat. Tekintsunk egy tetszoleges x pontot a gráfban. Ezt rakjuk A-ba. Most, x minden szomszédját rakjuk B-be, és az osszes olyan B-beli pont szomszédját amelyet még nem helyeztunk el, rakjuk A-ba. Ezt folytassuk amig minden pontot el nem helyeztunk A-ba vagy B-be. Ez az algoritmus azért lesz jo, mert ha egy halmazban lenne két szomszédos csucs, akkor a gráfban lenne páratlan kor is, ez viszont ellentmondas.
