10. gyakorlat
Gráfok
Mi a gráf?
Csúcsok és élek halmaza.
- \(V\): a gráf csúcsainak halmaza
- \(E\): a gráf éleinek halmaza
(Pl.: Az \(e_i\) él illeszkedik a \(v_j\)-re és a \(v_k\)-ra.)
Példa
Ha van egy \(G\) gráfunk:
- \(V(G) = \{V_1, V_2, V_3, V_4, V_5\}\)
- \(E(G) = \{(V_1, V_2), (V_3, V_4), (V_2, V_5), (V_1, V_5)\}\)
Fogalmak
- Irányítatlan gráf:
- \(\varphi \, (e_i) = \{v_j, v_k\}\) (halmaz)
- (Konyha nyelven: Nincs benne nyíl)
- Irányított gráf:
- \(\varphi \, (e_i) = (v_j, v_k)\) (rendezett pár)
- (Konyha nyelven: Van benne nyíl)
- Hurokél: ugyanaz a 2 végpontja az élnek (\(v_j = v_k\))
- Párhuzamos él: ugyanazon csúcsokra illeszkedő él
- Egyszerű gráf: nincs benne hurokél és párhuzamos él
- Összetett gráf: nem egyszerű gráf
- Fa: kör nélküli, összefüggő gráf (később lesz definiálva)
- Fokszám: \(V\)-re illeszkedő élek száma, ahol \(v \in V\)
- jele: \(d(v)\)
- irányított gráf esetén van kifok és befok is
- Mindig páros szám
Tétel: A fokszám mindig páros
\[
\sum_{v \in V} d(v) \, = \, 2 \cdot |E| \quad \Rightarrow \quad \text{páros}
\]
Fokszám és élek
A fokszámok összege megegyezik az élek számának 2-szeresével.
\[
\sum d(V_n) = 2E
\]
Teljes gráf éleinek száma
\[
\frac{n \cdot (n-1)}{2}
\]