În teoria grafurilor, o familie de grafuri Petersen este un set de șapte grafuri nedirecționate , inclusiv graful Petersen și graful complet K 6 . Familia Petersen este numită după matematicianul danez Julius Petersen , deoarece graficul Petersen este inclus în set.
Oricare dintre graficele din familia Petersen poate fi transformat în orice alt grafic din familia Δ-Y sau Y-Δ prin transformări , operații în care un triunghi este înlocuit cu un vârf de gradul 3, sau invers. Aceste șapte grafice formează minori interziși pentru graficele încorporabile nelegate , grafice care pot fi încorporate în spațiul tridimensional în așa fel încât două cicluri să nu formeze o legătură (în sensul teoriei nodurilor) [1] . Ei sunt, de asemenea, printre minorii interziși ai graficelor reductibile YΔY [2] [3] .
Transformările Δ-Y și Y-Δ utilizate în definiția familiei Petersen sunt după cum urmează:
Aceste transformări sunt numite astfel deoarece simbolul Δ arată ca un triunghi, iar simbolul Y arată ca un vârf cu trei muchii. În timp ce aceste operațiuni ar putea, în principiu, să conducă la multigrafe , ele nu o fac în familia Petersen. Deoarece aceste operații păstrează numărul de muchii din grafic, doar un număr finit de grafice sau multigrafe poate fi format dintr-un singur grafic inițial G printr-o combinație de transformări Δ-Y și Y-Δ.
Familia Petersen este formată din toate graficele care pot fi obținute din graficul Petersen printr -o combinație a transformărilor Δ-Y și Y-Δ. Există șapte grafice în familie și include un grafic complet K 6 cu șase vârfuri, un grafic cu opt vârfuri format prin eliminarea unei muchii dintr-un grafic bipartit complet K 4,4 și un grafic tripartit complet cu șapte vârfuri K 3 ,3,1 .
Un minor al unui grafic G este un alt grafic format dintr-un grafic G prin contractarea și îndepărtarea muchiilor. După cum arată teorema Robertson-Seymour , multe familii importante de grafice pot fi caracterizate printr-un set finit de minori interziși . De exemplu, conform teoremei lui Wagner , graficele plane sunt exact graficele care nu conțin nici graficul complet K 5 , nici graficul complet bipartit K 3,3 ca minore .
Neil Robertson Paul Seymour și Robin Thomas aufolosit familia Petersen ca parte a unei caracterizări similare a graficelor încorporabile nelegate , adică grafice care pot fi încorporate în spațiul euclidian în așa fel încât orice ciclu din grafic să fie limita unui disc (topologic) care nu este intersectat cu nicio altă parte a graficului [1] . Sachs Horst a studiat mai înainte astfel de înglobări și a arătat că șapte grafice ale familiei Petersen nu au astfel de înglobări și a ridicat problema caracterizării graficelor cu înglobări nelegate prin enumerarea subgrafelor interzise [4] . Robertson și colab. au rezolvat întrebarea lui Sachs arătând că graficele încorporabile fără linkuri sunt exact acele grafice care nu au membri ai familiei Petersen ca minori.
Graficele familiei Petersen sunt incluse în minorii interziși ai unei alte familii de grafice, graficele reductibile YΔY. Un graf conectat este YΔY-reductibil dacă poate fi transformat într-un singur vârf printr-o succesiune de pași, fiecare dintre acestea fiind o transformare Δ-Y sau Y-Δ, eliminând o buclă sau o muchie multiplă, eliminând un vârf cu un singur vecin , și înlocuirea unui vârf de gradul doi și a două nervuri adiacente cu o nervură. De exemplu, un grafic K 4 complet poate fi redus la un singur vârf folosind transformarea Y-Δ, care îl transformă într-un triunghi cu muchii duble. După îndepărtarea a trei muchii duble, transformând Δ-Y, care transformă triunghiul într-o gheară (trei muchii cu un vârf comun) K 1,3 , și îndepărtarea vârfurilor suspendate ale ghearei, graficul se transformă într-un vârf. Fiecare dintre graficele familiei Petersen formează minorul minim interzis pentru familia de grafice reductibile YΔY [2] . Cu toate acestea, Neil Robertson oferă un exemplu de graf de vârfuri (un graf de încorporare fără legături format prin adăugarea unui vârf la un graf plan) care nu este YΔY-reductibil. Acest lucru arată că graficele reductibile YΔY formează propria lor subclasă de grafice încorporabile fără legături, dar, pe lângă graficele familiei Petersen, au minori suplimentari interziși [2] . De fapt, după cum a arătat Yaming Yu, există cel puțin 68.897.913.652 de minori interziși pentru graficele reductibile YΔY, în plus față de cele șapte grafice ale familiei Petersen [3] .