Graafiteoriassa Petersenin graafiperhe on seitsemän suuntaamattoman graafin joukko , mukaan lukien Petersenin graafi ja täydellinen graafi K 6 . Petersenin perhe on nimetty tanskalaisen matemaatikon Julius Petersenin mukaan, koska Petersenin graafi sisältyy joukkoon.
Mikä tahansa Petersen-perheen graafista voidaan muuntaa mihin tahansa muuhun Δ-Y- tai Y-Δ-perheen graafiksi muunnoksilla , operaatioilla, joissa kolmio korvataan asteen 3 kärjellä tai päinvastoin. Nämä seitsemän graafia muodostavat kiellettyjä sivuja linkittämättömille upotetuille graafiille , kaavioille, jotka voidaan upottaa kolmiulotteiseen avaruuteen siten, että kaksi sykliä ei muodosta linkkiä (solmuteorian merkityksessä) [1] . He ovat myös kiellettyjen alaikäisten joukossa YΔY-pelkistävissä graafissa [2] [3] .
Petersen-perheen määrittelyssä käytetyt Δ-Y ja Y-Δ muunnokset ovat seuraavat:
Näitä muunnoksia kutsutaan niin, koska symboli Δ näyttää kolmiolta ja symboli Y näyttää kärjeltä, jolla on kolme reunaa. Vaikka nämä operaatiot voisivat periaatteessa johtaa multigrafeihin , ne eivät Petersenin perheessä. Koska nämä operaatiot säilyttävät graafin reunojen lukumäärän, yhdestä alkuperäisestä graafista G voidaan muodostaa vain äärellinen määrä graafia tai multigrafeja yhdistämällä Δ-Y- ja Y-Δ muunnoksia.
Petersen-perhe koostuu kaikista graafista, jotka voidaan saada Petersen-graafista Δ-Y- ja Y-Δ-muunnosten yhdistelmällä. Perheessä on seitsemän graafia ja se sisältää täydellisen graafin K 6 kuudella pisteellä, kahdeksan kärjen graafin, joka on muodostettu poistamalla yksi reuna täydellisestä kaksiosaisesta graafista K 4,4 , ja täydellisen kolmiosaisen graafin, jossa on seitsemän kärkeä K 3 ,3,1 .
Graafin G molli on toinen graafi, joka on muodostettu graafista G supistamalla ja poistamalla reunoja. Kuten Robertson-Seymourin lause osoittaa , monet tärkeät graafiperheet voidaan luonnehtia rajallisella kiellettyjen alaikäisten joukolla . Esimerkiksi Wagnerin lauseen mukaan tasograafit ovat täsmälleen niitä graafia, jotka eivät sisällä kokonaista graafia K 5 eivätkä täydellistä kaksiosaista graafia K 3,3 sivuina .
Neil Robertson Paul Seymour ja Robin Thomas käyttivät Petersen -perhettä osana samanlaista luonnehdintaa linkittämättömistä upotetuista graafista, toisin sanoen graafista, joka voidaan upottaa euklidiseen avaruuteen siten, että mikä tahansa kaavion sykli on kaavion raja. (topologinen) levy, jota ei ole leikattu missään muussa kaavion osassa [1] . Sachs Horst tutki tällaisia upotuksia aiemmin ja osoitti, että seitsemässä Petersen-perheen kaaviossa ei ole tällaisia upotuksia, ja esitti kysymyksen graafien luonnehtimisesta linkittämättömillä upotuksilla luettelemalla kiellettyjä aligraafia [4] . Robertson ym. ratkaisivat Sachsin kysymyksen osoittamalla, että linkkittömät upotettavat graafit ovat juuri niitä kaavioita, joissa ei ole Petersenin perheen jäseniä alaikäisinä.
Petersen-perheen graafit sisältyvät toisen graafiperheen, YΔY-pelistettävien graafien, kiellettyihin alaikäisiin. Yhdistetty graafi on YΔY-pelkistävä, jos se voidaan muuntaa yhdeksi kärjeksi useilla vaiheilla, joista kukin on Δ-Y tai Y-Δ muunnos, joka poistaa silmukan tai usean reunan, poistaa kärkipisteen, jolla on yksi naapuri. , ja korvataan toisen asteen kärki ja kaksi vierekkäistä ripaa yhdellä ripauksella. Esimerkiksi täydellinen K 4 -graafi voidaan pelkistää yhdeksi pisteeksi Y-Δ-muunnolla, joka muuttaa sen kolmioksi, jossa on kaksoisreunat. Kun on poistettu kolme kaksoisreunaa, muunnettu Δ-Y, joka muuttaa kolmion kynneksi (kolme reunaa yhdellä yhteisellä kärjellä) K 1,3 , ja poistamalla kynnen riippuvat kärjet, graafista tulee kärki. Kukin Petersen-perheen graafista muodostaa YΔY-pelkistyvien graafien perheen minimikielletyn mollin [2] . Neil Robertson kuitenkin antaa esimerkin kärkigraafista (linkitön upotettava graafi, joka muodostetaan lisäämällä yksi kärki tasograafiin), joka ei ole YΔY-pelkistävä. Tämä osoittaa, että YΔY-pelkistettävät graafit muodostavat oman linkittömien upotettavien graafien alaluokkansa, mutta niissä on Petersen-perheen graafien lisäksi muita kiellettyjä alaikäisiä [2] . Itse asiassa, kuten Yaming Yu on osoittanut, on ainakin 68 897 913 652 kiellettyä alaikäistä YΔY-vähennettyjen graafien osalta Petersenin perheen seitsemän graafin lisäksi [3] .