„Gráfelméleti fogalomtár” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a →Szomszédság és fokszám: görög betűk+ adj mátrrix jelölése A(G) |
a →Szomszédság és fokszám: görög betű |
||
120. sor:
A ''v'' csúcs '''szomszédai''' (vagy '''nyílt szomszédsága'''; jelölése <math>N_{G}(v)</math>) azok a csúcsok mellyekkel ''v'' szomszédos, kivéve önmagát. Ha a szomszédok közé ''v''-t is beleértjük, akkor '''zárt szomszédság'''ról beszélünk (jelölése <math>N_{G}[v]</math>). Az alsó indexben lévő ''G'' elhagyható, ha nem okoz félreértést. Egyszerű gráfban egy csúcs fokszáma a szomszédainak száma (<math>d_G(v)=|N_G(v)|</math>).
Egy gráf '''domináló halmaz'''a a csúcsok egy olyan részhalmaza, melyek zárt szomszédsága a gráf összes csúcsát tartalmazza. Egy ''v'' csúcs '''dominál''' egy másik ''u'' csúcsot, ha ''v''-ből ''u''-ba van él. Egy ''W'' csúcsrészhalmaz '''dominál''' egy másik ''U'' csúcsrészhalmazt, ha minden ''U''-beli csúcs szomszédos valamelyik ''W''-beli csúccsal. A legkevesebb csúcsú domináló halmaz mérete a '''dominálási szám''' (jelölése [[Gamma|γ]](''G'')).
A számítógépekben egy véges irányított vagy irányítatlan ''n'' csúcsú gráfot gyakran reprezentálnak az '''[[adjacencia mátrix]]'''ával (másnéven ''szomszédsági mátrix''; jelölése ''A''(''G'')): ez egy ''n''×''n''-es (négyzetes) [[mátrix]], melynek az ''i''-edik sor ''j''-edik oszlopában lévő szám adja meg az ''i''-edik csúcsból a ''j''-edik csúcsba menő élek számát. Az irányítatlan gráfok adjacencia mátrixa a főátlóra szimmetrikus; az egyszerű gráfoké csak 0-kból és 1-kből áll, és a főátló csupa 0.
| |||