Grafic Bull
| Grafic Bull | |
|
Reprezentarea graficului taurului. | |
| Număr de vârfuri | 5 |
|---|---|
| Numărul de margini | 5 |
| Distribuția gradului | 1 (2 vârfuri) 2 (1 vârf) 3 (2 vârfuri) |
| Ray | 2 |
| Diametru | 3 |
| Plasă | 3 |
| Automorfisme | 2 ( Z / 2 Z ) |
| Număr cromatic | 3 |
| Indicele cromatic | 3 |
| Proprietăți |
Unitate de distanță plană perfectă |
Graficul taur este, în teoria grafurilor , un grafic cu 5 noduri și 5 muchii. Poate fi construit prin adăugarea a două vârfuri la graficul de ciclu C 3 (triunghiul) și conectarea lor direct la două vârfuri distincte ale lui C 3 .
Denumirea graficului taur este utilizată în cadrul clasificării ISGCI (Sistemul de informații privind clasele de grafice și incluziunile acestora).
Proprietăți
Proprietăți generale
Diametrul graficului taurus, excentricitatea maximă a nodurilor sale, este de 3, ei raza , excentricitatea minimă a nodurilor sale, este 2 și sa ochiurilor de plasă , lungimea sa cel mai scurt ciclu , este 3. Acesta este d „un 1- grafic conectat la vârf și un grafic cu 1 margine conectată , adică este conectat și pentru a-l deconecta trebuie să fie privat de cel puțin 1 vârf sau 1 margine.
Este posibil să desenați graficul taurului pe un plan fără ca oricare dintre marginile sale să se intersecteze. Graficul taur este deci plan . Este, de asemenea, un grafic distanță-unitate : poate fi obținut dintr-o colecție de puncte pe planul euclidian conectând printr-o margine toate perechile de puncte aflându-se la o distanță de 1.
Colorare
Numărul cromatic al graficului taur este 3. Adică este posibil să-l colorați cu 3 culori, astfel încât două vârfuri conectate printr-o margine să fie întotdeauna de culori diferite. Acest număr este minim.
Indicele cromatic al graficului taurus este 3. Prin urmare , există un 3-colorare a marginilor grafului astfel încât cele două muchii incidente la același vertex sunt întotdeauna de culori diferite. Acest număr este minim.
Este posibil să se numere culorile distincte ale unui grafic, în funcție de numărul de culori permise. Aceasta dă o funcție polinomială, numită polinom cromatic al graficului. Acest polinom are rădăcini toate numere întregi pozitive sau zero , strict mai puțin de 3 grade și 5. Este egal cu: .
Există 2 grafice care sunt echivalente din punct de vedere cromatic cu graficul taur, adică având același polinom cromatic. Unul dintre ele este graficul lăcustelor .
Proprietăți algebrice
Grupul automorfisme grafului este un taur Abelian grup de ordine 2: ciclică Z / 2 Z .
Polinomul caracteristic al matricei de adiacență a graficului bull este: .
Grafice fără taur
Graficele fără taur sunt graficele care nu au graful taur ca subgraf indus . Ele au fost studiate în cadrul teoremei puternice a graficelor perfecte .
Prin definiție, graficele fără triunghi sunt grafice fără taur.
Vezi și tu
Legături interne
linkuri externe
- (ro) Eric W. Weisstein , Bull Graph ( MathWorld )
Referințe
- (în) ISGCI (Sistemul de informații cu privire la incluziunile clasei de grafice și a lor) Listă de grafice mici .
- Vaclac Chvátal și N. Sbihi , „ Graficele Berge fără taur sunt perfecte ”, Grafice și Combinatorie , vol. 3, n o 1, 1987, p. 127-139 ( DOI 10.1007 / BF01788536 )