coloracion de grafos

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Universidad Nacional Experimental de la Fuerza Armada Nacional
Núcleo: Caracas
Cátedra: Teoría de Grafos
5to semestre Sección “A”


Índice

Introducción……………………………………………………………pag.1
Unidad III: operaciones algebraicas
Operaciones binarias, semigrupos y monoides…………………...pag.2
Isomorfismoshomomorfismos de semigrupos y relaciones……...pag.3
Grupos y sus homomorfismos……………………………………….pag.4
Anillos…………………………………………………………………..pag.5
Sintética………………………………………………………………...pag.6
Unidad IV: Coloración de grafos
Definición y propiedades……………………………………………..pag.7
Numero Cromático, coloración de vértices y aristas…………….....pag.8
Coloración de regiones y grafos coloreables…………………….…pag.9
Grafosnotables………………………………………………………pag.10
Coloracion de grafos notables………………………………….......pag.11
Conclusion……………………………………………………………pag.12
Hemerografia………………………………………………………….pag.13










Introducción

Este trabajo tiene la finalidad de aprender más sobre teoría de grafos, se necesitara saber que es una estructura algebraica para poder dominar más los grafos y sus propiedades.
Senombrará mucho la palabra isomorfismo, que significa sustituir el modelo original por uno semejante pero con las mismas funciones.
Se definirá lo que es una coloración de un grafo que consiste simplemente en colorear el vértice o nodo de un grafo para poder identificarlos mejor.


















1
UNIDAD III:
Operaciones algebraicas

1.- Operaciones Binarias:
Tratan de unaaplicación A* A A donde observamos que los elementos de un mismo conjunto interactúan entre ellos siendo el dominio del producto cartesiano de A y el resultado estaría contenido en A

A x A A
(x,y) x * y ∈ A
Propiedades de las operaciones binarias:
Es cerrada: Si a*b ∈ A∀ a.b ∈ A
Es asociativa: si (a*b)*c= a*(b*c) ∀ a,b,c ∈ A
Si existe e (elemento neutro) contenidoen A tal que: a*e=a y e*a=a∀ a ∈ A
Simétrica: Si existe a ∈ A a´ ∈ A donde a*a´ = e asi como a´ *a=e. diciendo entonces a´ es simétrico de a
Conmutativo: a*b=b*a ∀ a,b, ∈ A

2.- Semigrupos:
Un semigrupo es una estructura algebraica de la forma (A,*) donde A es un conjunto donde se ha definido una ley de composición interna binaria (*).
Un semigrupo cumple las siguientes propiedades:es cerrada, es asociativa y es conmutativa.
3.- Monoide:

Es una estructura algebraica de la forma (A,*) donde A es un conjunto donde se ha definido una ley de composición interna binaria (*).

Un monoide cumple las siguientes propiedades: es cerrada, es asociativa, posee el número neutro y es conmutativo

2
4.- Isomorfismo de semigrupo
Si   f   es   inyectiva,   se   llama  monomorfismo;   si   es   sobreyectiva,
Epimorfismo,biyectiva,isomorfismo. En este último caso se dice que (A,) y (B, #) son estructuras isomorfas. 


5.- Morfismos u Homomorfismo de semigrupo

Para señalar que dos estructuras algebraicas son esencialmente análogas se dice que son homomorfas (semejantes en las formas).Sean (A,), (B, #) estructuras algebraicas y f : A B una aplicación. Diremos que f es un morfismo si f (a1 a2) = f (a1)#f (a2) para todos a1, a2   A.


6.- Relaciones de congruencia en semigrupos:

Sea (G,*) un semigrupo con neutro e. Sea ~ una relación de equivalencia en G

~ es compatible a izquierda con * ⇔ ∀ a, b, x ∈ G: a ~ b x * a ~ x * b
~ es compatible a derecha con * ⇔ ∀ a, b, x ∈ G: a ~ b a * x ~ b * x
La relación ~ es compatible con * (o es de congruencia) ⇔ escompatible de izquierda a derecha


















3

7.- Grupos:
Es una estructura algebraica que consta de un conjunto con una operación que combina cualquier pareja de sus elementos para formar un tercer elemento. Para que se pueda calificar como un grupo, el conjunto y la operación deben satisfacer algunas condiciones llamadas axiomas de grupo, estas...