¡Haz fotografías sobre tu cultura local, ayuda a Wikipedia y gana!
Contraer
Grafo de Petersen
Ir a la navegación
Ir a la búsqueda
Grafo de Petersen
Petersen1 [Link]
El grafo de Petersen es comúnmente dibujado como un pentágono con una estrella de 5
puntas dentro.
Nombre en honor a Julius Petersen
Vértices 10
Aristas 15
Radio 2
Diámetro 2
Cintura 5
Automorfismos 120 (S5)
Número cromático 3
Índice cromático 4
Propiedades Cúbico
Fuertemente regular
Distancia transitiva
Snark
[editar datos en Wikidata]
En el campo matemático de la teoría de grafos, el grafo de Petersen es un grafo no
dirigido con 10 vértices y 15 aristas . Es un grafo pequeño que sirve como ejemplo
y contraejemplo para muchos problemas en la teoría de grafos. El grafo de Petersen
lleva el nombre de Julius Petersen, quien en 1898 lo construyó para ser el grafo
cúbico sin puentes más pequeño que no se puede 3-colorear. 1
Aunque comúnmente se le da crédito a Petersen, en realidad apareció por primera vez
12 años antes, en un artículo de A. B. Kempe. Kempe observó que sus vértices pueden
representar las diez líneas de la configuración de Desargues, y sus bordes
representan pares de líneas que no se encuentran en uno de los diez puntos de la
configuración.
Donald Knuth afirma que el grafo de Petersen es "una configuración notable que
sirve como contraejemplo a muchas predicciones optimistas sobre qué podría ser
cierto en un grafo en general."2
Índice
1 Características
2 Equivalencias
3 Simetrías
4 Ciclos y caminos hamiltonianos
5 Coloración
6 La conjetura de coloración de Petersen
7 Grafos relacionados
8 Referencias
Características
Es un grafo regular de grado 3.
Dos vértices adyacentes no tienen vecinos en común, pero, no es bipartito, pues
existen varios ciclos de longitud impar.
Dos vértices no adyacentes tienen exactamente un vecino en común.
Equivalencias
El grafo de Petersen no es plano. Cualquier grafo no plano tiene como menores o al
grafo completo K 5 {\displaystyle K_{5}} o al grafo bipartito completo K 3 , 3 {\
displaystyle K_{3,3}}, pero el grafo de Petersen tiene a ambos como menores. El
menor K 5 {\displaystyle K_{5}} se puede format contrayendo las aristas de un
apareamiento perfecto, por ejemplo las cinco aristas cortas de la primera imagen.
El menor K 3 , 3 {\displaystyle K_{3,3}} se puede format eliminando un vértice (por
ejemplo el vértice central de la representación 3-simétrica) y contrayendo una
arista incidente a cada vecino del vértice eliminado. La representación planar
simétrica más común del grafo de Petersen (como un pentagrama contenido en un
pentágono) se cruza cinco veces. Sin embargo, esta no es la mejor representación
para ahorrar cruces; existe otra representación (la expuesta en la imagen
siguiente) con tan sólo dos cruces. Como no es planar, tiene al menos un cruce en
cualquier representación, y el número mínimo de cruces en cualquier representación
es exactamente 2. El grafo de Peterson también se puede dibujar en el plano de
forma que todas las aristas tengan igual longitud. Es por tanto un grafo de
distancia unidad. La superficie no orientable más simple en la cual el grafo de
Petersen puede ser incrustado es el plano proyectivo.
Simetrías
El grafo de Petersen es fuertemente regular. Es también simétrico, por lo que es
arista-transitivo y vértice-transitivo. En concreto, es 3-arco-transitivo: todo
camino dirigido de tres aristas en el grafo de Petersen puede ser transformado en
cualquier otro camino similar por una simetría del grafo. El grupo automórfico del
grafo de Petersen es el grupo simétrico S 5 {\displaystyle S_{5}}: la acción de S 5
{\displaystyle S_{5}} en el grafo de Petersen surge de su construcción como un
Grafo de Kneser. Todo homomorfismo del grafo de Petersen a sí mismo que no
identifica vértices adyacentes es un automorfismo. Como se puede observar en las
figuras, las representaciones del grafo de Petersen pueden mostrar 5-simetría o 3-
simetría, pero no se puede dibujar el grafo de Petersen en el plano de forma que la
representación posea el grupo de simetría completo del grafo. A pesar de su alto
grado de simetría, el grafo de Petersen no es un grupo de Cayley. Es el grafo
vértice-transitivo más pequeño que no es un grupo de Cayley.
Ciclos y caminos hamiltonianos
El grafo de Petersen tiene un camino hamiltoniano pero no un ciclo hamiltoniano. Es
el grafo cúbico sin puente más pequeño sin ciclo hamiltoniano. Es hipoamiltoniano,
lo que significa que aunque no tiene un ciclo hamiltoniano, al eliminar cualquier
vértice se convierte en hamiltoniano, y es el grafo hipoamiltoniano más pequeño.
Como un grafo finito conectado vértice-transitivo que no tiene un ciclo
Hamiltoniano, el grafo Petersen es un contra-ejemplo a una variante de la conjetura
de Lovász, pero la formulación canónica de la conjetura pide un camino Hamiltoniano
y es verificada por el grafo de Petersen.
Sólo se conocen cinco grafos transitivos de vértices conectados sin ciclos
hamiltonianos: el grafo completo K2, el grafo de Petersen, el grafo de Coxeter y
dos grafos derivados de los grafso de Petersen y Coxeter sustituyendo cada vértice
por un triángulo. Si G es un grafo r-regular conectado a dos vértices, con un
máximo de 3r + 1, entonces G es hamiltoniano o G es el grafo de Petersen.
Para ver que el grafo de Petersen no tiene un ciclo C hamiltoniano, considere los
bordes en el corte desconectando el ciclo interno de 5 ciclos del externo. Si hay
un ciclo hamiltoniano, se debe elegir un número par de estos bordes. Si sólo se
eligen dos de ellos, sus vértices finales deben estar adyacentes en los dos 5
ciclos, lo que no es posible. De ahí que se hayan elegido 4 de ellos. Supongamos
que no se elige el borde superior del corte (todos los demás casos son iguales por
simetría). De los 5 bordes del ciclo exterior, se deben elegir los dos bordes
superiores, no se deben elegir los dos bordes laterales y, por lo tanto, se debe
elegir el borde inferior. Los dos bordes superiores del ciclo interior deben ser
elegidos, pero esto completa un ciclo no expansivo, que no puede ser parte de un
ciclo hamiltoniano. Alternativamente, también podemos describir las gráficas de
diez vértices y 3-regulares que sí tienen un ciclo hamiltoniano y mostrar que
ninguna de ellas es el grafo de Petersen, encontrando un ciclo en cada una de ellas
que es más corto que cualquier ciclo en el grafo de Petersen. Cualquier grafo
tridimensional de diez versículos hamiltonianos consta de un ciclo de diez
versículos C más cinco cuerdas. Si alguna cuerda conecta dos vértices a una
distancia de dos o tres a lo largo de C uno del otro, el grafo tiene un ciclo de 3
o 4 ciclos, y por lo tanto no puede ser el grafo de Petersen. Si dos cuerdas
conectan vértices opuestos de C a vértices a una distancia de cuatro a lo largo de
C, hay de nuevo un ciclo de 4. El único caso que queda es una escalera Möbius
formada por la conexión de cada par de vértices opuestos por una cuerda, que de
nuevo tiene un ciclo de 4. Dado que el grafo de Petersen tiene una circunferencia
de cinco, no puede formarse de esta manera y no tiene un ciclo hamiltoniano.
Coloración
Coloración de los lados del grafo de Petersen formada por cuatro colores.
Coloración de los vértices del grafo de Petersen formada por 3 colores.
El grafo de Petersen tiene el número cromático 3, lo que significa que sus vértices
pueden ser coloreados con tres colores (pero no con dos) de manera que ningún borde
conecte vértices del mismo color. Tiene una lista de coloración formada por 3
colores, según el teorema de Brooks.
El grafo de Petersen tiene un índice cromático 4; la coloración de los bordes
requiere cuatro colores. Como un grafo cúbico sin puente conectado con índice
cromático cuatro, el grafo de Petersen es un snark. Es el snark más pequeño
posible, y fue el único conocido desde 1898 hasta 1946. El teorema del snark,
conjeturado por W. T. Tutte y anunciado en 2001 por Robertson, Sanders, Seymour y
Thomas, afirma que cada snark tiene el grafo de Petersen como un menor.
Además, el grafo tiene un índice cromático fraccionario 3, lo que demuestra que la
diferencia entre el índice cromático y el índice cromático fraccionario puede ser
tan grande como 1.
El número Thue (una variante del índice cromático) del grafo de Petersen es 5.
El grafo de Petersen requiere al menos tres colores en cualquier coloración que
rompa todas sus simetrías; es decir, su número distintivo es tres. Excepto en los
grafos completos, que son los únicos grafo de Kneser cuyo número distintivo no es
dos.
La conjetura de coloración de Petersen
Según DeVos, Nesetril y Raspaud, "Un ciclo de un grafo G es un conjunto C ⊆ {\
displaystyle \subseteq } E(G) para que cada vértice del grafo (V(G),C) tenga un
grado parecido. Si G,H son grafos, definimos un mapa φ: E(G) -> E(H) que sea ciclo
continuo si la pre-imagen de cada ciclo de H es un ciclo de G. Una fascinante
conjetura de Jaeger afirma que cada grafo sin puente tiene un ciclo continuo de
mapeo al grafo de Petersen. Jaeger demostró que si esta conjetura es cierta,
entonces también lo son la conjetura de 5 ciclos de doble cubierta y la conjetura
de Berge-Fulkerson".
Grafos relacionados
La familia de Petersen
El grafo generalizado de Petersen G(n,k) se forma conectando los vértices de un
polígono regular de n lados a los vértices correspondientes de una estrella con el
símbolo de Schläfli {n/k}.3 Por ejemplo, en esta notación, el grafo de Petersen es
G(5,2): puede formarse conectando los vértices correspondientes de un pentágono y
una estrella de cinco puntas, y los bordes de la estrella conectan cada dos
vértices. Los grafos generalizados de Petersen también incluyen el prisma-n G(n,1),
el grafo de Dürer G(6,2), el grafo de Möbius-Kantor G(8,3), el dodecaedro G(10,2),
el grafo de Desargues G(10,3) y el grafo de Nauru G(12,5).
La familia de Petersen está formada por los siete grafos que pueden ser formados a
partir del grafo Petersen por cero o más aplicaciones de transformaciones Δ-Y o Y-
Δ. El grafo completo K6 también pertenece a la familia de Petersen.
El grafo de Clebsch contiene muchas copias del grafo de Petersen como subgrafos
inducidos: por cada vértice v del grafo de Clebsch, los diez no vecinos de v
inducen una copia del grafo de Petersen.
Referencias
Brouwer, Andries E., The Petersen graph.
Knuth, Donald E., The Art of Computer Programming; volumen 4, pre-fascículo 0A (en
inglés). A draft of section 7: Introduction to combinatorial searching.
Coxeter (1950); Watkins (1969).
Control de autoridades
Proyectos Wikimedia Wd Datos: Q835614 Commonscat Multimedia: Petersen graph /
Q835614
Categorías:
Grafos individualesGrafos regulares
Menú de navegación
No has accedido
Discusión
Contribuciones
Crear una cuenta
Acceder
Artículo
Discusión
Leer
Editar
Ver historial
Portada
Portal de la comunidad
Actualidad
Cambios recientes
Páginas nuevas
Página aleatoria
Ayuda
Donaciones
Notificar un error
Herramientas
Lo que enlaza aquí
Cambios en enlazadas
Subir archivo
Páginas especiales
Enlace permanente
Información de la página
Citar esta página
Elemento de Wikidata
Imprimir/exportar
Crear un libro
Descargar como PDF
Versión para imprimir
En otros proyectos
Wikimedia Commons
En otros idiomas
Deutsch
English
Français
Bahasa Indonesia
日本語
한국어
Português
Русский
中文
Editar enlaces
Esta página se editó por última vez el 7 sep 2022 a las 11:32.
El texto está disponible bajo la Licencia Creative Commons Atribución Compartir
Igual 3.0; pueden aplicarse cláusulas adicionales. Al usar este sitio, usted acepta
nuestros términos de uso y nuestra política de privacidad.
Wikipedia® es una marca registrada de la Fundación Wikimedia, Inc., una
organización sin ánimo de lucro.
Política de privacidad
Acerca de Wikipedia
Limitación de responsabilidad
Versión para móviles
Desarrolladores
Estadísticas
Declaración de cookies
Wikimedia Foundation
Powered by MediaWiki