Back Petersenův graf Czech Petersen-Graph German Petersen graph English Grafo de Petersen Spanish Peterseni graaf Estonian گراف پترسن Persian Graphe de Petersen French Petersenov graf Croatian Petersen-gráf Hungarian Graf Petersen ID
En l'àmbit matemàtic de la teoria de grafs, el graf de Petersen és un graf no dirigit amb 10 vèrtexs i 15 arestes. És un graf petit que serveix com a exemple i com a contraexemple per a molts problemes de teoria de grafs. El graf de Petersen rep aquest nom pel matemàtic danès Julius Petersen, qui el va construir l'any 1898 com el més petit graf cúbic sense arestes de tall que no admet una 3-aresta-coloració.[1]
Tot i que s'acostuma a atribuir el descobriment del graf a Petersen, de fet va sorgir 12 anys abans en una publicació d'Alfred Kempe.[2] Kempe observà que els seus vèrtexs poden representar les 10 rectes de la configuració de Desargues, i les seves arestes representen parells de rectes que no s'intersecten a un dels 10 punts de la configuració.
Donald Knuth afirma que el graf de Petersen és
| « | (anglès) a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general.
|
(català) una configuració notable que serveix com a contraexemple a moltes prediccions optimistes sobre allò que hauria de ser cert per a grafs en general. | » |
| — Donald Knuth, The Art of Computer Programming[3]
| |||
- ↑ Brouwer, Andries E. «The Petersen graph». Technische Universiteit Eindhoven, Faculteit Wiskunde en Informatica.
- ↑ Kempe, 1886.
- ↑ Knuth, Donald E. The Art of Computer Programming; volum 4, pre-fascicle 0A. Secció 7: Introduction to combinatorial searching.