Graf Petersena.html



Graf Petersena

Graf Petersena narysowany z dwoma przecięciami.

Graf Petersena narysowany tak, że wszystkie krawędzie są tej samej długości.

Graf Petersena to graf o ciekawych własnościach często używany w teorii grafów. Nazwa pochodzi od nazwiska matematyka J. Petersena, któremu przypisuje się pierwszą publikację na temat grafu w 1898 roku.

edytuj Własności

Graf Petersena...

• jest silnie regularny stopnia 3.
• jest trójspójny i trójspójny krawędziowo.
• ma ścieżkę Hamiltona ale nie ma cyklu Hamiltona.
• jest grafem trójdzielnym.
• jest dopełnieniem grafu krawędziowego grafu K₅.
• jest symetryczny, to znaczy krawędziowo tranzytywny i wierzchołkowo tranzytywny.
• nie jest grafem planarnym.

Własności grafu Petersena:

edytuj Inne cechy

• jest najmniejszym żmirłaczem.
• jest najmniejszym grafem kubicznym bez mostów i cykli Hamiltona.
• jest największym grafem kubicznym o średnicy 2.
• jest najmniejszym graferm hipohamiltonowskim.