I grafteori er en Petersen-familie af grafer et sæt af syv urettede grafer , inklusive Petersen-grafen og den komplette graf K 6 . Familien Petersen er opkaldt efter den danske matematiker Julius Petersen , fordi Petersen-grafen indgår i sættet.
Enhver af graferne i Petersen-familien kan transformeres til en hvilken som helst anden graf i Δ-Y- eller Y-Δ-familien ved transformationer , operationer, hvor en trekant erstattes af et toppunkt på grad 3, eller omvendt. Disse syv grafer danner forbudte mindreårige for ikke- linkede indlejrbare grafer , grafer, der kan indlejres i tredimensionelt rum på en sådan måde, at ikke to cyklusser danner et link (i betydningen knudeteori) [1] . De er også blandt de forbudte mindreårige af YΔY-reducerbare grafer [2] [3] .
Δ-Y- og Y-Δ-transformationerne anvendt i definitionen af Petersen-familien er som følger:
Disse transformationer kaldes det, fordi symbolet Δ ligner en trekant, og symbolet Y ligner et toppunkt med tre kanter. Selvom disse operationer i princippet kan føre til multigrafer , gør de det ikke i familien Petersen. Da disse operationer bevarer antallet af kanter i grafen, kan kun et begrænset antal grafer eller multigrafer dannes ud fra en enkelt indledende graf G ved en kombination af Δ-Y og Y-Δ transformationer.
Petersen-familien består af alle grafer, der kan opnås fra Petersen-grafen ved en kombination af Δ-Y og Y-Δ transformationerne. Der er syv grafer i familien, og den inkluderer en komplet graf K 6 med seks toppunkter, en graf med otte hjørner dannet ved at fjerne en kant fra en komplet todelt graf K 4,4 og en komplet tredelt graf med syv toppunkter K 3 ,3,1 .
En mindre af en graf G er en anden graf dannet ud fra en graf G ved at trække kanter sammen og fjerne. Som Robertson-Seymour-sætningen viser , kan mange vigtige familier af grafer karakteriseres ved et begrænset sæt af forbudte mindreårige . For eksempel er plane grafer ifølge Wagners sætning præcis de grafer, der hverken indeholder den komplette graf K 5 eller den komplette todelte graf K 3,3 som mindre .
Neil Robertson Paul Seymour og Robin Thomas brugtePetersen-familien som en del af en lignende karakterisering af ikke-linkede indlejrbare grafer, det vil sige grafer, der kan indlejres i det euklidiske rum på en sådan måde, at enhver cyklus i grafen er grænsen for en (topologisk) disk, der ikke er gennemskåret ingen anden del af grafen [1] . Sachs Horst studerede sådanne indlejringer før og viste, at syv grafer af Petersen-familien ikke har sådanne indlejringer, og rejste spørgsmålet om at karakterisere grafer med ikke-linkede indlejringer ved at liste forbudte undergrafer [4] . Robertson et al. løste Sachs' spørgsmål ved at vise, at link-fri indlejrbare grafer er præcis de grafer, der ikke har medlemmer af Petersen-familien som mindreårige.
Petersen-familiens grafer er inkluderet i de forbudte mindreårige i en anden familie af grafer, YΔY-reducerbare grafer. En forbundet graf er YΔY-reducerbar, hvis den kan transformeres til et enkelt toppunkt ved en sekvens af trin, som hver er en Δ-Y eller Y-Δ transformation, fjernelse af en sløjfe eller multiple kant, fjernelse af et toppunkt med en enkelt nabo , og udskiftning af et toppunkt af grad to og to tilstødende ribber med en ribbe. For eksempel kan en komplet K 4 - graf reduceres til et enkelt toppunkt ved hjælp af Y-Δ-transformationen, som gør den til en trekant med dobbeltkanter. Efter at have fjernet tre dobbeltkanter, transformeret Δ-Y, som omdanner trekanten til en klo (tre kanter med et fælles toppunkt) K 1,3 og fjernet de hængende toppunkter på kloen, bliver grafen til et toppunkt. Hver af graferne i Petersen-familien danner den minimale forbudte minor for familien af YΔY-reducerbare grafer [2] . Neil Robertson giver dog et eksempel på en toppunktsgraf (en linkløs indlejrbar graf dannet ved at tilføje et toppunkt til en plan graf), som ikke er YΔY-reducerbar. Dette viser, at YΔY-reducerbare grafer danner deres egen underklasse af link-fri indlejrbare grafer, men ud over grafer af Petersen-familien har de yderligere forbudte mindreårige [2] . Faktisk, som Yaming Yu har vist, er der mindst 68.897.913.652 forbudte mindreårige til YΔY-reducerbare grafer, foruden de syv grafer fra Petersen-familien [3] .