„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
→Klikkek: görög betű link |
a →Szomszédság és fokszám: görög betűk+ adj mátrrix jelölése A(G) |
||
122. sor:
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 γ(''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.
A '''[[spektrális gráfelmélet]]''' tanulmányozza a gráf és adjacencia mátrixának tulajdonságai közti kapcsolatokat.
Egy gráfban a '''maximális fokszám''' (jelölése [[Delta|Δ]](''G'')) az összes csúcs fokszámai közül a legnagyobb; a '''minimális fokszám''' (jelölése [[Delta|δ]](''G'')) a legkisebb.
Egy gráf '''reguláris''', ha minden csúcsának fokszáma megegyezik. Ha minden csúcsának foka ''k'', akkor '''''k''-reguláris'''. 0-regulárisak az ''üres gráf''ok, vagy ''független halmaz''ok; az 1-reguláris gráfok a ''teljes párosítás''ok; a 2-reguláris gráfok csúcsdiszjunkt körök uniói.
145. sor:
Egy '''izolált csúcs''' olyan csúcs, melyre nem illeszkedik egy él sem. Egy '''független halmaz''' olyan csúcsok halmaza, melyek közül semelyik kettő sem szomszédos. Mivel egy független halmaz feletti részgráf mindig üres gráf az ''üres részgráf'' elnevezés is használható. A példa gráfban az 1, 3 és 6 csúcsok egy független halmazt alkotnak; míg a 3, 5 és 6 csúcsok egy másikat.
A '''független csúcsok maximális száma''' (másnéven '''függetlenségi szám'''; jelölése [[Alfa|α]](''G'')) a ''G'' gráf legnagyobb független halmazának elemszáma.
Egy gráf '''felbontható''' független halmazokra abban az értelemben, hogy a csúcshalmaz felbontható páronként diszjunkt független halmazokra. Az ilyen független részhalmazokat '''partíció'''knak, vagy ''független rész''eknek (? 'partite set, or simply part') hívjuk.
| |||