1. tétel - Gráfok alapfogalmai 1. irányítatlan gráf fogalma
A G (irányítatlan) gráf egy (Φ, E, V) hátmas, ahol E az élek halmaza, V a csúcsok (pontok) halmaza,
Φ:
E
{V-beli rendezetlen párok}
illeszkedési leképezés, E és V diszjunktak.
2. illeszkedés
Egy G = (Φ, E, V) gráfban, ahol e eleme E és v eleme V és v eleme
Φ(e)
teljesül, akkor v az e egyik végpontja, e él illeszkedik v-re. Azok a csúcsok, amikre nem illeszkedik él, izolált csúcsnak nevezzük.
3. párhuzamos élek, hurokél
Ha egy él egy csúcsra illeszkedik, akkor hurokélnek nevezzük. Ha egy G = (Φ, E, V) gráfban, ahol e1 ,e2 eleme E, e1 6= e2 , de ugyanazokra a csúcsokra illeszkednek, akkor e1 és e2 párhuzamos élek. 4. szomszédosság e1 ,e2 eleme E, e1 6= e2 szomszédos, ha van közös végpontjuk. v1 ,v2 eleme V, v1 6= v2 szomszédos, ha van él, ami v1 -re és v2 -re is illeszkedik.
5. fok
Ha egy G = (Φ, E, V) gráfban v eleme V csúcsra véges sok él illeszkedik, akkor ezeknek a száma a csúcs fokszáma, jele: d(v). A hurokéleket kétszer számoljuk.
6. reguláris gráf
Egy G = (Φ, E, V) gráf n-reguláris, ha minden v eleme V: d(v) = n. G reguláris, ha létezik n, amire n-reguláris.
7. véges gráf
G = (Φ, E, V) gráf véges, ha E is és V is véges, különben végtelen.
8. izomor zmus
1
G1 = (Φ1 , E1 , V1 ), G2 = (Φ2 , E2 , V2 ), G1 és G2 izomorfak, ha létezik f : E1 → E2 , g : V1 → V2 bijekciók, hogy v eleme Φ(e) akkor, és csak akkor, ha g(v) eleme Φ(f(e)), minden v eleme V, minden e eleme E-re. 9. gráfok Descartes-szorzata 10. részgráf
G1 = (Φ1 , E1 , V1 ), G2 = (Φ2 , E2 , V2 ). G1 -nek G2 részgráfja, ha E2 részhalmaza E1 -nek, V2 részhalmaza V1 -nek, Φ2 része Φ1 -nek. 11. feszített részgráf
G2
a V2 által feszített részgráf, ha az összes olyan E-beli élt tartalmazza,
aminek a végpontjai V2 -ben vannak. 12. komplementer G' részgráfja G-nek, ekkor G'-nek a G-re vonatkozó komplementere:
(Φ|E/E 0 , E/E 0 , V ) 13. páros gráf (példákkal) G = (Φ, E, V) gráf páros, ha létezik V1 , V2 , V1
T
V2 = 0, V1
S
V2 = V
úgy, hogy minden él egyik végpontja V1 -ben, a másik V2 -ben van. Példák: három ház, három kút:
14. séta Egy G = (Φ, E, V) gráfban egy n ≥ 0 hosszú séta v0 -ból vn -be egy v0 , e1 , v1 , e2 , ..., vn−1 , en , vn sorozatból áll, ahol ei a vi−1 , vi csúcsokra illeszkedik, ha i = 1, .., n. Ha v0 = vn (vagyis a kezd®pont megegyezik a végponttal), akkor a séta zárt, különben nyílt.
2
15. vonal Ha egy sétában minden él különböz®, akkor vonal. 16. út Egy séta út, ha v0 ,v1 ,...,vn mind különböz®k. A nulla hosszú séták mind utak is egyben. Az egy hossuú séták csak akkor utak, ha egyetlen éle sem hurokél. 17. kör Egy zárt vonal kör, ha n
≥
1, v0 = vn , de egyébként minden csúcs külön-
böz®. 18. távolság v és v' V-beli csúcsok, kettejük távolsága az ®ket összeköt® utak hosszának a minimuma (amennyiben nincsen köztük út, a vávolságuk végtelen). 19. átmér® Egy gráf átmér®je a csúcspárok közti távolságok maximuma (szuprémuma, ha a gráf végtelen). 20. összefügg®ség Egy ~ ekvivalenciareláció szerinti ekvivalenciaosztályok által feszített részgráfok a gráfok komponensei. Egy gráf összefügg®, ha bármely csúcsából bármely csúcsába vezet út/séta (vagyis ha komponenseinek száma egy). 21. fák de níciója Egy gráf fa, ha összefügg®, és nincs köre. 22. fák jellemzése ekvivalens állításokkal G egyszer¶ gráfra ekvivalens: (a) Fa (b) G összefügg®, de bármely él törlésével a kapott gráf nem összefügg®. (c) minden v, v' élre pontosan egy út vezet v-b®l v'-be (d) G körmentes, de ha hozzáveszünk bármilyen új élt, a kapott gráf már nem körmentes 23. fák jellemzése élszámmal G n csúcsú, egyszer¶, véges gráfra ekvivalens (a) fa (b) (n-1) éle van, körmentes (c) (n-1) éle van, összefügg®
3
BIZONYÍTÁSOK 1. Sétából ugyanolyan végpontokkal rendelkez® utat kaphatunk Állítás: v-b®l v'-be men® sétából elhagyhatunk (v6=v'), hogy út marad vissza Bizonyítás: amíg nem út, addig létezik i és j index, amire vi =vj , vagyis tartalmaz kört. (vi ...ej ) (a kör) törölhet® és vj -t®l megyünk tovább, ami marad, az egy út lesz. 2. Összefügg®ség és komponensek kapcsolatának részletei Állítás: ~ egy ekvivalenciareláció, vagyis re exív, szimmetrikus és tranzitív Bizonyítás: (a) re exív: minden v-re v-b®l v-be 0 hosszú út vezet
v = v0 , e1 , v2, , e2 , ..., en , vn = v 0 egy út v = vn , en , vn−1 , ..., e1 , v0 = v egy út v'-b®l v-be.
(b) szimmetrikus: akkor
v-b®l v'-be,
0
0
v 0 , f1 , ..., fn , v 00 út, ekkor a v, e1 , ..., en , v 0 , f1 , ..., fn , v 00
(c) tranzitív:v, e1 , ..., en , v út és
egy séta v-b®l v-be, azt pedig tudjuk, hogy sétából lehet utat csinálni. 3. fák ekvivalens jellemzései Tétel: G egyszer¶ gráfra ekvivalens: (a) Fa (b) G összefügg®, de bármely él törlésével a kapott gráf nem összefügg®. (c) minden v, v' élre pontosan egy út vezet v-b®l v'-be (d) G körmentes, de ha hozzáveszünk bármilyen új élt, a kapott gráf már nem körmentes Bizonyítás: (1) (1)
(2)
(3)
(4)
(1)
(2) indirekt:
G fa, v és v' közti élt elhagyva még mindig összefügg® lenne, de akkor a v-b®l v'-be men® utat az elhagyott éllel kiegészítve egy kört kapnék G-be, ami ellentmondás, mert G fa volt, fa pedig de níció szerint körmentes. (2)
(3) indirekt:
legalább 2 út van v és v' között, legyen vk és v'k az els® eltérés az utakon, ekkor a (vk−1 ,vk ) él elhagyható lenne, továbbra is összefügg® lenne, ami pedig ellentmondás. (3)
(4)
Vegyünk hozzá v és v' közé egy élt. v-b®l v'-be volt út, az új él bevételével pedig kör keletkezik, vagyis megsz¶nt a körmentesség.
Ha eredetileg is
lenne kör, akkor a kör 2 tetsz®leges pontja között 2 út is menne.
4
(4)
(1) kell: a gráf összefügg®
ha nem lenne az, akkor lenne két csúcs, mely nem lenne összekötve. Ha új élt veszek v és v' közé, akkor a (4) alapján kapunk egy kört. Ezt az élt elhagyva aztán mégis lenne út v-b®l v'-be.
5
