Kislexikon

 

csúcs fokszáma
a gráf adott csúcsából kiinduló élek száma

eloszlás
Egy véletlenszerű mennyiséget azzal írunk le, hogy minden x valós számra meghatározzuk, mi annak a valószínűsége (x függvényében), hogy a mennyiség kisebb, mint x. Az igy kapott függvényt nevezzük a mennyiség eloszlásának.

gráf
Matematikai struktúra, mely csúcsokból (pontokból, szögpontokból) és azokat összekötő élekből áll. Ebben az előadásban minden gráfnak véges számú csúcsa és éle van, és azt is feltesszük, hogy a szereplő gráfokban két csúcsot legfeljebb egy él köt össze (egyszerű gráf).

haranggörbe
Az exp(-x2) függvény grafikonja (esetleg eltolva). Szokták Gauss-görbének is nevezni. A valószínüségszámításban a normális eloszlás ábrázolásával kapunk ilyen görbét. Nagyon sok mérési adat vezet ilyen eloszláshoz, elsősorban akkor, ha a mérést sok kis független hiba terheli. Ennek matematikai megfogalmazása a Centrális Határeloszlástétel.

kétváltozós függvény
Olyan f(x,y) függvény, mely két változótól, x-től és y-tól is függ. Az előadásban x és y 0 és 1 közötti valós számok lehetnek, így az (x,y) számpárt az egységnyi oldalú négyzet egy pontjának tekintjük. A függvény értéke is nulla és egy közé esik, ami lehetővé teszi, hogy a függvényt a pont szürkeségével ábrázoljuk (ahol a függvény értéke 0, ott a pont fehér, ahol az érték 1, ott a pont fekete, ahol a függvény értéke a kettő között van, ott ennek megfelelően szürke).

lemma
Segédtétel - olyan matematikai állítás, melyet azért bizonyítunk be, hogy egy másik, önmagában is érdekes tétel bizonyításában is felhasználjuk. Előfordul azonban, hogy a lemma sok más bizonyításban is felhasználható, és néha fontosabbá válik, mint maga a tétel, melynek a bizonyítása végett először megalkották.

nagy számok törvénye
Legegyszerűbb változatában azt mondja ki, hogy ha egy pénzérmét sokszor feldobunk, akkor az esetek mintegy felében látunk fejet. Pontosabban, bármely pozitív c számra annak a valószínűsége, hogy a fejek aránya kisebb, mint 1-c, vagy nagyobb, mint 1+c, nullához tart, ha a pénzérme feldobások száma végtelenhez tart.

összefüggő gráf
Olyan gráf, melynek bármely csúcsából bármely másik csúcsába eljuthatunk úgy, hogy minden lépésben egy csúcsból egy vele éllel összekötött csúcsba lépünk.

sűrű gráf
Pontatlanul: olyan gráf, melyben a csúcspárok pozitív százaléka össze van kötve. Pontosabban gráfoknak egy növekvő sorozatáról mondjuk, hogy sűrű, ha van olyan c pozitív szám, hogy a sorozat minden gráfjára teljesül, hogy legalább cn2 éle van, ahol n a csúcsok száma.

Szemerédi-féle regularitási lemma
Szemerédi Endre 1975-ben bizonyított lemmája, melyet egy számelméleti probléma megoldására használt: Erdős és Turán azon fontos sejtésének bizonyítására, hogy egész számoknak minden pozitív sűrűségű sorozata tartalmaz akármilyen hosszú számtani részsorozatot. A lemma azóta a gráfelméleti kutatások egyik legfontosabb eszközévé vált. Pontos megfogalmazása bonyolult, hétköznapi nyelven úgy foglamazható meg, hogy minden gráf felbontható olyan részekre, melyek véletlenszerűek, és a részek száma csak attól függ, hogy mennyire pontosan követeljük meg a véletlenszerűséget.