Mesh (teoria graficelor)

În teoria graficelor , rețeaua unui grafic este lungimea celui mai scurt dintre ciclurile sale . Un grafic aciclic este, în general, considerat a avea o rețea infinită (sau, pentru unii autori, o rețea de -1).

Definiție

Plasa unui grafic este lungimea cea mai scurtă dintre ei cicluri .

Exemple

• Graficul Petersen are ochiuri de 5 și este o cușcă.

• Grafic Heawood are o plasă de 6 și o cușcă.

• Frucht Graph conține triunghiuri, are ochiuri de 3.

Familii asociate

• A ( r , g ) - cușca este un grafic regulat al gradului r și al ochiului minim g în număr de vârfuri.
• Graficele cu o plasă mai mare sau egală cu patru sunt grafice fără triunghi .

Legătură cu colorare

Există teoreme despre relația dintre plasă și numărul cromatic de grafice. De exemplu, o teoremă a lui Paul Erdős publicată în 1959 arată că pentru toate g și k , există un grafic cu plasă cel puțin g și număr cromatic cel puțin k . De exemplu, graficul Grötzsch are o plasă de 4 și un număr cromatic de 4. Dovada acestei teoreme utilizează metoda probabilistică .

Note și referințe

1. (în) Reinhard Diestel , Graph Theory [ ediții cu amănuntul ] , p.  11.
2. Paul Erdős , „  Teoria graficului și probabilitatea  ”, Canadian Journal of Mathematics , vol.  11, 1959, p.  34-38 ( DOI  10.4153 / CJM-1959-003-9 ).
3. Frédéric Havet, „  Metodă probabilistică pentru colorarea graficelor: grafic cu plasă mare și număr cromatic mare (prezentare)  ” , pe Laboratorul de informatică, robotică și microelectronică din Montpellier ,2009.