tételek fagráfra
Fának nevezzük azt az összefüggő gráfot, amely nem tartalmaz kört. Fákra vonatkozó néhány tétel: A fák bármely két pontját egyetlen út köti össze. Ha egy fának bármely élét elhagyjuk, akkor a gráf már nem összefüggő. Ha egy fának bármely két olyan pontját összekötjük,a mely között eddig nem volt él, akkor a gráf már tartalmaz kört.
körmentes gráf
Körnek nevezzük a kezdőpontjába visszatérő utat, azaz minden olyan élsorozatot, amely kezdőpontjába tér vissza, és minden pont és minden él csak egyszer szerepelt. Ha egy gráfban nincs kör, akkor azt a gráfot körmentes gráfnak nevezzük. A maximális körmentes összefüggő gráf a fa, hiszen akármelyik két pontját kötnénk is össze, amely eddig nem volt összekötve, akkor a gráfban már lenne kör.
Euler-vonal
Ha egy gráfnak van Euler-vonala, az azt jelenti, hogy a gráf egyik pontjából kiindulva a ceruza felemelése nélkül megrajzolhatjuk a gráfot úgy, hogy ceruzánkkal minden élen pontosan egyszer haladunk át, és visszatérünk a kiindulópontba.
fagráf
Olyan összefüggő gráf, amelyben nincs kör.
sorrendek összeszámlálása
Sorrendek összeszámlálása vagyis hányféleképpen tudunk n elemet sorba rendezni. Kombinatorikában ezzel a kérdéssel a permutáció foglalkozik ami lehet ismétléses vagy ismétlés nélküli. Ha ismétlés nélküli akkor Pn= n!. Ismétléses permutációnál megengedjük a tagok ismétlését Pni = n! /(k1! * k2! * .....* km), ahol k1,k2,..,km azonos elemek számát jelenti.
teljes gráf
Az olyan egyszerű gráfot, amelyben bármely pontból bármely tőle különböző pontba vezet él teljes gráfnak nevezzük.
permutáció
N elem egy adott sorrendjét az n elem permutációjának nevezzük. A permutáció lehet ismétlés nélküli, ha az össze elem különböző, vagy ismétléses, ha az adott n elem között előfordulnak azonos elemek is. N elem ismétlés nélküli permutációinak száma n!, ismétléses permutációinak száma , ahol i1, … im az azonos elemek számát jelenti, így i1 + i2 + i3 + … + im = n.
ötszíntétel
Ha egy térképet úgy akarunk kiszínezni, hogy bármely két szomszédos ország különböző színű legyen, akkor a térkép színezéséhez öt szín elegendő.
fokszámtétel
Bármely gráfban a fokszámok összege az élek számának kétszerese, valamint bármely gráfban a páratlan fokszámú pontok száma páros.
gráf élei
Gráfnak nevezzük pontoknak és éleknek egy halmazát, ahol élekre pontok illeszkednek úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik. Ha két csúcsot több él is összeköt, akkor ezeket az éleket párhuzamos éleknek nevezzük. Ha egy élnek ugyanaz a kezdő és a végpontja, akkor hurokélnek nevezzük.
összefüggés a binomiális együtthatók között
; ; ;
faktoriális
N faktoriálisnak nevezzük , és n!-nel jelöljük az első n pozitív egész szám szorzatát. Így 1! = 1; 2! = ; 3! = .
többszörös él
Ha egy gráfban két pontot több él is összeköt, akkor ezeket az éleket többszörös éleknek vagy párhuzamos éleknek nevezzük.
séta
Az ED, DG, GL, … egymáshoz csatlakozó élek sorozatát sétának nevezzük, ebben az esetben az élek és pontok nem feltétlenül különbözőek, ha két pont között séta van, akkor minden esetben út is van.
Euler-vonalra vonatkozó tétel
Ha egy gráfnak van Euler-vonala, az azt jelenti, hogy a gráf egyik pontjából kiindulva a ceruza felemelése nélkül megrajzolhatjuk a gráfot úgy, hogy ceruzánkkal minden élen pontosan egyszer haladunk át, és visszatérünk a kiindulópontba.
egyszerű gráf
Egy gráfot egyszerűnek nevezünk, ha nincs benne sem hurok- sem párhuzamos él.
ismétléses kombináció
Ha (n N+) k-Ad osztályú (k n) kombinációit úgy képezzük, hogy a k számú elem között az n elem bármelyike akárhányszor szerepelhet, akkor egy ilyen kiválasztást az n elem k-ad osztályú ismétléses kombinációjának nevezzük. Az n elem összes k-ad osztályú ismétléses kombinációinak száma:
valószínűség mint függvény
összeg esemény
Két esemény összegének valószínűsége megegyezik az események valószínűségeinek összegével mínusz a két esemény szorzatának valószínűségével, tehát: P(A + B) = P(A) + P(B) – P(AB)
biztos esemény
Biztos eseménynek nevezzük az olyan eseményt, amely biztosan bekövetkezik. A biztos esemény valószínűsége 1. Például: Szabályos hatoldalú kocka feldobásakor legyen A az az esemény, hogy 10-nél kisebb számot dobunk. Ez biztosan bekövetkezik, s így P(A) = = 1.
komplementer esemény
Elemi események egy halmazát eseménynek nevezzük. A halmaz komplementere, , szintén egy halmaz, amely így esemény. Ezt az eseményt az A komplementer eseményének nevezzük, amely pontosan akkor következik be, ha A nem következik be. Példa: szabályos hatoldalú kocka feldobásakor a lehetséges eredmények hat elemi eseményt határoznak meg: 1, 2, 3, 4, 5 és 6. Legyen A az az esemény, hogy páros számot dobunk. Ez az 2, 4 és 6 elemi események halmaza. Az A komplementer eseménye így az 1, 3 és 5 elemi események halmaza, tehát az amikor a dobott szám páratlan lesz.
szorzat
Az A és B események szorzatának nevezzük, és AB-vel jelöljük azt az eseményt, amely pontosan akkor következik be, ha A és B is bekövetkezik. Példa. Szabályos kockadobáskor jelentse A azt az eseményt, hogy 1-t vagy 2-t dobunk, B pedig azt, hogy 2-t vagy 3-at dobunk. Ekkor AB az az esemény, hogy 2-t dobunk. Az események szorzása kommutatív és asszociatív is. Az A és B események szorzatának nevezzük, és AB-vel jelöljük azt az eseményt, amely pontosan akkor következik be, ha A és B is bekövetkezik. Példa. Szabályos kockadobáskor jelentse A azt az eseményt, hogy 1-t vagy 2-t dobunk, B pedig azt, hogy 2-t vagy 3-at dobunk. Ekkor AB az az esemény, hogy 2-t dobunk. Az események szorzása kommutatív és asszociatív is.
elemi esemény
Az elemi esemény olyan esemény ami bekövetkezhet a kísérlet alatt. Az összes elemi esemény alkotja az esemény teret.
kedvező elemi események
A kedvező elemi események ami olyan elemi események amikor P(a) bekövetkezhet. P(a)= kedvező elemi esemény/ összes elemi esemény.
véletlen mennyiség eloszlása
Ha egy véletlen mennyiség a 0, 1, 2, …, n értékeket (n allat k)*p^k*(1-p)^(n-k) eséllyel veszi fel, akkor ezt a véletlen mennyiséget binomiális eloszlásúnak nevezzük.
egymást kizáró események
Az A és B eseményeket kizárónak vagy diszjunktnak nevezzük, ha , azaz ha A és B egyszerre nem következnek be. Például szabályos hatoldalú kocka dobásakor, ha A az az esemény, hogy páros B pedig az az esemény, hogy páratlan számot dobunk.
eseménytér
Az elemi események összességét eseménytérnek nevezzük.
binomiális eloszlás
Egy esemény valószínűsége P(X=k)=∑_(k=0)n▒〖(n¦k) xk a(n-k) 〗. Ha egy véletlen mennyiség a 0, 1, 2, …, n értékeket az előbb meghatározott eséllyel veszi fel, akkor ezt a véletlen mennyiséget binomiális eloszlásúnak nevezzük. A p értéket az eloszlás paraméterének nevezzük.
relatív gyakoriság
Végezzük n számú kísérletet, amelyek mindegyikének kimeneteleként valamely A esemény vagy bekövetkezik, vagy nem következik be. Ha k azt jelöli, hogy az A esemény hányszor következett be (k valószínűségi változó, amelynek lehetséges értékei: 0, 1, 2, …n számok), akkor k-t az A esemény (abszolút) gyakoriságának, a k/n hányadost pedig az A esemény relatív gyakoriságának nevezzük. A relatív gyakoriság tulajdonságait a nagy számok törvényei írják le.
minta fogalma
Egy adott véges számú sokaságból kiválasztott – véges számú – egységek összessége. A minta elemszáma mindig kisebb, mint maga az alapsokaság. Ha e kettő megegyezik, akkor cenzusról beszélünk.
21. századi közoktatás - fejlesztés, koordináció (TÁMOP-3.1.1-08/1-2008-0002)