Teora de grafos

La teora de grafos (tambin llamada teora de las grficas) es un campo de estudio de

las matemticas y las ciencias de la computacin, que estudia las propiedades de
los grafos (tambin llamadas grficas, que no se debe confundir con las grficasque tienen
una acepcin muy amplia) estructuras que constan de dos partes, el conjunto de vrtices,
nodos o puntos; y el conjunto de aristas, lneas o lados (edges en ingls) que pueden
ser orientados o no.
La teora de grafos es una rama de las matemticas discretas y de las matemticas aplicadas,
y es un tratado que usa diferentes conceptos de diversas reas
como combinatoria, lgebra, probabilidad, geometra de polgonos, aritmtica ytopologa.
Actualmente ha tenido mayor preponderancia en el campo de la informtica, las ciencias de la
computacin y telecomunicaciones.

Historia
El origen de la teora de grafos se remonta al siglo XVIII con el problema de los puentes de
Knigsberg, el cual consista en encontrar un camino que recorriera los siete puentes del ro
Pregel (

544212N 203056E) en la ciudad de Knigsberg, actualmente Kaliningrado, de

modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El
trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs
pertinentis1 (La solucin de un problema relativo a la geometra de la posicin) en 1736, es
considerado el primer resultado de la teora de grafos. Tambin se considera uno de los
primeros resultados topolgicos en geometra (que no depende de ninguna medida). Este
ejemplo ilustra la profunda relacin entre la teora de grafos y la topologa.
Luego, en 1847, Gustav Kirchhoff utiliz la teora de grafos para el anlisis de redes elctricas
publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos
elctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicacin de la teora
de grafos a un problema de ingeniera.
En 1852 Francis Guthrie plante el problema de los cuatro colores el cual afirma que es
posible, utilizando solamente cuatro colores, colorear cualquier mapa de pases de tal forma
que dos pases vecinos nunca tengan el mismo color. Este problema, que no fue resuelto
hasta un siglo despus por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado

como el nacimiento de la teora de grafos. Al tratar de resolverlo, los matemticos definieron

trminos y conceptos tericos fundamentales de los grafos.
En 1857, Arthur Cayley estudi y resolvi el problema de enumeracin de los ismeros,
compuestos qumicos con idntica composicin (frmula) pero diferenteestructura molecular.
Para ello represent cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante
un grafo rbol donde los vrtices representan tomos y las aristas la existencia de enlaces
qumicos.
El trmino grafo, proviene de la expresin Hgraphic notation usada por primera vez
por Edward Frankland2 y posteriormente adoptada por Alexander Crum Brown en 1884, y
haca referencia a la representacin grfica de los enlaces entre los tomos de una molcula.
El primer libro sobre teora de grafos fue escrito por Dnes Knig y publicado en 1936

Aplicaciones
Gracias a la teora de grafos se pueden resolver diversos problemas como por ejemplo la
sntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para
diferentes reas por ejemplo, Dibujo computacional, en toda las reas de Ingeniera.
Los grafos se utilizan tambin para modelar trayectos como el de una lnea de autobs a
travs de las calles de una ciudad, en el que podemos obtener caminos ptimos para el
trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.
Para la administracin de proyectos, utilizamos tcnicas como tcnica de revisin y evaluacin
de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los
tiempos para concretar los mismos.
La teora de grafos tambin ha servido de inspiracin para las ciencias sociales, en especial
para desarrollar un concepto no metafrico de red social que sustituye los nodos por los
actores sociales y verifica la posicin, centralidad e importancia de cada actor dentro de la red.
Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura
social puede representarse grficamente. Por ejemplo, una red social puede representar la
estructura de poder dentro de una sociedad al identificar los vnculos (aristas), su direccin e
intensidad y da idea de la manera en que el poder se transmite y a quines.

Se emplea en problemas de control de produccin, para proyectar redes de ordenadores, para

disear mdulos electrnicos modernos y proyectar sistemas fsicos con parmetros
localizados (mecnicos, acsticos y elctricos).
Se usa para la solucin de problemas de gentica y problemas de automatizacin de la
proyeccin (SAPR). Apoyo matemtico de los sistemas modernos para el procesamiento de la
informacin. Acude en las investigaciones nucleares (tcnica de diagramas de Feynman). 4
Los grafos son importantes en el estudio de la biologa y hbitat. El vrtice representa un
hbitat y las aristas (o "edges" en ingls) representa los senderos de los animales o las
migraciones. Con esta informacin, los cientficos pueden entender cmo esto puede cambiar
o afectar a las especies en su hbitat.

Tipos de grafos[editar]

Grafo simple. o simplemente grafo es aquel que acepta una sola arista uniendo dos
vrtices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la nica
que une dos vrtices especficos. Es la definicin estndar de un grafo.

Multigrafo. o pseudografo son grafos que aceptan ms de una arista entre dos
vrtices. Estas aristas se llaman mltiples o lazos (loops en ingls). Los grafos
simples son una subclase de esta categora de grafos. Tambin se les llama grafos nodirigido.

Grafo dirigido. Son grafos en los cuales se ha aadido una orientacin a las aristas,
representada grficamente por una flecha

Grafo etiquetado. Grafos en los cuales se ha aadido un peso a las aristas (nmero
entero generalmente) o un etiquetado a los vrtices.

Grafo aleatorio. Grafo cuyas aristas estn asociadas a una probabilidad.

Hipergrafo. Grafos en los cuales las aristas tienen ms de dos extremos, es decir, las
aristas son incidentes a 3 o ms vrtices.

Grafo infinito. Grafos con conjunto de vrtices y aristas de cardinal infinito.

Representacin de grafos[editar]
Artculo principal: Grafo (estructura de datos)

Existen diferentes formas de representar un grafo (simple), adems de la geomtrica y

muchos mtodos para almacenarlos en una computadora. La estructura de datos usada
depende de las caractersticas del grafo y el algoritmo usado para manipularlo. Entre las
estructuras ms sencillas y usadas se encuentran las listas y las matrices, aunque
frecuentemente se usa una combinacin de ambas. Las listas son preferidas en grafos
dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen
acceso rpido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista[editar]

lista de incidencia - Las aristas son representadas con un vector de pares

(ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. 5

lista de adyacencia - Cada vrtice tiene una lista de vrtices los cuales son
adyacentes a l. Esto causa redundancia en un grafo no dirigido (ya que A existe en la
lista de adyacencia de B y viceversa), pero las bsquedas son ms rpidas, al costo de
almacenamiento extra.

lista de grados - Tambin llamada secuencia de grados o sucesin grfica de un

grafo no-dirigido es una secuencia de nmeros, que corresponde a los grados de los
vrtices del grafo.

Estructuras matriciales[editar]

Matriz de adyacencia - El grafo est representado por una matriz cuadrada M de

tamao

, donde

es el nmero de vrtices. Si hay una arista entre un vrtice x y un

vrtice y, entonces el elemento

es 1, de lo contrario, es 0.

Matriz de incidencia - El grafo est representado por una matriz de A (aristas) por V
(vrtices), donde [vrtice, arista] contiene la informacin de la arista (1 - conectado, 0 - no
conectado)

Grafo G(V,A)

Conjuntos

Matriz de

Matriz de

Secuencia

Lista de

adyacencia

incidencia

de grados

Adyacencia

V = { 1, 2,
3, 4, 5, 6 }
A = { {1,1},
{1,2}, {1,5},
{2,3}, {2,5},

{ {1,2,5},
(4,3,3,3,2,1)

{3,4},

{3,5}, {4},
{5,6} }

{4,5},
{4,6} }

Problemas de teora de grafos[editar]

Ciclos y caminos hamiltonianos[editar]

Artculo principal: Ciclo hamiltoniano

Ejemplo de un ciclo Hamiltoniano.

Un ciclo es una sucesin de aristas adyacentes, donde no se recorre dos veces la misma
arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene adems que recorrer
todos los vrtices exactamente una vez (excepto el vrtice del que parte y al cual llega).
Por ejemplo, en un museo grande (al estilo del Louvre), lo idneo sera recorrer todas las
salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo
(los vrtices son las salas, y las aristas los corredores o puertas entre ellas).
Se habla tambin de Camino hamiltoniano si no se impone regresar al punto de partida, como
en un museo con una nica puerta de entrada. Por ejemplo, un caballo puede recorrer todas
las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino
hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.

Hoy en da, no se conocen mtodos generales para hallar un ciclo hamiltoniano en tiempo
polinmico, siendo la bsqueda por fuerza bruta de todos los posibles caminos u otros
mtodos excesivamente costosos. Existen, sin embargo, mtodos para descartar la existencia
de ciclos o caminos hamiltonianos en grafos pequeos. El problema de determinar la
existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.

Grafos planos[editar]
Artculo principal: Grafo plano

Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten,
se dice que es plano.
Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos
de las casas tienen el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto,
no quieren cruzarse jams. Es posible trazar los nueve caminos que juntan las tres casas
con los tres pozos sin que haya cruces?
Cualquier disposicin de las casas, los pozos y los caminos implica la presencia de al menos
un cruce.
Sea Kn el grafo completo con n vrtices, Kn, p es el grafo bipartito de n y p vrtices.
El juego anterior equivale a descubrir si el grafo bipartito completo K3,3 es plano, es decir, si se
puede dibujar en un plano sin que haya cruces, siendo la respuesta que no. En general, puede
determinarse que un grafo no es plano, si en su diseo puede encontrase una estructura
anloga (conocida como menor) a K5 o a K3,3.
Establecer qu grafos son planos no es obvio, y es un problema que tiene que ver
con topologa.

Coloracin de grafos[editar]
Artculo principal: Coloracin de grafos

Si G=(V, E) es un grafo no dirigido, una coloracin propia de G, ocurre cuando coloreamos los
vrtices de G de modo que si {a, b} es una arista en G entonces a y b tienen diferentes
colores. (Por lo tanto, los vrtices adyacentes tienen colores diferentes). El nmero mnimo de
colores necesarios para una coloracin propia de G es el nmero cromtico de G y se escribe
como C (G). Sea G un grafo no dirigido sea el nmero de colores disponibles para la
coloracin propia de los vrtices de G. Nuestro objetivo es encontrar una funcin polinomial P

(G,), en la variable , llamada polinomio cromtico de G, que nos indique el nmero de

coloraciones propias diferentes de los vrtices de G, usando un mximo de colores.
Descomposicin de polinomios cromticos. Si G=(V, E) es un grafo conexo y e pertenece a ,
entonces: P (G,)=P (G+e,)+P (G/e,), donde G/e es el grafo se obtene por contraccin de
aristas.
Para cualquier grafo G, el trmino constante en P (G,) es 0
Sea G=(V, E) con |E|>0 entonces, la suma de los coeficientes de P (G,) es 0.
Sea G=(V, E), con a, b pertenecientes al conjunto de vrtices V pero {a, b}=e, no perteneciente
a al conjunto de aristas E. Escribimos G+e para el grafo que se obtiene de G al aadir la arista
e={a, b}. Al identificar los vrtices a y b en G, obtenemos el subgrafo G++e de G.0000
Teorema de los cuatro colores
Otro problema famoso relativo a los grafos: Cuntos colores son necesarios para dibujar un
mapa poltico, con la condicin obvia que dos pases adyacentes no puedan tener el mismo
color? Se supone que los pases son de un solo pedazo, y que el mundo es esfrico o plano.
En un mundo en forma de toroide; el teorema siguiente no es vlido:
Cuatro colores son siempre suficientes para colorear un mapa.
El mapa siguiente muestra que tres colores no bastan: Si se empieza por el pas central a y se
esfuerza uno en utilizar el menor nmero de colores, entonces en la corona alrededor
de aalternan dos colores. Llegando al pas h se tiene que introducir un cuarto color. Lo mismo
sucede en i si se emplea el mismo mtodo.
La forma precisa de cada pas no importa; lo nico relevante es saber qu pas toca a qu
otro. Estos datos estn incluidos en el grafo donde los vrtices son los pases y las aristas
conectan los que justamente son adyacentes. Entonces la cuestin equivale a atribuir a cada
vrtice un color distinto del de sus vecinos.
Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega,
es bastante fcil. Pero el teorema de los cuatro colores no es nada obvio. Prueba de ello es
que se han tenido que emplear ordenadores para acabar la demostracin (se ha hecho un
programa que permiti verificar una multitud de casos, lo que ahorr muchsimo tiempo a los
matemticos). Fue la primera vez que la comunidad matemtica acept una demostracin

asistida por ordenador, lo que cre en su da una cierta polmica dentro de la comunidad
matemtica.

Caracterizacin de grafos[editar]
Grafos simples[editar]
Un grafo es simple si a lo ms existe una arista uniendo dos vrtices cualesquiera. Esto es
equivalente a decir que una arista cualquiera es la nica que une dos vrtices especficos.
Un grafo que no es simple se denomina multigrafo.
Grafos conexos[editar]
Un grafo es conexo si cada par de vrtices est conectado por un camino; es decir, si para
cualquier par de vrtices (a, b), existe al menos un camino posible desdea hacia b.
Un grafo es doblemente conexo si cada par de vrtices est conectado por al menos dos
caminos disjuntos; es decir, es conexo y no existe un vrtice tal que al sacarlo el grafo
resultante sea disconexo.
Es posible determinar si un grafo es conexo usando un algoritmo Bsqueda en anchura (BFS)
o Bsqueda en profundidad (DFS).
En trminos matemticos la propiedad de un grafo de ser (fuertemente) conexo permite
establecer con base en l una relacin de equivalencia para sus vrtices, la cual lleva a una
particin de stos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que
son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es
importante para muchas demostraciones en teora de grafos.

Grafos completos[editar]
Artculo principal: Grafo completo

Un grafo es completo si existen aristas uniendo todos los pares posibles de vrtices. Es decir,
todo par de vrtices (a, b) debe tener una arista e que los une.
El conjunto de los grafos completos es denominado usualmente

, siendo

el grafo

completo de n vrtices.

Un

, es decir, grafo completo de

La representacin grfica de los

vrtices tiene exactamente

aristas.

como los vrtices de un polgono regular da cuenta de su

peculiar estructura.
Grafos bipartitos[editar]
Artculo principal: Grafo bipartito

Un grafo G es bipartito si puede expresarse como

(es decir, sus

vrtices son la unin de dos grupos de vrtices), bajo las siguientes condiciones:

son disjuntos y no vacos.

Cada arista de A une un vrtice de V1 con uno de V2.

No existen aristas uniendo dos elementos de V1; anlogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente

como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos
resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A
con un elemento de la columna B.

Homeomorfismo de grafos[editar]
Artculo principal: Homeomorfismo de grafos

Dos grafos

son homeomorfos si ambos pueden obtenerse a partir del mismo grafo

con una sucesin de subdivisiones elementales de aristas.

rboles[editar]
Artculo principal: rbol (teora de grafos)

Ejemplo de rbol.

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un rbol. En un grafo
con n vrtices, los rboles tienen exactamente n - 1 aristas, y hay nn-2 rboles posibles. Su
importancia radica en que los rboles son grafos que conectan todos los vrtices utilizando el
menor nmero posible de aristas. Un importante campo de aplicacin de su estudio se
encuentra en el anlisis filogentico, el de la filiacin de entidades que derivan unas de otras
en un proceso evolutivo, que se aplica sobre todo a la averiguacin del parentesco entre
especies; aunque se ha usado tambin, por ejemplo, en el estudio del parentesco entre
lenguas.

Grafos ponderados o etiquetados

En muchos casos, es preciso atribuir a cada arista un nmero especfico,

llamado valuacin, ponderacin o coste segn el contexto, y se obtiene as un grafo valuado.
Formalmente, es un grafo con una funcin v: A R+.
Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre s por
carreteras; su inters previsible ser minimizar la distancia recorrida (o el tiempo, si se pueden
prever atascos). El grafo correspondiente tendr como vrtices las ciudades, como aristas las
carreteras y la valuacin ser la distancia entre ellas.
Y, de momento, no se conocen mtodos generales para hallar un ciclo de valuacin mnima,
pero s para los caminos desde a hasta b, sin ms condicin.

Dimetro
En un grafo, la distancia entre dos vrtices es el menor nmero de aristas de un recorrido
entre ellos. El dimetro, en una figura como en un grafo, es la mayor distancia de entre todos
los pares de puntos de la misma.

El dimetro de los Kn es 1, y el de los Kn,p es 2. Un dimetro infinito puede significar que el

grafo tiene una infinidad de vrtices o simplemente que no es conexo. Tambin se puede
considerar el dimetro promedio, como el promedio de las distancias entre dos vrtices.
El mundo de Internet ha puesto de moda esa idea del dimetro: Si descartamos los sitios que
no tienen enlaces, y escogemos dos pginas web al azar: En cuntos clics se puede pasar
de la primera a la segunda? El resultado es el dimetro de la Red, vista como un grafo cuyos
vrtices son los sitios, y cuyas aristas son lgicamente los enlaces.
En el mundo real hay una analoga: tomando al azar dos seres humanos del mundo, En
cuntos saltos se puede pasar de uno a otro, con la condicin de slo saltar de una persona a
otra cuando ellas se conocen personalmente? Con esta definicin, se estima que el dimetro
de la humanidad es de... ocho solamente!
Este concepto refleja mejor la complejidad de una red que el nmero de sus elementos.

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos

DEFINICIN DE GRAFO
Un Grafo es un par (V(G), E(G)), donde:

V(G) es un conjunto no vaco y finito de elementos {v 1, v2, , vp}

E(G) pertenece a V(G) x V(G) , o sea, define una relacin R entre los vrtices,
puntos o elementos V(G).

El conjunto V(G) se denomina conjunto de vrtices (puntos, nodos) y si vi y

vj estn en E(G), es equivalente a decir viRvj (vi, vj. estn en V(G)) y esto se expresa
diciendo que entre vi y vj existe una lnea que se denota xij = (vi, vj) y E(G) se
denomina el conjunto de lneas del grafo (o aristas). Los vrtices v 1 y v2 se
denominan extremos de la lnea.
Ejemplo: El grafo representado a continuacin, se obtiene a partir del conjunto de
vrtices
V={v1, v2,v3, v4, v5} y de la relacin R es subconjunto de V x V, tal que, {(v1, v2)(v2,
v3)(v4, v5)(v1, v4)(v2, v4) (v4, v4)(v2, v5)(v2, v3)} .

Una lnea de la forma (u,u) la denominaremos lazo o bucle y una lnea del tipo
(u,v) con u distinto de v (uRv) la llamaremos lnea simple. En cambio, cuando
tengamos varias lneas que tengan como vrtices terminales u y v, diremos que
son lneas mltiples.
Observacin: Las lneas (v2, v3) y (v3, v2) de la figura anterior son lneas mltiples
y la lnea (v4, v4) de la misma figura es un lazo.

En algunos casos es conveniente considerar grafos dirigidos en los cuales es necesario distinguir el sentido en que van las lneas, por
medio de flechas.

Ejemplos:

Este grafo se representa por:

G1 = (V(G1), E(G1))
V(G1) = {1, 2, 3, 4}
E(G1) = {(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)}

G1 es un grafo NO DIRIGIDO. Esto es que los pares de puntos (1,2) y (2,1) representan la misma lnea. Es decir, si el vrtice 1 est
conectado con el vrtice 2, entonces el vrtice 2 est conectado con el vrtice 1.

Ahora bien, si tenemos el siguiente grafo:

Este grafo, sin embargo, se representa por:

G2 = (V(G2), E(G2))
V(G2) = (1,2,3)
E(G2) = ( (1,2) (2,1) (2,3) )

Aqu se repiten las conexiones de 1 con 2 porque este, como se ve, es un grafo DIRIGIDO. En este tipo de grafos si 1 est conectado
con 2, no necesariamente 2 est conectado con 1.

Esto es lo que la mayora de los autores denominan multigrafo. Sin embargo, nos dedicaremos a estudiar un tipo particular de grafos
denominados grafos simples o matemticos, que son aquellos grafos que no poseen orientacin, ni lneas mltiples, ni lazos.

Usaremos la notacin utilizada por F. Harary, denotaremos la cardinalidad del conjunto de vrtices de un grafo simple como V(G)= p
y la cardinalidad del conjunto de lneas del grafo como E(G) = q.

GRAFOS: RELACIN DE EQUIVALENCIA

Si la relacin es reflexiva, significa que por ejemplo v1Rv1, lo que indica que el vrtice
v1 tiene un lazo.

Si en un grafo dirigido la relacin R es simtrica, es decir, v1Rv2entonces v2R v1, tenemos

que existen dos lneas que unen a v1 y v2.

Si la relacin es transitiva, o sea, (v1Rv2) y (v2Rv3) si y slo si v1Rv3, se tiene la existencia

de un tringulo v1 v2 v3.

Grado o valencia de un vrtice (se denota grad(vi) o val(vi)) e indica el nmero total
de lneas que tiene un vrtice vi.
En el problema de los puentes de Knigsberg (resuelto por Euler) encontramos un
multigrafo de cuatro vrtices y siete lneas que representan la relacin entre los vrtices.
Los vrtices A, B, D tienen tres lneas y el vrtice C cinco lneas. De este modo, tenemos
val(A) = val(B) = val(D) = 3 y val(C) = 5.
Si tenemos una lnea xij = (vi, vj), entonces los vrtices vi y vj se
llaman vrtices adyacentes y a vi lo denominaremos vrtice inicial y vj vrtice final.
Adems se dice que la lnea es incidente al vrtice vi como tambin es incidente al vj.
Las lneas son concurrentes entre s, si varias lneas tienen un vrtice vi en comn.
Las lneas (A, C), (C, D), (B, C) son concurrentes entre s. Entonces el nmero total de
lneas concurrentes al vrtice vi es igual al grado o valencia de vi.
A los vrtices con valencia mnima los denotaremos con d(G) y aquellos vrtices con
valencia mxima D(G).

En el grafo anterior vemos que d(G) = 3 y D(G) = 5.

En particular, si d(G) = D(G) = r, entonces todos los vrtices de G tienen la misma valencia
"r" y el grafo se dice regular de grado r.

Obs.: No siempre es posible construir grafos regulares para valores cualesquiera de p, q y

r, ya que de acuerdo con el Teorema de Euler se debe cumplir con 2q = pr.

Al conjunto de todos los vecinos de un vrtice dado le llamaremosvecindad de vi o

conjunto de adyacencia de vi, y se denota N(vi).
As, N(vi) = { vj/ vjRvi }.
En particular, un vrtice vi para el cual N(vi)= 0, se le denominavrtice aislado.
Por ejemplo, en el siguiente grafo v4 es un punto aislado.

TEOREMA DE LAS VALENCIAS

La suma de las valencias de los vrtices de un grafo es dos veces el nmero de lneas, es
decir, si G es un grafo con "p" vrtices y "q" lneas, entonces val(v 1) + val(v2) + ... + val(vp)
= 2q.

Demostracin: Si vi pertenece a N(vj), entonces vj pertenece a N(vi), lo que

implica que la lnea (vi, vj) es contada dos veces. Como esto ocurre para cada vrtice
vi, con i entre 1 y p, la suma de todos los vi es 2q.

Corolario: En todo grafo G el nmero de vrtices con valencia impar debe ser par.
Demostracin: Los vi que pertenecen a V(G), con val(vi') par y los vi'' con val(vi'') impar.
Luego,
Pero, la

.
es par y 2q es un nmero par, lo que implica que la

diferencia de dos nmeros pares, y por lo tanto es par.

Lo anterior es muy til para verificar la existencia de grafos.

Por ejemplo, si tenemos los siguientes datos:
El grafo tiene 5 puntos, donde:
Val (1) = 2
Val (2) = 3
Val (3) = 1

es la

Val (4) = 1
Val (5) = 4
Entonces no existe grafo alguno que cumpla con esta condicin, pues viola el teorema
anterior, ya que existen 3 puntos con valencia impar, y como vimos en la demostracin la
cantidad de vrtices con valencia impar, debe ser par.

TEOREMA: Sea un grafo G = (p,q); entonces:

a) Si "p" es par, existen grafos regulares de cualquier valencia r, si
b) Si "p" es impar, existen grafos regulares solamente de valencia par r y si

.
.

Por ejemplo, si p = 7 existen grafos regulares de grado 2, 4 y 6

posted by Claudio Cifuentes M | 6:41 PM | 1 comments

ISOMORFISMO DE GRAFOS

Definicin:

Se dir que dos grafos G y G' son isomorfos entre s, si:

Existe una funcin biyectiva

Si dos vrtices vi, vj son adyacentes en V(G), es decir, viRvj, entonces las

correspondientes imgenes de dichos vrtices tambin son adyacentes pero en V(G'), dicho
de otra forma,
; y viceversa.

Ejemplo: En la siguiente figura, tenemos que G es isomorfo a G'.

Donde V(G) = {1,2,3,4} y V(G') = {A,B,C,D} y como debe cumplirse que f:V(G)
V(G') es una biyeccin, entonces f(1) = D, f(2) = B, f(3) = C, f(4) = A. Observar que
1R4 en G, entonces, D R A en G'.
Tenemos otra funcin que tambin define un isomorfismo entre G y G'.
f(1) = B, f(2) = D, f(3) = C y f(4) = A.
Observar, igualmente, que para este caso 1 R 4 en G, entonces, B R A en G'.
La relacin de isomorfismo preserva las vecindades de cada vrtice.
La relacin de isomorfismo de dos grafos G y G' se denota de la siguiente
manera,

Corolario: Si

, entonces:

1. /V(G) /= /V(G')/
2. /E(G) /= /E(G') /
3. Si tiene vi tiene "k" vrtices vecinos vi1, vi2, vi3, ... , vik, entonces, f(vi) tiene los
siguientes "k" vrtices vecinos f(vi1), f(vi2), f(vi3), ... , f(vik).
4. vi y f(vi) tienen la misma valencia.

posted by Claudio Cifuentes M | 6:38 PM | 0 comments

CARACTERIZACIN DE LOS GRAFOS

Un problema interesante en la teora de grafos, que no ha sido resuelto del todo, es el
referente a la bsqueda de todos los grafos simples diferentes que existen con un nmero
determinado de vrtices (caracterizacin de los grafos). As, para p = 1 hay un solo
grafo.

As, para p = 1 hay un solo grafo.

Para p = 2, existen dos grafos diferentes.

Para p = 3 ya llegan a ser cuatro grafos

.
Pero para p = 4 ya nos encontramos con once grafos distintos.

Si hacemos esto para todos los grafos simples diferentes que existen con un nmero "p" de
vrtices, vemos que a medida que "p" crece el nmero de grafos aumenta
considerablemente.
Esto es un problema muy complejo, y para que se tenga una idea, cuando p = 9, existen
274668 grafos diferentes y conviene clasificar los grafos en ciertas familias de acuerdo a
algunas propiedades especficas.

Grafos Nulos (Np), son aquellos grafos que presentan solamente vrtices aislados
y por lo tanto, no existe una relacin R entre sus vrtices, es decir, /V(G)/= p y /E(G)/= 0.

Grafos Completos (Kp), son grafos donde cada vrtice est relacionado con
todos los (p-1) vrtices restantes.

Si tengo "p" vrtices hay p (p-1) posibles lneas. pero como el grafo es simple, cada lnea se
cuenta dos veces. Luego hay un total de p(p-1)/2 lneas.
Esntonces /V(Kp)/= p y /E(Kp)/= p(p -1)/2
Algunos ejemplos de los cinco primeros Kp

Por ejemplo, la familia de los Grafos Nulos (Np), considera aquellos grafos que
presentan solo vrtices aislados y por lo tanto, no existe una relacin R entre sus
vrtices, es decir, /V(G)/= p y /E(G)/= 0.
En contraposicin, existe la familia de los Grafos Completos (Kp), donde cada
vrtice est relacionado con todos los (p-1) vrtices restantes. Ahora, si tengo "p"
vrtices hay p(p-1) posibles lneas. Sin embargo, el grafo es simple y cada lnea se
cuenta dos veces, luego, hay un total de p(p -1)/2 lneas, o sea, /V(K p)/= p y
/E(Kp)/= p(p-1)/2 .
Otra familia de particular inters son los llamados Ciclos, que denotaremos Cp ,
donde "p" es el nmero de vrtices. Son grafos regulares de valencia 2, donde el
nmero de lneas q = p. Tambin son conocidos (sobre todo en geometra) como los
"p-gonos". Algunos de los grafos que forman esta familia son los siguientes:

Tringulo ------>

Cuadrado ------>

Pentgono ---->
http://teoriadegrafos.blogspot.com/
Una

breve

introduccin

la

http://revistasuma.es/IMG/pdf/28/011-026.pdf

teora

de

grafos

en