„Gráfelméleti fogalomtár” változatai közötti eltérés

→‎Színezések: kidolgozás
(→‎Színezések: kidolgozás)
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 ==
321

szerkesztés