Algoritmo para determinar la k-coloración de un grafo
Date
2023-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Benemérita Universidad Autónoma de Puebla
Abstract
"En la teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a los nodos o vértices del grafo. Es decir, una coloración de los vértices de un grafo es una asignación tal que ningún vértice adyacente comparta el mismo color. Si en la coloración se usan k (k=1,2, …, n) colores distintos diremos que es una k-coloración. Una coloración siempre es posible, dado que podemos asignar a cada vértice del grafo un color diferente si fuera necesario, por ejemplo, para grafos completos. Si existe una k-coloración de G se dice que el grafo G es k-coloreable. El valor mínimo k para el que un grafo G es k-coloreable se denomina número cromático de G, y se designa por χ(G). De esta forma la coloración de los vértices se basa en encontrar grupos de vértices en el grafo que no sean adyacentes entre sí para así poder asignarles el mismo color. Este proyecto propone diseñar e implementar un algoritmo para determinar con cuantos colores se puede colorear un grafo. El sistema debe estar en línea para que personas interesadas puedan realizar pruebas del kcoloreo de grafos".
Description
Keywords
Citation
Collections
Document Viewer
Select a file to preview:
Can't see the file? Try reloading