„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 →<span id="Irányított gráfok">Irányított gráfok</span>: görög betű link |
→Színezések: kidolgozás |
||
277. sor:
An arborescence, or out-tree or branching, is an oriented tree in which all vertices are reachable from a single vertex. Likewise, an in-tree is an oriented tree in which a single vertex is reachable from every other one.
-->
== Színezések ==
Egy '''színezés''' a gráfelméletben „színeket” (''kék'', ''zöld'' stb., de lehetnek [[természetes szám]]ok is az általánosságot megőrizve) rendel a gráf elemeihez. Ezek az elemek lehetnek csúcsok, élek, tartományok, vagy ezeknek a keverékei.
Egy gráf színezése alatt (hacsak a szövegkörnyezet nem utal másra) általában a gráf csúcsainak színezését értjük. Egy színezés '''jó''' (''helyes'', ''megfelelő''), ha a szomszédos csúcsok különböző színűek. Egy gráf '''''k'' színnel színezhető''', ha van legfeljebb ''k'' színt használó jó színezése. Egy ''G'' gráf '''kromatikus szám'''a (jelölése [[khi|χ]](''G'')) az a legkisebb ''k'' szám, amelyre ''G'' ''k'' színnel színezhető.
Egy gráf '''élszínezés'''e jó, ha a szomszédos élek különböző színűek. Egy gráf '''''k'' színnel élszínezhető''', ha van legfeljebb ''k'' színt használó jó élszínezése. Egy ''G'' gráf '''élkromatikus szám'''a (jelölése [[khi|χ]]<sub>''e''</sub>(''G'')) az a legkisebb ''k'' szám, amelyre ''G'' ''k'' színnel élszínezhető.
== Lásd még ==
| |||