Legyen M egy párosítás és legyen L egy lefogó ponthalmaz egy gráfban. Mit mondhatunk a két halmaz méretének kapcsolatáról? Indoklást is kérnék!

Figyelt kérdés

2010. dec. 26. 22:00

1/2 anonim

válasza:

A maximális párosítás mérete megegyezik a minimális lefogó halmazéval.

A bizonyítást megtalálhatod Frank András: Operációkutatás jegyzetében. Ha jól tudom, fent van az interneten.

2010. dec. 27. 19:37

Hasznos számodra ez a válasz?

2/2 A kérdező kommentje:

Köszönöm a választ, utána fogok nézni!

2010. dec. 28. 02:33

Kapcsolódó kérdések:

Melyik nagyobb halmaz? (matematika)

Ha az A komplementerhalmaz metszete a B komplementerhalmazának, akkor a megoldás az üres halmaz?

Van ilyen halmaz, aminek feltételei az alábbiak?

Mi a különbség a halmaz számossága és elemszáma között?

Határozd meg az n zérótól különböző természetes számot úgy, hogy az n elemű halmaz összes 2 elemű részhalmazainak a száma 6-tal legyen egyenlő?

Mely párosítás teszi lehetővé, hogy a DNS két szála egyenlő távolságra legyen egymástól?

Tudományok főkategória kérdései »

Tudományok - Természettudományok kategória kérdései »

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!