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 n pontú gráfban a legnagyobb fokszám n-1 lehet
• 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?

Megoldás:

Egyik megközelítésben a válasz kombináció(n,2), mert legfeljebb ennyi lehetőségünk van csomópontpárok megválasztására (és minden pár esetén legfeljebb egy élet lehet behúzni a pontok közé).

Másik megközelítésben: ha minden pont minden másikkal össze van kötve, akkor a fokszámok összege n*(n-1), az élek száma pedig ennek a fele.

2.

Hányféle n pontú gráf létezik.

Megoldás:

A válasz 2^(komb(n,2)) = 2^(n*(n-1)/2), mert az előbb meghatározott lehető legtöbb élnek tetszőleges részhalmazát megválasztva egy-egy gráfot kapunk. Ugyanakkor egy k elemű halmaz részhalmazainak száma 2^k (a ^ művelet itt hatványozást jelöl).