extremális gráfelmélet
Kiejtés
- IPA: [ ˈɛkstrɛmaːliʒɡraːfɛlmeːlɛt]
Főnév
- (matematika) Az extremális gráfelmélet a gráfelmélet egy ága, amely azzal foglalkozik, hogy milyen szélsőséges tulajdonságokkal rendelkezhet egy gráf adott feltételek mellett. Az extremális problémák tipikusan valamilyen maximális vagy minimális érték meghatározására irányulnak, például:
- Maximális élszám adott csúcsszám és tiltott részgráf mellett: Az egyik legismertebb ilyen probléma a Turán-tétel, amely azt mondja meg, hogy mekkora lehet egy csúcsú gráf maximális élszáma, ha nem tartalmaz -t (azaz egy csúcsú teljes gráfot) részgráfként.
- Példa: Ha nem akarunk háromszöget ( ) egy gráfban, akkor egy kétszínű (kétosztatú) gráf a megoldás.
- Minimális csúcsszámú gráf adott részgráf meglétéhez: Itt az a kérdés, hogy mekkora a legkisebb csúcsszámú gráf, amely adott feltételt biztosít. Ez például a Ramsey-elméletben jelenik meg, ahol azt vizsgálják, hogy mekkora csúcsszám kell ahhoz, hogy bármely élkiszínezés mellett bizonyos részgráf biztosan megjelenjen.
- Extrém struktúrák a gráfokon belül: Ide tartoznak olyan kérdések, hogy adott csúcs- és élszám mellett milyen eloszlású fokszámú gráfok létezhetnek, vagy hogy hogyan maximalizálhatók egy gráf más paraméterei, például a kromatikus szám, a klikk-szám, stb.
Fontos tételek és fogalmak
- Turán-tétel: Az extremális gráfelmélet alaptétele.
- Erdős-Stone tétel: Általánosítás, amely más típusú tiltott részgráfokra is kiterjed.
- Szélsőértékek gráfokban: Például a legnagyobb fokszám, a minimális átlagfokszám, vagy a legnagyobb feszített részgráf mérete.
Alkalmazások
Az extremális gráfelmélet eredményei nemcsak az elméleti matematikában, hanem a számítástudományban, hálózatelméletben, és a kombinatorikus optimalizálásban is fontos szerepet játszanak. Az olyan problémák, mint a hálózatok hatékonyságának és biztonságának optimalizálása, gyakran extremális gráfelméleti eszközöket használnak.
- extremális gráfelmélet - Értelmező szótár (MEK)
- extremális gráfelmélet - Etimológiai szótár (UMIL)
- extremális gráfelmélet - Szótár.net (hu-hu)
- extremális gráfelmélet - DeepL (hu-de)
- extremális gráfelmélet - Яндекс (hu-ru)
- extremális gráfelmélet - Google (hu-en)
- extremális gráfelmélet - Helyesírási szótár (MTA)
- extremális gráfelmélet - Wikidata
- extremális gráfelmélet - Wikipédia (magyar)