| dbo:abstract
|
- A Vizing-tétel alsó és felső korlátot ad egy egyszerű gráf élkromatikus számára. A tételt 1964-ben bizonyította be. A tétel szerint egy egyszerű gráf élkromatikus száma legfeljebb eggyel nagyobb a maximális fokszámánál, azaz ha a gráf minden csúcsában k-nál kevesebb él találkozik, akkor ki tudjuk színezni az éleit legfeljebb k színnel. Képlettel: Az irányítatlan gráfok két osztályba particionálhatók: melyek színezéséhez szín elegendő, azok az „első csoportba” sorolt gráfok (class one), melyekhez szín szükséges, azok a „második csoportba” sorolt gráfok (class two). (hu)
- A Vizing-tétel alsó és felső korlátot ad egy egyszerű gráf élkromatikus számára. A tételt 1964-ben bizonyította be. A tétel szerint egy egyszerű gráf élkromatikus száma legfeljebb eggyel nagyobb a maximális fokszámánál, azaz ha a gráf minden csúcsában k-nál kevesebb él találkozik, akkor ki tudjuk színezni az éleit legfeljebb k színnel. Képlettel: Az irányítatlan gráfok két osztályba particionálhatók: melyek színezéséhez szín elegendő, azok az „első csoportba” sorolt gráfok (class one), melyekhez szín szükséges, azok a „második csoportba” sorolt gráfok (class two). (hu)
|
