| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén az Erdős Pálról és Pósa Lajosról elnevezett Erdős–Pósa-tétel kimondja, hogy létezik egy f(k) függvény, hogy minden k pozitív egész számra minden gráf vagy tartalmaz k csúcsdiszjunkt kört, vagy f(k) méretű körlefogó csúcshalmazt, ami a gráf minden köréből tartalmaz csúcsot. Továbbá, f(k) = O(k log k) az O jelölés szerint. A tétel miatt szokás azt mondani körökre, hogy „rendelkeznek az Erdős–Pósa-tulajdonsággal”. A tétel állítása szerint bármely véges k számra létezik olyan (legkisebb) f(k) érték, amire igaz, hogy minden, k csúcsdiszjunkt kört nem tartalmazó gráf körei lefedhetők f(k) csúccsal. Ez Bollobás Béla publikálatlan eredményét általánosította, ami szerint f(2) = 3. az általános esetre a c1k log k < f(k) < c2k log k korlátokat bizonyították. Az eredményből következik, hogy bár végtelen sok különböző gráf van, amiben nincsen k diszjunkt kör, ezek mégis véges sok, egyszerűen leírható osztályba sorolhatók. A k = 2 esetre teljes leírást adott. bizonyította, hogy f(3) = 6 és 9 ≤ f(4) ≤ 12. (hu)
- A matematika, azon belül a gráfelmélet területén az Erdős Pálról és Pósa Lajosról elnevezett Erdős–Pósa-tétel kimondja, hogy létezik egy f(k) függvény, hogy minden k pozitív egész számra minden gráf vagy tartalmaz k csúcsdiszjunkt kört, vagy f(k) méretű körlefogó csúcshalmazt, ami a gráf minden köréből tartalmaz csúcsot. Továbbá, f(k) = O(k log k) az O jelölés szerint. A tétel miatt szokás azt mondani körökre, hogy „rendelkeznek az Erdős–Pósa-tulajdonsággal”. A tétel állítása szerint bármely véges k számra létezik olyan (legkisebb) f(k) érték, amire igaz, hogy minden, k csúcsdiszjunkt kört nem tartalmazó gráf körei lefedhetők f(k) csúccsal. Ez Bollobás Béla publikálatlan eredményét általánosította, ami szerint f(2) = 3. az általános esetre a c1k log k < f(k) < c2k log k korlátokat bizonyították. Az eredményből következik, hogy bár végtelen sok különböző gráf van, amiben nincsen k diszjunkt kör, ezek mégis véges sok, egyszerűen leírható osztályba sorolhatók. A k = 2 esetre teljes leírást adott. bizonyította, hogy f(3) = 6 és 9 ≤ f(4) ≤ 12. (hu)
|
