A gráf egy matematikai modell, melyet bizonyos feladatok megoldására használhatunk; pontokból és ezek közötti összeköttetésekből (élekből) áll.
Alkalmazási lehetőségek:
- Adott egy úthálózat, kell rajta navigálni (pl. melyik a legrövidebb út két pont között?);
- Ételfutár útvonalai: hogy tudunk olyan útvonalat gyártani, ami minden rendelést kivisz és lehetőleg minél rövidebb?
- Adottak munkafázisok és ezek közötti összefüggések (Y nem kezdődhet meg, míg X be nem fejeződik). Milyen sorrendben kell ezeket elvégezni, lehet-e egyszerre többet is elvégezni, melyik fázis mennyit csúszhat stb.?
- Előfordulhat-e, hogy egy 5 fős társaságban mindenkinek pontosan három barátja legyen? (A barátságok kölcsönösek.)
Nemirányított (irányítatlan) gráfok
Románul: grafuri neorientate, angolul: undirected graphs.
Cikk pbinfo-n: https://www.pbinfo.ro/articole/810/grafuri-neorientate
Értelmezés
A G = (X,U) halmazpárt nemirányított gráfnak (vagy nemirányított egyszerű gráfnak nevezzük), ahol:
- X - a csúcsok / csomópontok nem üres halmaza (a csúcs románul vârf, angolul vertex, a csomópont pedig románul nod, angolul node);
- U - az élek halmaza, elemei az X kételemű részhalmazai (az él románul muchie, angolul edge).
Általában a csomópontokat 1-től n-ig sorszámozzuk, ahol n = |X|, az éleket pedig [x,y] vagy {x,y} jelöléssel írjuk le, ahol x és y csomópontok.
Gráfok ábrázolása rajzzal: a csomópontok körök (bennük a sorszám), az élek szakaszok ezek között (lehetőleg minél kevesebb metszéspontot képezzenek a rajzon).
Gráfokat ábrázoló program: https://csacademy.com/app/graph_editor/
További fogalmak értelmezése:
- A.m.h. („azt mondjuk, hogy”) az x és y csúcsok szomszédosak, ha létezik az {x,y} él (ami ugyanaz, mint az {y,x} él) (RO: adiacent, EN: adjacent).
- A.m.h egy csomópont illeszkedik egy élre, ha eleme annak, mint halmaznak. Továbbá ekkor ez annak az élnek egy végpontja. (Az illeszkedés románul incidență.)
- A.m.h. két él illeszkedik egymásra, ha van közös végpontjuk.
- Egy pont fokszáma a szomszédainak (vagy a hozzá illeszkedő éleknek) a száma.
- Ha egy csomópont fokszáma 0, akkor izolált pontnak nevezzük.
- Ha egy csomópont fokszáma 1, akkor a pont terminális.
Tulajdonságok:
- egy
npontú gráfban a legnagyobb fokszámn-1lehet - a fokszámok összege az élek számának kétszerese (tehát mindig páros szám)
Példa
X = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }U = { [1,4], [1,5], [2,3], [2,8], [3,11], [4,5], [4,9], [7,10], [8,11] }
- A gráfnak 11 csomópontja és 9 éle van.
- A 6-os számú csomópont izolált, a 7-es, 9-es és 10-es pedig terminális pontok.
- Az 1 és 2 csomópontok nem szomszédosak, az 1 és 4 csomópontok viszont igen.
- A [2,3] és [2,8] élek illeszkedő élek, mert van közös végpontjuk (a 2-es csomópont).
- Az 1-es pont fokszáma 2, a 4-esé pedig 3.
Gyakorlatok
1.
Egy n pontú gráfban legfeljebb hány él lehet?
N*(N-1) a fokszámok összege => élek száma: N*(N-1)/2
Máskép:
élek száma = comb(n,2)
(mert annyi él lehet, ahányféleképpen ki tudunk választani egy pontpárt)
2.
Hányféle n pontú gráf létezik?
Az összes lehetséges él halmazának bármilyen részhalmazát vesszük, az egy gráf. Tehát annyi gráf van, ahány részhalmaza van annak a K = N*(N-1)/2 elemszámú halmaznak.
Hány részhalmaza van egy K elemű halmaznak?
K=0: {} -> {} 1db
K=1: {1} -> {}, {1} 2db
K=2: {1,2} -> {}, {1}, {2}, {1,2} 4db
K=3: {1,2,3} -> {}, {1}, {2}, {3},
{1,2}, {1,3}, {2,3}, {1,2,3} 8db
Sejtés: K -> pow(2,K) részhalmaz
Biz: indukció
felt. hogy a K-1 elemű halmazoknak pow(2,K-1) részhalmazuk,
kellene igazolni K-ra
{1,2,...,K-1,K} részhalmazai kétfélék:
azok, amik nem tartalmazzák a K-t:
== {1,2,...,K-1} részhalmazai -> pow(2,K-1) darab
azok, amik tartalmazzák a K-t:
{ K, esetleg néhány elem az első K-1 közül }
pow(2,K-1) darab
Összesen {1,2,...,K-1,K} halmaznak
pow(2,K-1) + pow(2,K-1) = pow(2,K).
Biz. másképp:
minden részhalmaznak megfelel egy N hosszú bitsor:
1 2 ... K
0/1 0/1 0/1 (0-nincs benne, 1-benne van)
annyi részhalmaz, ahány féle bitsor = pow(2,K)
Biz. megint másképp:
részhalmazok = 0 elemű részhalmaz
+ 1 elemű részhalmazok
+ 2 elemű részhalmazok
....
+ K-1 elemű részhalmazok
+ K elemű részhalmaz
összesen = C(K,0) + C(K,1) + C(K,2) + ... + C(K,K-1) + C(K,K)
= pow((1+1),K) (Newton's Binomial Theorem)
= pow(2,K)
Válasz a feladatra: pow(2, N*(N-1)/2)
Ismétlés
permutációk darabszáma:
permutáció = sorbarendezés
N elem
N=1 1 1 db
N=2 1 2 2 db
2 1
N=3 1 2 3 6 db
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
N=4 1 ... 6db
...
2 ... 6db
...
3 ... 6db
...
4 ... 6db
...
innen indukcióval azonnali
indukció nélkül:
1. elem 2. elem ... (N-1).elem N.elem
(N lehetőség) (N-1 lehetőség) 2 lehetőség 1 leh.
összesen: ezeknek a szorzata
variációk darabszáma:
V(N,K): N elemből K darab kiválasztására hány lehetőség van
(ha számít a kiválasztások sorrendje is)
1. 2. ... K.
N féle (N-1) féle (N-(K-1)) féle
lehetőségek száma: V(N,K) = N*(N-1)*...*(N-(K-1))
= N*(N-1)*...*(N-K+1)
= N! / (N-K)!
kombinációk darabszáma:
C(N,K): N elemből K darab kiválasztására hány lehetőség van
(ha nem számít a kiválasztások sorrendje)
C(N,K) = V(N,K) / P(K) = N! / ( (N-K)! * K! )
Minden kombináció P(K)=K! darab variációnak felel meg.