definiție
Numărul cromatic al unui grafic este numărul minim de clase disjuncte de vârfuri ale graficului
(unde V este setul de vârfuri ale graficului) astfel încât vârfurile fiecărei clase să fie independente, adică orice margine a graficului să nu conecteze vârfuri din aceeași clasă.
Definiții înrudite
- Un grafic este numit K-colorabil. dacă numărul său cromatic nu depășește valoarea K. și K nu depășește numărul de vârfuri ale graficului. Asta este
- graficul este numit K-colorabil. dacă vârfurile sale pot fi colorate K în culori diferite, astfel încât marginile să aibă capete diferite.
- Un grafic K-cromatic este un grafic al cărui număr cromatic este K. Asta este,
- graficul este numit K-cromatic. dacă nodurile sale pot fi vopsite cu cel puțin K culori, astfel încât marginile să aibă capete diferite. K este numit numărul cromatic al acestui grafic.
Rig colorare
marginea de culoare a unui grafic cubic
Clasa cromatică a graficului G este numărul minim de culori în care marginile graficului G pot fi colorate astfel încât marginile adiacente să aibă culori diferite. Este notat cu χ '(G). Problema de colorare a marginilor unui grafic arbitrar plan cubic fără poduri în trei culori este echivalentă celebrului Problem de patru culori. Culoarea de margine determină 1-factorizarea graficului.
Polinomul cromatic
Dacă luăm în considerare numărul de culori diferite ale unui grafic marcat ca funcție de numărul de culori disponibil t. atunci se pare că această funcție va fi întotdeauna un polinom în t. Acest fapt a fost descoperit de Birkhoff și Lewis [1] atunci când încerca să dovedească ipoteza a patru culori.
Polinoamele cromatice ale unor grafice
Valoare pentru teoria graficelor
Setul de probleme profunde ale teoriei grafurilor poate fi formulat cu ușurință în termeni de colorare. Cea mai faimoasă dintre aceste probleme este Problema celor patru culori. acum este rezolvată, cu toate acestea există o nouă, de exemplu, generalizarea Problemei a patru culori, ipoteza lui Hadwiger.
literatură
"Teoria grafurilor" - O. Ore. traducere din engleză de IN Vrublevskaya, editat de NN Vorobyov, Editura Nauka, Moscova 1986
- ↑ Birkhoff, G. D. și Lewis, D. C. "Polinoame cromatice." Trans. Amer. Math. Soc. 60, 355-451, 1946.
Urmăriți ce este "Earl Chromatic" în alte dicționare:
Contele lui Petersen - Acest articol ar trebui să fie vikifitsirovat. Completați-l conform regulilor articolelor ... Wikipedia
Graficul complet - Vertex n Ribs Diametrul 1 Automorphism ... Wikipedia
Numărul cromatic - 3 culori ale graficului Petersen Numărul cromatic al graficului G numărul minim de culori în care să picteze topurile ... Wikipedia
Ipoteza lui Hadwiger - Nu trebuie confundată cu problema lui Nelson Erd Haș Hadwiger. Conjectura lui Hadwiger este una dintre ipotezele nerezolvate ale teoriei grafurilor. Se formulează după cum urmează: fiecare graf cromatic k este contractat la un grafic complet pe noduri. ... ... Wikipedia
Probleme nerezolvate în matematică - probleme nerezolvate (sau probleme deschise) care au fost luate în considerare de matematicieni, dar care nu au fost încă rezolvate. Ele au adesea forma unor ipoteze care se presupune că sunt adevărate, dar au nevoie de dovadă. În lumea științifică, practica este populară ... ... Wikipedia
Probleme matematice deschise - Probleme matematice deschise (nerezolvate) ale unei probleme considerate de matematicieni, dar care nu au fost încă rezolvate. Există adesea forma de ipoteze care se presupune că sunt adevărate, dar au nevoie de dovadă. În lumea științifică este populară ... ... Wikipedia
Probleme nerezolvate în matematică - probleme nerezolvate (sau probleme deschise) care au fost luate în considerare de matematicieni, dar care nu au fost încă rezolvate. Ele au adesea forma unor ipoteze care se presupune că sunt adevărate, dar au nevoie de dovadă. În lumea științifică, practica este populară ... ... Wikipedia
Probleme nerezolvate în teoria numerelor - probleme nerezolvate (sau probleme deschise) care au fost luate în considerare de matematicieni, dar care nu au fost încă rezolvate. Ele au adesea forma unor ipoteze care se presupune că sunt adevărate, dar au nevoie de dovadă. În lumea științifică, practica este populară ... ... Wikipedia