extremális gráfelmélet

Magyar

Kiejtés

IPA: [ ˈɛkstrɛmaːliʒɡraːfɛlmeːlɛt]

Főnév

extremális gráfelmélet

(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 $n$ $n$ csúcsú gráf maximális élszáma, ha nem tartalmaz $K_{r+1}$ $K_{r+1}$ -t (azaz egy $r+1$ $r+1$ csúcsú teljes gráfot) részgráfként.
- Példa: Ha nem akarunk háromszöget ( $K_{3}$ ) 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.

További információk

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)