Kislexikon

 

árnyék, árnyékhalmaz
Egy k elemű halmaz árnyékhalmazai azon k-1 elemű halmazokból állnak, melyeket egy-egy elem elhagyásával kapunk. Több ilyen halmazból álló halmazrendszer árnyéka az egyes halmazok árnyékhalmazainak összessége, másképpen: azon k-1 elemű halmazok összessége, amelyeket valamelyik k elemű halmazból egy elem elhagyásával kaphatunk.

diszkrét matematika
lásd: kombinatorika

Erdős-szám
Azon matematikusok Erdős-száma 1, akiknek van közös cikkük Erdős Pállal. Akinek nincs közös cikke vele, de van egy olyannal, akinek az Erdős száma 1, annak az Erdős száma 2, stb. Másképpen fogalmazva: alkossunk egy gráfot, melyben a pontok matematikusokat jelképeznek, két ilyen pont össze van kötve, ha az illető matematikusoknak van közös cikke. Egy matematikus Erdős-száma a minimális lépésszám, amennyivel Erdős Páltól eljuthatunk hozzá ebben a gráfban éleken keresztül.

gráf
Alapvetően a matematikában használt fogalom. A gráf valamilyen elemekből áll, némelyek közülük kapcsolatban állnak, mások nem. Ezt jól lehet ábrázolni úgy, hogy az elemeket pontokkal ábrázoljuk, a kapcsolatokat pedig összekötő vonalakkal. A matematikai (függvény-) analízisben a függvények grafikonját is szokás gráfnak nevezni.

gráfelmelet
A gráfok paraméterei közötti kapcsolatokat, a gráfok struktúráját leíró tételek összessége.

kombinatorika
Véges, diszkrét objektumok matematikai elmélete. Egyik fejezete a leszámlálási kombinatorika, ahol az objektumok különféle elrendezési lehetőségeinek számát kell meghatározni. Egy másik fontos fejezet a gráfelmélet. Sok más mellett a véges geometriák elmélete is a kombinatorikához tartozik.

Kevin Bacon-játek
Egy olyan gráfot tekintünk, amiben az objektumok (pontok) filmszínészek, kettő közülük össze van kötve akkor, ha játszottak közös filmben. A játék során két színész távolságát keressük ebben a gráfban.

matematikai tétel
Olyan matematikai állítás, amelynek létezik egzakt bizonyítása.

összefüggő gráf
Bármelyik pontjából eljuthatunk bármelyik másik pontjába élek sorozatán keresztül.

véges matematika
lásd: kombinatorika

véletlen gráf
A véges sok pontú gráf minden élét egy adott (azonos) valószínűséggel választjuk ki, vagy nem. A véletlen gráfokra fontos tulajdonságok teljesülnek nagy valószínűséggel, azaz az esetek túlnyomó részében. A véletlen gráfok egy lényegében a fentivel azonos, de szemléletesebb modellje a következő: A gráfban kezdetben nincs él. Először beveszünk az összes lehetséges élből egyet véletlenül a gráfba, mindegyiket ugyanazzal a valószínűséggel szerepeltetve. A következő lépésben a többi lehetséges él egyikét vesszük hozzá a gráfhoz, megint a maradék éleket egyforma valószínűséggel figyelembe véve. Ezt folytathatjuk addig, míg minden él be nem lesz húzva.