Contele Desargues

Graficul Desargues  este un grafic cubic distanță-tranzitiv cu 20 de vârfuri și 30 de muchii [1] . Numit după Gerard Desargues . Apare în unele construcții combinatorii, are un grad ridicat de simetrie, este singurul cub parțial cubic neplanar cunoscut și este utilizat în bazele de date chimice.

Numele „Contele Desargues” este folosit și pentru graficul cu zece vârfuri, complementul grafului Petersen , care poate fi obținut ca jumătate din graficul Desargues cu 20 de vârfuri. [2]

Clădire

Există mai multe moduri diferite de a construi un grafic Desargues:

• Este un grafic Petersen generalizat G (10, 3). Pentru a obține graficul Desargues în acest fel, conectăm zece vârfuri într-un decagon regulat și conectăm cele zece vârfuri rămase într-o stea cu zece vârfuri, conectând perechi de vârfuri la o distanță de trei. Graficul Desargues este format din cele 20 de muchii ale acestor două poligoane, împreună cu alte 10 muchii care conectează punctele unui decagon de punctele corespunzătoare ale celuilalt.
• Este Contele Levi din configurația Desargues . Această configurație constă din zece puncte și zece linii care formează perspectiva a două triunghiuri , centrul lor de perspectivă și axa lor de perspectivă. Un grafic Desargues are un vârf pentru fiecare punct, un vârf pentru fiecare linie și o muchie pentru fiecare pereche punct-linie dacă punctul se află pe acea linie. Teorema lui Desargues , numită după matematicianul francez din secolul al XVII-lea Gérard Desargues , descrie setul de puncte și drepte care formează această configurație. Configurația și graficul și-au luat numele de la această teoremă.
• Este o acoperire dublă bipartită a grafului Petersen și se formează prin înlocuirea fiecărui vârf al grafului Petersen cu o pereche de vârfuri și fiecare muchie a grafului Petersen cu o pereche de muchii care se intersectează.
• Este un grafic Kneser bipartit H 5,2 . Vârfurile sale pot fi etichetate cu zece subseturi de două elemente și zece subseturi de trei elemente ale unei mulțimi de cinci elemente. În acest marcaj, o muchie conectează vârfuri dacă unul dintre seturile corespunzătoare este conținut în celălalt.
• Graficul Desargues este hamiltonian și poate fi construit folosind notația LCF : [5,−5,9,−9] 5 .

Proprietăți algebrice

Graficul Desargues este un grafic simetric  - are simetrii care duc orice vârf la orice alt vârf și orice muchie la orice altă muchie. Grupul său de simetrie are ordinul 240 și este izomorf cu produsul grupurilor simetrice cu 5 vârfuri și un grup de ordinul 2.

Se poate gândi la acest produs al grupurilor simetrice în ceea ce privește construirea unui graf Desargues - grupul simetric în 5 puncte este grupul de simetrie al configurației Desargues, iar subgrupul de ordinul doi schimbă rolurile vârfurilor care reprezintă configurația și vârfurile Desargues. care reprezintă linii. Alternativ, în ceea ce privește graficul Kneser bipartit, grupul simetric în cinci puncte acționează separat asupra submulțumirilor de două și trei elemente ale celor cinci puncte, iar complementul submulțimii formează un grup de ordinul doi care transformă un tip de subgrup în altul. Grupul simetric în cinci puncte este, de asemenea, grupul de simetrie a grafului Petersen, iar subgrupul de ordinul 2 schimbă vârfuri în fiecare pereche de vârfuri formată din capacul dublu.

Un grafic Peterson generalizat G ( n , k ) este tranzitiv la vârf dacă și numai dacă n = 10 și k = 2 sau dacă k 2 ≡ ±1 (mod n ) și este tranzitiv la muchie numai în următoarele șapte cazuri: ( n , k ) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). [3] Astfel, graficul Desargues este unul dintre cele șapte grafice Petersen generalizate simetrice. Aceste șapte grafice includ graficul cub G (4, 1), graficul Petersen G (5, 2), graficul Möbius-Cantor G (8, 3), graficul dodecaedru G (10, 2) și graficul Nauru G (12, 5).

Polinomul caracteristic al grafului Desargues este

Astfel, graficul Desargues este un graf întreg  - spectrul său este format în întregime din numere întregi.

Aplicații

În chimie , contele Desargues este cunoscut sub numele de Contele Desargues-Levy . Este folosit pentru a construi sistemul stereoizomeri al pentaliganzilor . În această aplicație, cele treizeci de muchii ale grafului corespund pseudo -rotațiilor ligandului. [4] [5]

Alte proprietăți

Graficul Desargues are un număr de intersecție de linie de 6 și este cel mai mic grafic cubic cu acel număr de intersecții (secvența A110507 în OEIS ). Este singurul cub parțial cubic neplanar cunoscut . [6]

Graficul Desargues are numărul cromatic 2, indicele cromatic 3, raza 5, diametrul 5 și circumferința 6. Este, de asemenea, un graf hamiltonian cu 3 vârfuri și 3 muchii .

Sunt cunoscute toate graficele distanțe cubice -regulate. [7] Comte Desargues este unul dintre acești conți.

Galerie

• Contele Desargues, colorat în așa fel încât să scoată în evidență diferitele cicluri.

• Indicele cromatic al contelui Desargues este 3.

• Numărul cromatic al contelui Desargues este 2.

Note

1. ^ Weisstein , Eric W. Desargues Graph  pe site- ul web Wolfram MathWorld .
2. ↑ ÎN Kagno. Graficele lui Desargues și Pappus și grupurile lor. — Jurnalul American de Matematică. - The Johns Hopkins University Press, 1947. - T. 69. - S. 859-863. - doi : 10.2307/2371806 . .
3. ↑ R. Frucht, J.E. Graver, M.E. Watkins. Grupurile graficelor Petersen generalizate // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 , nr. 02 . - S. 211-218 . - doi : 10.1017/S0305004100049811 .
4. ↑ Balaban. Grafice ale deplasărilor multiple de 1, 2 în ionii de carboniu și sistemele înrudite // Rev. cameră. Chim.. - 1966. - T. 11 . - S. 1205 .
5. ↑ Kurt Mislow. Rolul pseudorotației în stereochimia reacțiilor de deplasare nucleofile // Acc. Chim. Res .. - 1970. - T. 3 , nr. 10 . — S. 321–331 . doi : 10.1021 / ar50034a001 .
6. ↑ Sandi Klavžar, Alenka Lipovec. Cuburi parțiale ca grafice de subdiviziune și ca grafice Petersen generalizate // Matematică discretă . - 2003. - T. 263 . — S. 157–165 . - doi : 10.1016/S0012-365X(02)00575-7 .
7. ↑ A.E. Brouwer, A.M. Cohen, A. Neumaier. Grafice distanță-regular.- New York: Springer-Verlag, 1989.