10.2 Alapfogalmak, jelölések

Legyen V elemeknek egy véges halmaza, és E a V elemeiből képezett rendezett párok -esetleg üres - halmaza. Gráfnak nevezzük a V és E által meghatározott struktúrát. Jelölése: G(V,E).V = {v1, v2, ... , vn} halmazt nevezzük a G gráf csúcshalmazának, jelölése V(G).

 

 

1. ábra. Példa egy G(V,E) gráfra.

V(G) elemeinek a számát a gráf rendjének nevezzük. Jelölése: n(G). E(G) elemeinek a számát a gráf méretének nevezzük. Jelölése: m(G). Az n-ed rendű, m méretű gráfot G(n,m) vagy Gn,m jelöli.  Azt mondjuk, hogy e1 = {v1,v2} összeköti a v1 és v2 csúcsokat, v2 és v3  szomszédos csúcsok, e2 és e5  szomszédos élek és e4 és v6 illeszkednek.

Egy G gráf mindig leírható mátrixokkal. A szomszédsági mátrix  A(G) = [aij]nxn  ahol

Az illeszkedési mátrix B(G) = [bij]nxm  ahol

Az 1. ábrán bemutatott gráf szomszédsági és illeszkedési mátrixa:

 
Egy G gráf v csúcsának fokszámán a csúcshoz illeszkedő élek számát értjük. Jelölése: degG v vagy deg v. Az ábrán látható gráfban degG v4=2. Egy csúcsot párosnak vagy páratlannak nevezzük attól függően, hogy a fokszáma páros vagy páratlan. Egy csúcsot izoláltnak nevezünk, ha deg v = 0, és vég-csúcsnak, ha

deg v = 1.

A v csúccsal szomszédos csúcsok halmazát Γ(v)-vel jelöljük. Világos, hogy degGv=|Γ(v)|.

a G gráf minimális, ill. maximális fokszáma:

      

A gráfelmélet segítségével könnyen megválaszolható az alábbi - rejtvényekben gyakran előforduló - kérdés: ha egy fogadáson n résztvevő van, és ezek közül m meghívott ismeri egymást, akkor hány kézfogás történik a kölcsönös üdvözléskor?

Tétel 10.1 ("Kézfogási" Lemma): Tekintsük a G(n,m) gráfot, ahol . Ekkor  

A tétel bizonyítása azonnal következik abból a tényből, hogy minden él pontosan két csúcsra illeszkedik.

Következmény.

Bármely gráfban a páratlan csúcsok száma mindig páros.