Nucleos en digraficas

1. Gráficas

Para los conceptos generales nos referiremos a la referencia [2].
Sean V un conjunto finito no vacío, y A ( V X V, una colección de pares ordenados de distintos elementos de V, una gráfica G está determinada por V y A, donde V es el conjunto de vértices de G, es cual se denotará como V(G), y A es el conjunto de Aristas de G, denotado por A(G).
Dada una Gráfica G, el complementode G, denotado por GC, es la gráfica en la cual V(G) = V(GC) y u1 es adyacente a u2 en GC ( u1 no es adyacente a u2 en G.
En la figura 1.1 se muestran dos gráficas (G) y sus gráficas complemento(GC ).

[pic]
Figura 1.1

Una coloración de los vértices de una gráfica G, es una coloración propia, si cualesquiera dos vértices adyacentes tienen asignado un color diferente.
El númerocromático de una gráfica G, denotado por (G es el número mínimo de colores necesario para colorear los vértices de G, tal que, dos vértices adyacentes no sean coloreados del mismo color, o dicho de otra manera, es el mínimo número de colores necesario para dar una coloración propia a los vértices de la gráfica G.
En la figura 1.2 se muestran dos gráficas con su coloración propia, en la que se observa que(G1 = 3, y (G2 = 3.

[pic]
Figura 1.2

Una gráfica Kn es completa cuando cada par de vértices es adyacente. Una gráfica completa Kn necesita n colores para colorearla adecuadamente, ya que cada vértice es adyacente a todos los demás de Kn.
En la figura 1.3 se muestran tres gráficas completas.

[pic]
Figura 1.3

El número de clan de una gráfica G, denotado por (G es el número máximo devértices en una subgráfica completa de G.
Sea G una gráfica. Un subconjunto de vértices S ( V(G) se denomina conjunto independiente siempre que no haya dos vértices en S que sean adyacentes. El número máximo de conjuntos independientes de una gráfica se denota por (G.
Los conjuntos independientes de la gráfica de la figura 1.4 son:
{a, c, e}, {a, e}, {a, f}, {b, d}, {b, f}, {c, d}, {c, e}, {c,f} y {d, e}
de los cuales, el de mayor cardinalidad es {a, c, e} cuya cardinalidad es 3, por lo que (G = 3.

[pic]
Figura 1.4

2 Digráficas

Sean V un conjunto finito no vacío, y F ( V X V, una colección (puedes ser vacía) de pares ordenados de distintos elementos de V, una gráfica dirigida ó digráfica está determinada por V y F, lo denotaremos como D(V, F), donde V es el conjunto devértices de D y F es el conjunto de flechas de D. La cardinalidad de V(D) es el orden de D, mientras que la cardinalidad de F(D) es el tamaño de D.
En la figura 2.1 se muestran dos digráficas:
La digráfica D1 donde V(D1) = {u, v, w} y F(D1) = {(u, v), (u, w), (w, u)}, en ella se puede ver que (u, v) es una flecha de D1, pero (v, u) no es una flecha de D1.
La digráfica D2 donde V(D2) = {u, v, w}y F(D2) = {(v, u), (u, w), (w, u)}, en ella se puede ver que (v, u) es una flecha de D2, pero (u, v) no es una flecha de D2.

[pic]

Figura 2.1

Si a = (u, v) es una flecha de una digráfica D, decimos que a une u a v, decimos también que a es incidente desde u e incidente hacia v, al mismo tiempo que u es incidente hacia a y v es incidente desde a.

Si a = (u, v) y b = (v, w) son flechasde una digráfica D, entonces la flecha a es adyacente hacia la flecha b, mientras que b es adyacente desde la flecha a. Ver figura 2.2.

[pic]

Figura 2.2

El exgrado ((+) de un vértice v en una digráfica D, es el número de vértices que son adyacentes desde v; el ingrado ((- ) de un vértice v en una digráfica D es el número de vértices que son adyacentes hacia v.
El grado (() de unvértice v en D esta definido por ((v) = (+ (v) + (- (v).
La figura 2.3 muestra que:
( - (u) = 2, (+ (u) = 1, (+ (v) = 1, ( - (v) = 0, (+ (w) = 1 y ( - (w) = 1
entonces ( (u) = 3, ( (v) = 1 y ( (w) = 2

[pic]

Figura 2.3

Teorema 2.1

Si D es una digráfica de orden p y tamaño q con V(D) = {v1,v2,..., vp}, entonces:
P P
( (+ (v i) = ( ( - (v i) = q = | F(D) |
i=1...