Adnotare: Colorarea Ribului. Probleme pentru graficele cu marginile colorate și proprietățile care rezultă din ele. Problema triunghiurilor nelimitate cu laturi monocrome.
Rig colorare
Un grafic este numit graf de margine colorat. dacă marginile sale pot fi vopsite cu culori în așa fel încât nici două muchii adiacente să nu fie de aceeași culoare. Dacă graficul este marcat pe margine, dar nu este colorat pe muchie, atunci se numește o clasă cromatică sau un indice cromatic. sau un număr cromatic de margine al graficului. Se folosește o înregistrare. Figura arată un grafic pentru care.
Este clar că dacă cea mai mare dintre gradele vârfurilor unui grafic este egală cu, atunci. Următorul rezultat, cunoscut ca teorema lui Wiesing, oferă estimări precise pentru clasa cromatică a graficului. Dovada acestei teoreme poate fi găsită în Ore (Ore O. Problema cu patru culori., Academic Press, New York, 1967).
Teorema 7.1 (Vizing, 1964) Să presupunem că într-un grafic fără bucle este cea mai mare dintre gradele vârfurilor.
Sarcina de a determina ce grafice au o clasă cromatică și care nu sunt rezolvate. Cu toate acestea, în unele cazuri speciale, rezultatele corespunzătoare sunt ușoare. De exemplu, sau 3, în funcție de dacă este ciudat sau par și când. Clasele cromatice de grafice complete și grafice bipartite complete sunt, de asemenea, ușor de calculat.
Articole similare
-
Cunoștințe, prelegere, mecanisme de apărare ale sistemelor de operare
-
Know-how, prelegere, raport semnal-zgomot în sistemele de comunicații digitale
Trimiteți-le prietenilor: