Je 
2 ema 
UNIVERSIDAD NACIONAL AUTONOMA 
DE MEXICO 
    
  
   
  
A DA   A CD Es 
FORA] E D cp] 
E 
  
FACULTAD DE CIENCIAS 
(4.£)- NÚCLEOS EN DIGRÁFICAS 
T E S ! S 
QUE PARA OBTENER EL TITULO DE: 
MA TEMATICA 
P R E Ss E N T A 
MARGARITA | SmEnez VILLARRUEL     
DIRECTORA DE TESIS: 
HORTENSIA GALEANA SANCHEZ. 
S Ip 
S .   
TESIS CON | ve 
FALLA DE ORIGENL99Ó macurz> 
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
  
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
  
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
  
 
Dye
 
A
 
  
AYÉNMA DE 
MEXICO 
M. enC. Virginia Abrin Batule 
Jefe de la División de Estudios Profesionales de la 
Facultad de Ciencias 
Presente 
Comunicamos a usted que hemos revisado el trabajo de Tesis: 
“(4 - NÚCLEO EN DIGRÁFICAS” 
realizado por Margarita Jiménez Villarruel 
con número de cuenta  7111149-4 , pasante de la carrera de MATEMÁTICAS. 
Dicho trabajo cuenta con nuestro voto aprobatorio. 
Atentamente ; 
o Tess DRA. HORTENSIA GALEANA SÁNCHEZ DA ARA 
Propietario DR. HUGO ALBERTO RINCON MEJIA Muego E luisa M. 
Propietario M.ENC. VIRGINIA ABRÍN BATULE igor a Gén 5 se 
Suplente 
Suplente Lavra Ribana R. 
 
A LA MEMORIA DE EPIFANIO JIMÉNEZ GUTIÉRREZ
N
S
 
II 
A MIS PADRES: GUADALUPE VILLARRUEL CEDILLO 
EPIFANIO JIMENEZ GUTIERREZ 
A MIS HIJOS: JORGE HOMERO Y PABLO ISAAC 
A MI HERMANA: MA. VIRGINIA 
A MIS SOBRINOS:ALEJANDRA MARGARITA Y ERICK 
ULISES
A
 
C
S
 
AGRADEZCO INFINITAMENTE A LA DRA. HORTENSIA 
GALEANA SÁNCHEZ HABER DIRIGIDO ESTE TRABAJO Y 
REGALARME SU VALIOSO TIEMPO.
E
,
 
A 
OS 
INDICE 
Introducción 
Definiciones 
Capítulo 1 
Seminúcleos y Núcleos en Digráficas 
Capítulo 11 
é y (4, £)-Núcleos en Digráficas 
Capítulo HI 
£ -Núcleos en Digráficas 
Capitulo IV 
Una condición suficiente para la existencia de 4 - 
Núcleos en Digráficas. 
Referencias 
21 
34 
54 
63 
75
Ah 
Introducción 
Sea D una digráfica, V(D) su conjunto de vértices y F(D) su 
conjunto de flechas. Un conjunto N < V(D) es un núcleo de D si: N 
es independiente (no existen flechas de D con ambos extremos en N) 
y absorbente (para cada x e V(D) — N existe y e N tal que (Xx,y) € 
F(D)). 
El concepto de núcleo de una digráfica fue introducido por John 
Von Neumann y Morgenstern 1944 en el contexto de la Teoría de 
Juegos, ellos probaron que toda digráfica finita sin ciclos dirigidos 
posee un único núcleo, 
El concepto de núcleo de una digráfica tiene aplicaciones en: 
problemas de toma de decisiones, en teoría de juegos como en el 
juego de Nim, en la ubicación de radares, en lógica y en muchas 
otras áreas, esto ha hecho que crezca el interés por encontrar 
condiciones suficientes para la existencia de núcleos en digráficas. 
En 1953 Richardson demostró que toda digráfica sin ciclos dirigidos 
de longitud impar posee núcleo. 
Este es ahora un resultado clásico sobre la existencia de núcleos en 
digráficas. 
El problema de la existencia de un núcleo en una digráfica dada ha 
sido estudiado por varios autores. : 
En 1981 M. Kwasnik introdujo el concepto de (4.£)-núcleo que es 
una generalización del concepto de núcleo en una digráfica y 
" demostró una generalización del teorema de Richardson; probó que 
toda digráfica fuertemente conexa sin ciclos dirigidos de longitud no 
congruente con cero módulo k posee un é-núcleo.
$
 
En el presente trabajo se expone una recopilación sobre la existencia 
de (€.£)-núcleos en digráficas explicando en detalle los métodos 
usados para la obtención de condiciones suficientes para la 
existencia de (4, £)-núcleos en digráficas. 
Antes de continuar definiremos lo que es un é-núcleo, y un (4.£)- 
núcleo, ¿> 2,42 1. 
Sea D una digráfica é y £ números naturales con £>2,£2> 1. Un 
conjunto J c V(D) será llamado un (4. £)-núcleo de la digráfica si: 
1. Paracadax” *x,  x,x”€ J tenemos dp (x,x”) > €. 
2. Para cada y e (V(D) — J) existe x e J tal que dp (yx) <£. 
Un é¿-núcleo es un (€, 4-1) —úcleo, para 4= 2 y £= 1 es un núcleo en 
el sentido de Von Neumann. 
El trabajo desarrollado en esta tesis “(4,)-núcleos en digráficas” se 
basa en los trabajos de investigación publicados por investigadores 
mexicanos y extranjeros. Los investigadores mexicanos son: 
Hortensia Galeana S., Hugo Alberto Rincón M. y Víctor Neumann 
L. Algunos delos investigadores extranjeros son M. Kwassnik, C. 
Berge, P. Duchet. 
La tesis contiene cuatro capítulos: El Capítulo I “Seminúcleos y 
Núcleos. en Digráficas”;, el Capitulo 1 “é£ y (4.£)-núcleos en: 
digráficas”; el Capítulo IM “£-núcleos en digráficas” y el capítulo TV 
“Una condición suficiente para la existencia de é-núcleos en 
digráficas”. Antes de desarrollar los cuatro “capítulos hacemos un 
glosario con los términos más usados.
ad
 
Y
 
Definiciones 
Una digráfica D es un par (V,F) en donde V es un conjunto finito no 
vacio y F un subconjunto de VxV que no contiene pares de la forma 
(v,v). Los elementos de V son los vértices de D y los de F las flechas. 
vi 
Y 
v2 
vs 
Mi v3 D;»: 
D:: 
v(D,) = (V1,V2,V3,Vg, Vs] 
F(D) = ((v1,v2), (v2,Va), (Va,V2), (V3,Va), (Va,V3), (Va,V5), (V5,V1), 
(Viv) 
V(D>) = (vi) 
F(D)=0 
Si f = (v,,va) e F diremos que f va de v; a va, que v;, y va son las 
terminales de f y que v, es el vértice terminal inicial de f y va es el 
vértice terminal final de f. Si además v, e S¡ < V(D) y v2 € Sac 
V(D) se dirá que f va de v, a Sz, de S¡ aSzo de S, a v2.
Si (v¡,v2) € F y (v2,v1) € F diremos que f = (v,,v2) € F es una flecha 
simétrica. 
; En el siguiente ejemplo tenemos los conjuntos de vértices y flechas de 
D: 
V(D) = [v1,V2,V3,V4,Vs,V6) 
F(D)= ((v1,v2), (V1,V4), (V2,V3), (V3,V6), (V3,Va), (Va4,V3), (Va,V5), (V5,Vs), 
(V5,Va), (V6,V3), (Vó,V1), (V2,Vs)) 
va 
v3 
Mi 
Va y
 
Vá 
Vs 
Si = ÍV1.V2,V3) 
S2= [Va,Vs, Vo) 
VieSicV VES, V 
f = (v3,vg) va de S, a S» 
f = (v3, vs) es una flecha simétrica de D. 
ud
 
d
e
Una digráfica D se llama simétrica si siempre que (u,v) es una flecha 
de D, entonces también lo es (v,u). Existe una correspondencia 
natural uno a uno entre el conjunto de digráficas simétricas y el 
conjunto de gráficas. Una digráfica se llamará asimétrica u orientada 
si siempre que (u,v) sea una. flecha de D, entonces (v,u) no es una 
flecha de D. Así una digráfica asimétrica puede obtenerse desde una 
gráfica G asignando una sola dirección a cada arista de G, 
transformándose G en una digráfica orientada o asimétrica. 
Una gráfica finita (G) es una pareja ordenada formada por un 
conjunto finito, Y junto con un conjunto (posiblemente vacío) A 
(separado de V) de subconjuntos de dos elementos (distintos) de 
vértices de V. 
Gráfica G Gráfica orientada de G o 
Digráfica D. 
É>SN 
Digráfica simétrica
> 
> 
Una digráfica D, es una subdigráfica de una digráfica D si V(D¡) < 
V(D) y F(D,) < F(D) y se denota D, < D. 
0 0 
Digráfica D Subdigráfica D¡ 
Si U es un subconjunto no vacío del conjunto de vértices de una 
digráfica D, entonces la subdigráfica (U) de D plena o inducida por U 
es aquella digráfica que tiene como conjunto de vértices U y cuyo 
conjunto de flechas son todas aquellas de D que unen vértices de U.
>
 
vi va v> 
v3 v3 
v6 V6 
V4 Va 
vs 
. Subdigráfica de D inducida por U 
Digráfica D U =([V), Va, Va, Vo) 
La parte asimétrica de D (Asym(D)) es la subdigráfica generadora de 
D cuyas flechas son las flechas asimétricas de D y los vértices son 
todos los vértices de la digráfica D. 
e 
Asym(D): 
 
> 
Una buena coloración de vértices de una digráfica es una coloración 
de los vértices de manera que vértices adyacentes tengan distinto 
color. 
El número cromático x(D) de una digráfica D es el mínimo número m 
de colores para el cual una digráfica tiene una buena coloración con 
m colores. Si x(D) = n, entonces la digráfica se llama n-cromática. 
l 1 1 l 
o] : 
2 1 D, 
D, D; 
2 l
E
 
> 
x1(D)=1 
1(D)) =2 
1D3) = 2 
1D4) =3 
1(D5) =3 
Sean u y v vértices (no necesariamente distintos) de una digráfica D, 
por un u-v semicamino dirigido se entiende una sucesión alternante 
finita 
u=Ug,f,,U ¡+ £2,....,Un-1> Lp, Un=V 0 
de vértices y flechas empezando con el vértice u y terminando con el 
vértice v, tal que f; = (u;.,,u;) o f, = (u;, u; ,) es una flecha de D para i = 
1,2,...,N. 
El número n (el número de ocurrencias de las flechas) se llama la 
longitud del semicamino dirigido. Si f; = (u;.,,u;) es flecha de D para 
cada i = 1,2,....n en (1) entonces la sucesión (1) se llama un u-v 
camino dirigido. 
v2 
vi v3 
Vs Va 
Semicamino dirigido C;: v¡,.(v1,V2), Val(Vs,V2), Var(V3,V4), V3.(V3,V2), 
va,(v»,V5), vs es un seriicamino dirigido v¡-vs. 
Camino dirigido Ca: v;,V2,V3,V2,V5 es Un v¡-vs camino dirigido. 
9
> 
El camino dirigido se denotará cerrado sí vy = Vr. 
La longitud del camino dirigido es n si C = (Vo.Vio0> Va) y la 
denotaremos por ¿(€ ), asit(C)=n. 
  
  
  
C 1: (V1,V2,Vé,V3,V4,Vs, Vs, V3) es un camino dirigido y 2(C ¡)=7 
C 2: (v1,V2,V3,Va, Vs, V6,V¡) es un camino dirigido cerrado y £(C,)= 6 
Una trayectoria dirigida que une a u con v es un camino dirigido 
U = U,U;,....Un = v en el que ningún vértice se repite, una trayectoria 
dirigida une a u y v y la llamamos una u-v trayectoria dirigida. 
En la digráfica anterior T(v,,v5) = (v,,V2,V3,Va,Vs) es una trayectoria de 
v;¡ a vs. 
Por la distancia dirigida dp( y) del vértice x al vértice y en una 
digráfica D entendemos la longitud de la trayectoria dirigida más 
10
corta desde x a y en D. dp(x,y) = mín f ¿(T) HT es una xy-travectoria 
dirigida). 
La longitud de una trayectoria dirigida T; € ( T ) es el número de 
vértices sobre la trayectoria menos uno. 
X2 
X3 
X6 Xa 
Xs 
=>
 
Ti(x1-X5) = Ti (%1,X2,X3,X4,X5,X6), € (11J=5, T2(X1-X6)= 
Ta(%1,X2,X3,X4X7,X6), € (12) = 5 
Ti1-x6) = Ts(X1,X7,X6), € (13 ) = 2 
T; es la trayectoria más corta de Xx, a xs. 
Un conjunto independiente J de una digráfica D es un conjunto de 
vértices en donde cada dos vértices son no adyacentes. 
1(D) representa el número de independencia y es igual a la máxima 
cardinalidad de un conjunto independiente de vértices en D. 
11
<A 
v: v3 2 
v7 Yg Y9 
Y; 
vs V6 
[v1,V2,V3.Va)[ Vs, Vo, V7 Ve, Wo), [Ws,WesV7 Vet, [WisVoj, (V1,V7,Vaj Son 
algunos conjuntos independientes de vértices, donde K[D) = 5 
Sea D una digráfica. Diremos que S c V(D) es un seminúcleo de D 
si: : 
a) S es independiente 
b) Para cada flecha que va de S a x (en virtud de la condición anterior, 
xe V-S), existe una flecha f que va de x a S. 
v v Y 2. 3 Va 
 
+ 
Ejemplo de Seminúcleo 
S = [v1,v2,v3,va) es un seminúcleo de D. 
Sea N < V(D). N es un núcleo de D si 
1) Nesindependiente 
ii)  Paratodo xe V-N existe una flecha de x a N. 
N = [v¡,v2,V3, Va) es un núcleo de D porque es independiente 
Un conjunto J c V(D) se llama un (4. £ )-núcleo de la digráfica D sí 
(1) para cada x” +x € J tenemos dp(x,y) > € 
(2) para cada y e (V(D) — J) existe una x e J tal que dp(x,x”) <£ 
Un 4-núcleo es un (4,4-2-núcleo; para 4= 2 y € = 1 tenemos un núcleo 
en el sentido de Berge. 
vi va v3 
Va 
Vy 
Va v3 V6 vs 
J= ([v1,v4,v7) es un (3,2)-núcleo 
Vi, Va, 17€) 
do (V1,Va) = 3 
do (V4,v7) = 3 
do (v7,v1) = 3 
t=2 
Sea va € V-J 
13
do (va va)=2 y 2<2 
de la misma manera para v3,Vs, e, Vg,V9 
  
J= £v¡,v5,v9) es un (4,3)-múcleo 
- V ¡»Vs EJ 
do (V1,Vs)= 4 
dp (Vs,V9) = 4 
dp (v9,vi)= 4 
Todo punto que no está en el (£.é)-núcleo xe V(D) — J tiene dp(x,v) < 
3. Donde v es un elemento del (£.£)-núcleo. 
Se dice que un vértice u está conectado a un vértice v en una 
digráfica D si existe un u-v semicamino dirigido (o equivalentemente 
14
E 
un v-u semicamino dirigido) en D. Se dice que una digráfica es 
conexa si cada dos vértices están conectados. Una digráfica que no es 
conexa la llamamos disconexa. La relación “está conectado a” es una 
relación de equivalencia en el conjunto de vértices de una digráfica; la 
subdigráfica inducida por los vértices en una clase de equivalencia es 
una componente conexa o una componente de D. 
   
va 
Y va 
Yi 
O Va 
D, D, 
Va 
vz ) 
vs 
vé 
Mi YES Vs 
o : E? : 
v3 
D, es disconexa, Dz y Dz son fuertemente conexas. 
15
Sea D una digráfica, consideremos en V(D) la siguiente relación 
binaria ru ; uv € V(D) uv v si y sólo si existe una uv-trayectoria 
dirigida en D y una vu-trayectoria dirigida en D; “Y es de 
equivalencia; las clases de equivalencia son las componentes 
fuertemente conexas de D o componentes fuertes; si D tiene una única 
componente fuerte se dirá que D es fuertemente conexa. 
Un ciclo es una sucesión de vértices de D, C = (0,1,2,....n-1) tal que 
(1,1+1) e F(D) (notación mod n). 
Sea £ un número natural 4 > 2. Un conjunto J c V(D) se llamará un 
é-núcleo de la digráfica si: 
1) Para cada x,x” € J tenemos dp(x,x”) > 4 
2) Para cada y e (V(D) — J), existe xeJ tal que dp(x,x” ) < 6-17 
Cuando toda subdigráfica inducida de D tiene núcleo, se dice que D 
es núcleo-perfecta o y se denota NP. Note que el é-núcleo de D es el 
núcleo de una digráfica D” obtenida de D poniendo una flecha xy si 
existe en D una trayectoria dirigida de x a y y de longitud < é-/. 
v 
vi va 
v v3 
v3 
Vg 
Vo Va Va 
Ve Ve 
vs vs 
v3 v7 
vé Ve 
Lv 1,Va,V23= 3 Ív1,V4,V7] €S un núcleo 
Es un 3-núcleo en D 
16
D es bipartita si existe una descomposición de V(D) en dos 
subconjuntos independientes ajenos. 
Vo V 0 1 va Va vi 
va 
D:: D, 
o ve Y 
v7 V6 Vs Va 
Vi= (vo viva Vidy V2=  (fva,Vs,V6,V7) son los conjuntos 
independientes, D; es bipartita y D¿ no es bipartita. 
D es R-digráfica si toda subdigráfica plena de D posee un seminúcleo 
no trivial (es decir, no vacío). 
17 +
v 
vi v3 
vé vs 
R-digráfica 
vi 
Vé 
v7 
  
vs v3 
Va 
D no es R-digráfica 
v 
va 
V 
Va 
Subdigráfica 
vi 
Va Y 
La 
inducida 
[v;,v3,Va) no 
seminúcleo. 
subdigráfica 
por 
tiene 
18
Una digráfica D se llama cíclicamente k-partita (k > 2) si uno puede 
hacer una partición del conjunto V(D) = VO Vi 0 Ve tal que 
si (u,v) es una flecha de D, entonces ue V; y veVis, (notación mod 
k). En el caso de que k = 2 obtenemos una digráfica bipartita en el 
sentido usual. 
La distancia de un punto hacia un conjunto J se define como: 
dy (<,3) = mín [ dp (%y)| y €J3 
Sea T = ([Zp,21»...,Zn) UNA trayectoria de una digráfica D, T es una 
subdigráfica de D. € (T) es la longitud de T. Dados z;,2, € T, 
denotaremos por [ z;,T, z;] el camino dirigido desde z; a 2; contenido 
en T 
Una cuerda del camino dirigido T es una flecha de D de la forma 
(z;,2,) donde j + ¡+1 y [2;,23) C (Zo,21,.=>2n)- 
Una cuerda corta de T es una flecha de la forma (i,i+2) con 
“O<i<n-2. 
vi va va 
Va 
Vea v7 vs 
Vo 
T= [V1,V2,V3,V4,V5»V6sV1,V8) 
(v¡, vs) es una cuerda 
- (va, va) es una cuerda corta 
19
Denotamos a [u*,C,v”] como el subcamino dirigido de u a v contenido 
en C. 
20
Capítulo I 
El objetivo principal de este capítulo -es demostrar que toda R- 
digráfica contiene al menos un núcleo. 
Sea D una digráfica. Diremos que S c V(D) es un seminúcleo de D 
sí: 
a) S es independiente 
b) Para cada flecha que va de S a x (en virtud de la condición 
anterior, xe V-S), existe una flecha f que va de x aS. 
D: 
Yi Y 
v3 
Ys : Va 
S = fv¡,v2,v3Jes un seminúcleo de D 
Sea N < V(D). N es un núcleo de D sí 
i) Nes independiente 
ii) Paratodo xe V-N existe una flecha de x a N.
va 
vi 
v3 
v 
Va 
vs 
N= ( v,, v3, vs j es un núcleo 
D es R-digráfica si toda subdigráfica plena. de D posee un 
seminúcleo no trivial (es decir, no vacío). 
. Y 
Y; va v3 
va 
v 
vé vs Vs 
R-digráfica Subdigráfica 
En este capítulo daremos algunos lemas y teoremas acerca de la 
existencia, primero de seminúcleos de una digráfica y luego de la 
existencia de núcleos de una digráfica. 
22
El resultado principal de este capítulo es el Teorema de Richardson 
“Si D es finita y no posee ciclos impares, entonces D es R- 
digráfica y, por consiguiente posee un núcleo.” 
El primer teorema sobre seminúcleos de digráficas es 1.1 “Todo 
seminúcleo está incluido en un seminúcleo máximo"! 
Empezando con las condiciones para que existan seminúcleos 
llegaremos paso a paso a la definición de núcleo de una digráfica. 
El siguiente Teorema es el 1.2 “Toda R-digráfica posee al menos 
un núcleo”. 
“Si D es finita y no posee ciclos impares, D contiene un 
seminúcleo”", 
Este Teorema nos da una condición para que una digráfica tenga un 
seminúcleo, enseguida veremos el Teorema 
“Todo camino dirigido cerrado de longitud impar contiene un 
ciclo dirigido de longitud impar”! 
Este teorema lo usaremos en forma generalizada en todos los 
capítulos posteriores de este trabajo de tesis. 
Como penúltimo teorema de este capítulo veremos el Teorema 1.5 
“Si D es finita y no posee ciclos impares, entonces D es R- 
digráfica y, por consiguiente posee un núcleo.” 
Y finalmente presentamos el Teorema de Richardson como un 
. 2 
corolario) del teorema 1.5 y resultado de los lemas y teoremas 
anteriores.
D es finita y no posee ciclos impares 
vi 
va 
Vg 
 
v3 
  
v7 Va     
V6 Vs 
N= fv¡,v3,V5,V7) es un núcleo. 
En este Capítulo se demuestra que toda R-digráfica contiene al 
menos un núcleo. 
Pueden demostrarse varios teoremas sobre la existencia de núcleos 
de un modo más transparente, probando que las digráficas que se 
consideran son R-digráficas. 
Como ilustración de este procedimiento, se dará una demostración 
del Teorema de Richardson y se probará que toda digráfica bipartita 
es R-digráfica. 
24
Teorema 1.1. Todo seminúcleo está incluido en un seminúcleo 
máximo. 
La demostración se obtendrá como consecuencia de los lemas Lema 
1.1 y Lema 1.2. 
Lema 1.1. El conjunto de seminúcleos de D, ordenado por 
inclusión es inductivo superiormente. 
Demostración. 
Ser inductivo superiormente significa que toda cadena tiene cota 
superior. 
Sea C una cadena de seminúcleos de D, es decir, una colección de 
seminúcleos tal que si S¡,S2 e C, se tiene S; € S2 o S2 c S;. 
Pongamos U = US 
Sec 
Tenemos que demostrar: 
a) U es independiente, pues si existiera una flecha f(v,,v2) con sus 
dos terminales en U, se tendría v; e S¡ e C para algún S; y vz € 
S2eC para algún S». Luego v,,vz e máx (S¡,S2) €C , lo que es 
imposible. 
U=US; 
Sel 
  
no puede ser
b) Si fes una flecha que va de U a x, existen s y S tales que f= (s,x) 
y seSeC. Como S es seminúcleo existe una flecha f que va de x 
a $ y por consiguiente a U. c.q.d. 
U es independiente. 
Si existiera Í con sus 
dos terminales en U 
  
Lema 1.2, Sea S un seminúcleo de D, B= fv e V-S /no existe 
flecha de v a S] y S* un seminúcleo de la subdigráfica (B) 
inducida por B. Entonces S US” es un seminúcleo de D.
Demostración. 
Por demostrar que S U $” es independiente 
Sean u,v e (S U $”) supongamos que existe una flecha de u a v de 
tal forma que se consideren: 
i) ueS,veS 
li) ueS”,ves” 
111) ueS”,veS 
iv) ueS,veS” 
No pueden cumplirse i) y 1i) por ser S y S” seminúcleos y por lo 
tanto independientes; ¡ii) es imposible ya que S* < B. Finalmente si 
iv) se cumpliera, existiría otra flecha de S” a S, por ser S seminúcleo, 
lo cual satisfaría 111). Luego S U S” es independiente. 
Pongamos A =V-(SUB ). Sea f una flecha de Su S” a x. Si 
xeA, obviamente existe una flecha de x a S y por consiguiente a 
Sus”. 
Six £ A f necesariamente sale de S” (pues no hay flechas de S a 
SUB)) y llega a B — S” y por ser S* seminúcleo de (B), existe f de x 
a $” y por consiguiente a Su S*.Oc.q.d. 
Teorema 1,2.Toda R-digráfica posee al menos un núcleo. 
Demostración 
Sea D una R-digráfica, S un seminúcleo máximo de D y 
=(ve Vv-S | no existe flecha de v a A 
27
e ==" no existe 
Probaremos que B = 2 y por lo tanto $ es un núcleo de D, pues si se 
tuviera B + Z existiría un seminúcleo S” + Y de la subdigráfica (B) 
inducida por B. S U $?” sería un seminúcleo de D por el Lema 1.2 y 
contendría propiamente a S lo que contradice la hipótesis de 
maximalidad de S.O c.q.d. 
En realidad como es fácil de observar, el que D sea una R-digráfica 
implica que toda subdigráfica plena de D contiene un núcleo. 
Que D sea R-digráfica significa que cada subdigráfica inducida 
posee un seminúcleo + J, 
Sea H una subdigráfica inducida de D. Toda subdigráfica inducida 
de H es también una subdigráfica inducida de D y por lo tanto tiene 
seminúcleo no vacío. 
Por lo tanto H es R-digráfica y por el Teorema 1.2 tiene un núcleo. 
Se dará ahora, como una aplicación del Teorema 1.2 el Teorema de 
Richardson. 
28
Teorema L3. Si D es finita y no posee ciclos impares, D contiene 
un seminúcleo. 
Demostración. 
Definamos en V las relaciones Í y mu 
a) v' € v si y sólo si existe en D un camino dirigido de v a v” 
> y eñlo el > > b) v nv” si y sólo si Y WE yv v. 
Ejemplo 
vi Y v3 
v7 v6 Vs Va 
va E v| porque existe un v¡-v2 camino dirigido (v2,V5,V1) 
v¿< va existe un v¿-v2 camino dirigido (va4,v2) 
y Va E va existe un vz-v4 camino dirigido (v2,Vs,V3,Va) 
< Es un preorden, es decir una relación binaria, transitiva y 
reflexiva. 
1) Si v; Z v2 y V2 2 V3 entonces v; <-V3 
a) Si v, <v2 existe un camino dirigido de v, a y; 
b) Si v¿ < vz existe un camino dirigido de v3 a va 
y por lo tanto por a) y b) existe un v3-v, camino dirigido de vz a v;. 
29
Por lo tanto Ú es transitiva y v, < v, ya que (v;) es un camino 
dirigido de v; a v, por lo tanto Á es reflexiva y transitiva. 
"Y Es una relación de equivalencia (es decir, reflexiva, simétrica y 
transitiva) 
Demostración: 
1. Ya vimos v, < vi por lo tanto viv  v, y por lo tanto”Y es 
reflexiva. 
2.Si vi Va > V1 E va y va Ev, por lo tanto 
Si VinyY2> Vary vr 
3. ru estransitiva 
Sup v¡Y va y v2nY v3porlo tanto VÁ Va y VI% Vi y V3% va, por 
la transitividad de £ tenemos que entonces VÍ vV3 y VIS v, por 
lo tanto v¡”Y v3. 
Demostración. 
Sea mo e V un elemento mínimo (Es decir tal que m< mo implique 
my mo) 
Si se toman S = ím e M | que existe un camino dirigido de longitud 
par de ma a mj e Il = ¿m e M | que existe un camino dirigido de 
longitud impar de mo a m) se tiene 
D mo € S 
im Snal=9 
Pues si existiera s e S 1, habría un camino de mo a s de longitud 
par sea C,, y otro de longitud impar, sea C,, y además otro de s a mo, 
Ca, por ser mg s . Por lo tanto habría un ciclo impar, porque si C3 
es par, entonces Cz U C, es un camino dirigido cerrado de longitud 
impar y por el Teorema 1.3 contiene un ciclo dirigido de longitud 
impar. Si Cy es impar, entonces C3 Y C, es un camino dirigido 
cerrado de longitud impar, esto contradice la hipótesis. 
30
C; par 
ES Ss 
6 
Todas las flechas de D que salen de elementos de S ¡legan a I ya que 
si s € S tenemos s e M y existe un camino dirigido de longitud par 
C de mo a s; si (s,u) e F(D) tenemos C U f es un camino dirigido de 
longitud impar de my a u por lo tanto u e 1 ya que de cada vértice de 
I sale alguna flecha hacia S. De aquí se sigue sin más que S es un 
seminúcleo de D.O c.q.d. 
Teorema 1.4. Todo camino dirigido cerrado de longitud impar 
contiene un ciclo dirigido de longitud impar. 
Demostración. 
La demostración se hace por inducción sobre la longitud del camino 
19. Sí € (C) = 3 el mismo es el ciclo porque C = (Zp,2,,Z>,20) 
Z1 % 24 22% 2, 22 % Zy por ser adyacentes. 
2”. Suponemos que todo camino dirigido cerrado de longitud impar 
< 2n+1 contiene un ciclo dirigido de longitud impar. 
3”. Sea C un camino dirigido cerrado con longitud £(C)=2n+ 1 
31
Por demostrar que contiene un ciclo dirigido de longitud impar. 
Sea C = (Zo,Z1s....ZanZo) Zi * z; Y 1i%j entonces C es un ciclo 
dirigido de longitud impar y queda demostrado. 
Si z=Z¡ para alguna ¡xj i<j 
Li+2 
  
C A Zi Zi41 3000, Li z:) y C.= (Z0,Z1».-:» ¿Zi Za Zi4 19 2j4250 ++» »ZnsZg) 
Recorro el camino por fuera 
C, y C, son caminos dirigidos cerrados de longitud < 2n + 1 
Además 
t (Ci) +£ (Co) =£ (C) y €(C) es impar, por lo que se tiene 
que al menos uno: C, o C) tiene longitud impar y sin pérdida de 
generalidad digamós que C, tiene longitud impar. Por hipótesis de 
inducción tenemos que C, contiene un ciclo de longitud impar. Por 
lo tanto C contiene un ciclo dirigido de longitud impar.O c.q.d. 
Corolario (Teorema de Richardson). Si D es finita y no posee 
ciclos impares, D es R-digráfica y por consiguiente, posee núcleo. 
Demostración. 
32
Sea H una subdigráfica inducida de D, H no posee ciclos impares 
(porque es una parte de D que no contiene ciclos impares). Por el 
Teorema 1.4 H tiene un seminúcleo no vacío. Por lo tanto D es R- 
digráfica y por el Teorema 1.2 posee un núcleo.O c.q.d. 
33
Capitulo Il 
“£ y (£,0)-núcleos en digráficas” 
Como vimos en el Capítulo 1, el Teorema de Richardson “Si D es finita y 
no posee ciclos impares, D es R-digráfica y, por consiguiente posee un 
núcleo”. 
En este capítulo veremos algunas generalizaciones del Teorema de 
Richardson y vamos a ver una generalización del Teorema de DuchetÚ: 
“Si todo ciclo dirigido de longitud impar en una digráfica D tiene al 
menos dos flechas simétricas, entonces D tiene un núcleo”. 
Un conjunto J < V(D) se llama un (6.£)-núcleo de la digráfica D sí 
(0 paracada y % x e J tenemos dy(x,y) 24 
(2) para cada x'e (V(D)—.) existe una x e J tal que dp(x,x') <t 
Un k-núcleo es un (4,4-1)-núcleo; para é=2 yt =1 tenemos un núcleo en 
el sentido de Berge. 
vi : v2 Y3 
Va 
Vg 
Vs v7 Vé vs 
En esta digráfica [v1,Va,V7) es un (3,3)-múcleo. 
34
El concepto de (4.£)-núcleo de una digráfica D lo introdujo Kwasnik!Sl 
quien también obtuvo una generalización del Teorema de Richardson 
sobre la existencia de é-núcleos en digráficas. 
Su teorema 2.1 “Sea D una digráfica fuertemente conexa tal que todo 
ciclo dirigido de D tiene longitud =0 (mod Kk), k > 2. Entonces D tiene un 
é-núcleo”., 
También veremos una generalización del Teorema 1.4 (pág. 38) mediante 
el Lema 2.1. Todo camino dirigido cerrado de longitudF 0 (mod k) k> 2 
contiene un ciclo dirigido de longitud F 0 (mod k). 
Incluimos también la demostración de teoremas acerca de la existencia de 
£-núcleos como son los Teoremas: 
Teorema 11.2. “Sea D una digráfica tal que Asym (D) es fuertemente 
conexa. Además supngamos que para cada ciclo dirigido y tal que 
t(NÉ 0 (mod k) al menos una de las dos condiciones siguientes se 
satisface. 
(a) Toda flecha de y es una flecha simétrica en D 
(b) y tiene por lo menos k flechas simétricas. (note que cuando t (y < 
£-1, y debe satisfacer (a). 
Entonces D tiene un ¿-núcleo.” 
Veremos una generalización de este Teorema que es el Teorema I1.3. 
Teorema IL3, Sea D una digráfica que satisface las siguientes 
condiciones: 
(0) Existe myeV(D) tal que para cada x e V(D) existe en Asym(D) 
un ximy-camino dirigido de longitud =1 (mod k) para alguna 0 <i< 
[ y un mpx-camino dirigido. 
(ii) Todo ciclo dirigido y tal que t (y) £0 (mod k) se satisfacen (a) o 
(b) 
35
a) Toda flecha de yes una flecha simétrica de D 
b)  ytiene al menos k flechas simétricas. 
Entonces D tiene un (4 ,t) — núcleo. 
Veremos también dos ejemplos de digráficas que no contienen é-múcleos!*, 
MÍ 
v 
v7 
v3 
Va 
vs 
£v,,vajes un (3,2)- núcleo 
En este capítulo se desarrollan algunos resultados sobre la existencia de 
é-núcleos y (4.€ )-núcleos en digráficas con el propósito de generalizar el 
Teorema de Duchet [3] : “Si todo ciclo dirigido de longitud impar en una 
digráfica D tiene al menos dos flechas simétricas entonces D tiene un 
núcleo.” 
Este a su vez es una generalización del Teorema de Richardson. 
36
Y; Ya 
v7 
v3 
Vá 
vs 
N = (v¡,v3,v6) es un núcleo y el ciclo impar C = [v¡,V2,V3,V4sVs,VesV7,V1) 
tiene dos flechas simétricas. 
En '% Kwasnik define el é - núcleo de una digráfica y obtiene la siguiente 
generalización del Teorema de Richardson (para digráficas fuertemente 
conexas) 
Teorema I1.1. Sea D una digráfica fuertemente conexa tal que todo ciclo 
dirigido de D tiene longitud =0 (mod k), k > 2. Entonces D tiene un k - 
núcleo. 
Antes de demostrar este teorema, enunciaremos y demostraremos el 
siguiente lema. 
Lema 1.1 P Todo camino dirigido cerrado de longitud * 0 (mod k) k> 2 
contiene un ciclo dirigido de longitud E 0 (mod K). 
Demostración. Para k = 2 ya se demostró (Teorema 1.4) 
Supongamos k> 2 
37
Por inducción sobre la longitud del camino cerrado. 
1.Si C es un camino dirigido cerrado de longitud 2. Sea C tal 
camino(vo,v1,Vo) este es el mismo ciclo dirigido de longitud* O(mod k). 
Puesk> 2. 
2”. Supongamos que si C? es un camino dirigido cerrado de longitud + 0 
(mod k) £ (C”) <n, entonces C” contiene un ciclo dirigido de longitud 
F0 (mod k). 
3”. Sea C un camino dirigido cerrado de longitud ng O (mod k) 
C= (Zo,21,Z25-..3Zp-1,Z0) 
(a) Siz,*z¡Wixj entonces C es un ciclo dirigido de longitud + 0 
(mod k) 
(b)  Siz;=z; para alguna i *j denotamos: 
  
ZA 2; 
Vamos a partir el camino dirigido 
C15 (ZosZi)..0, 2: Zi ,Zj41 50>0»Zm-1920) 
C,= (Z;¡,Zi+1,2; +2) 2; =z;) 
C, y C2 forman un camino dirigido cerrado 
t(Cy) +e(C,) =e(C)=n 
¿(C))<n, £(C,) <n 
38
nÉ 0 (mod k) 
Si los dos tuvieran £= 0 (mod k) 
€(C) tendría ¿(C) = 0 (mod k) 
Ya que nz 0 (mod k) se tiene que al menos uno de los dos caminos C, o 
C, tiene longitud É 0 (mod k) 
Supongamos sin pérdida de generalidad que £(C,) £0 (mod k) 
Además €(C¡) <n por hipótesis de inducción tenemos que 
C, contiene un ciclo dirigido de longitud 0 (mod k). Por lo tanto C 
contiene un ciclo dirigido de longitud F 0 (mod k).0 c.q.q.d. 
Ejemplo de un camino dirigido de longitud impar que contiene un ciclo 
dirigido de longitud impar. 
va v3 vs 
v7 
vi 
Va v6 
C1 = (Vr, Va, Va, Va, Vs, Vó, V7, Vs, Va, V)) contiene al ciclo dirigido de 
longitud impar C;1 = (Vs, Va, Vs, Vo). 
Teorema (M. Kwasnik '%) 2.1. Sea D una digráfica fuertemente conexa 
tal que todo ciclo dirigido de D tiene longitud = 0 (mod k), k 2 2. 
Entonces D tiene un k - núcleo. 
Demostración. Sea my e V(D) y para cada 0 < i < k-1 sea N; c V(D) 
definida como sigue: 
= [z € V(D) | existe un mpoz-camino dirigido de longitud = 1 (mod k)j 
39
() Afirmamos que N; AN;=% paraixj, ij ef0,l,...,k-13 
Desde luego si hubiera un z e N; NN; 
Entonces existiría un mpz-camino dirigido C; tal que £(C,) =i (mod k) 
Y un mpz-camino dirigido C, tal que ¿(C,) =j (mod k) 
Puesto que D es fuertemente conexa existe un zmpo-camino dirigido C 
((C¡UC)=(C¿U C)=0 (mod k) 
mo — > 
¿(Cu C)=0 (mod k) porque si fueraÉ 0 (mod k), por el Lema 2.1 
contendría un ciclo dirigido de longitud É 0 (mod k), contradiciendo la 
hipótesis. . : : 
De forma análoga 
t(C¿UC)=0 (mod k) 
¿(C1UC)=(C¡)+e(C) 
((C3UC)=(C,)+e(C) 
de donde 
(Cr) =£(C2) (mod k) 
esto no es posible porque £(C, ) =1' (mod k) 
y. ¿(C2) =j (mod k) 
y ademásix*j coni<j 
j<k 
40 :
(1) Afirmamos que cada N; es un conjunto k-independiente, (esto es: 
para x,y € N;, x % y, dp(x,y) > k.) 
Sean x,y € N; y suponemos que existe una xy-trayectoria dirigida T con 
€ (D) < k-1. Sea C, un mpx-camino dirigido, y Cy un mpy-camino dirigido 
tal que £ (C,) =£ (C,) =1 (mod k) y C un ymo-camino dirigido. 
t (C,¿UTUC)=0 (mod k) [Sit (C,¿UTUC) £ 0 (mod k) contendría 
un ciclo dirigido de longitud 4 0 (mod k) por el Lema 2.1]. Análogamente 
¿(Cy UC) =0 (mod k) 
por lo tanto £ (C¿UTuUC)=f (CyuUC) 
por lo tanto £ (C,)+€ (2) +e (T)=¿ (Cy) +4 7) 
e (C,) + ¿(T)=é(C,) 
y como £ (C,) =£ (Cy) =1 (mod k)i>0 
se sigue £ (T )=0 (mod k). Contradicción pues 0 <f£ (T)<k-1 
C, 
Xx ro 
- e Ñ 
AA, 
0 
111) Claramente toda flecha con punto final inicial en N; tiene punto final 
terminal en Ni +, (notación mod k) 
k-1 
y V(D) =Y N; 
(uy) € F(D) con x e N¡: > y € Ns; 
3 mgx- camino dirigido C con £ (C) =i (mod k) 
sea C U(x,y) 
¿(CU(xy)=1+1 
41
por esto y € Ni 
  
42
Cy = (V1, Va, V3, Vas Vs, Ve, Va, Va ) es un ciclo dirigido de longitud = 8 = 0 
(mod 2) 
J= (v;, v3, Vs, v7 Y es un 2-núcleo 
Teorema 11,2. Sea D una digráfica tal que Asym (D) es fuertemente 
conexa. Además suponemos que para cada ciclo dirigido y tal que 
€ (y) 40 (mod k) al menos uno (a) ó (b) se satisface. 
(a) Toda flecha de y es una flecha simétrica de D 
(b) y tiene por lo menos k flechas simétricas. (note que cuando £ (y) < 
k-1, y debe satisfacer (a). 
Entonces D tiene un k-núcleo. 
Demostración. 
Sea mo € V(D) y para cada 0 < i < k sea N;c V(D) definida como sigue: 
N¡= (z € V(D) | existe un mpz-camino dirigido de longitud = i (mod k) 
contenido en Asym(D)) 
DN; AN =9 paraixJ, ij e(0,l,....k-13 
Supongamos que N; AN; +0 
SeazeN NN ¡xj 
Sea C, un moz-camino dirigido en Asym(D) con £ (C;) =i (mod k). 
Sea C, un mpz-camino dirigido en Asym(D) con € (C2) =j (mod k). 
Como Asym (D) es fuertemente conexa existe un C3 z-mp-camino dirigido 
en Asym(D) 
¿(CU Cs) =e(C,)+e(C3) 
C,U C; es un-camino dirigido cerrado en Asym (D) 
£ (CU C3) = 0 (mod k) porque si no tendríamos que €; U (3 es un 
camino dirigido cerrado de longitud 4 0 (mod k) y por lo tanto contiene 
un ciclo dirigido de longitud £ O (mod k) y asimétrico, contradiciendo (a) 
y (b). 
Análogamente ¿(CU Cy) = 0 (mod k) 
£(C¡u C3)=0 (mod k) : 
((C2U Cy) =0 (mod k). 
43
Por lo tanto ¿(CU C3) =£(C2¿U C3) 
t(C)+1(C3) =e(C2) +0(C3) 
de aquí 
t(C,) =t(C,) para i+j CONTRADICCIÓN. 
N¡ NN¡= 4 ya tengo una partición de los vértices de D. 
 
  
11) Para x,y € N;, x % y, dp (x,y) > k 
Suponemos por contradicción que existe una xy-trayectoria dirigida T en 
Decon ¿(M<k-1 
Supongamos que ¿(T) < k-1 
Sea C, un mox-eamino dirigido asimétrico tal que t(C,) =i (modk) 
Sea Cy un mpy-camino dirigido asimétrico tal que £ (Cy) =i (mod k) 
Existe C ymo-camino dirigido asimétrico por ser Asym(D) fuertemente 
conexa. 
Entonces 
Cy U TU C es un camino dirigido cerrado con a lo más k-1 flechas 
simétricas (las flechas de T), por lo tanto £(C,¿U TU C) = 0 (mod k) de no 
ser así por Lema 2.1 contendría un ciclo de longitud É 0 (mod k) no 
simétrico y con a lo más k-1 flechas simétricas. CONTRADICCIÓN (a la 
hipótesis). 
Análogamente 
¿(C,u C)=0 (mod k) 
t(Cyu C)=(C,U TU C) 
(Cy) HC) = (Cy) +£(C) + e(T) 
t(Cy) =£(C,) +£(D) y €(T)=0 (mod k) 
CONTRADICCIÓN. 
C, 
mo 
  
45
Porque 1<f (D)<k-1 
iii) Cada flecha asimétrica con punto final inicial en N; tiene punto final 
terminal en N;+, (notación mod k) y 
k-1 
VOD)=2N; 
Dada una flecha asimétrica xy tal que x eN; demostrar que y € Nis] 
K-1 
VD)= ÓN: 
Sea (u,v) una flecha asimétrica, existe un mpu-camino dirigido asimétrico 
C; con ¿(C, ) =i (mod k) C, < Asym (D) por lo tanto C, U (u,v) es un 
camino dirigido asimétrico de my a v con£(C¡u (uv) =1(C,)+.1=i+1 
(mod k) . 
Por lo tanto v € Ni+1 
Ejemplo. Para k > 3 sea H, la digráfica definida como sigue: 
46.
V(Hy) = £0,1,....k*k+13 
F(H) = (GD) li ef0,L...k?+k 0408 +k+ 1,0) u 
((k +2, ik+)li e (1,2....k3). 
Supongamos que Hy tiene un k-núcleo N, claramente N N 10,1,...,k- 1 
O. Síie (0,1,....k- 1) 1 N, entonces N= (ik+i2k+i,...k +1) k?+i+ 
1 £ Ny no hay trayectoria dirigida de longitud a lo más k-— 1 del vértice k? 
+i+lenN. : 
Se concluye que H; no tiene k-núcleo. 
47
Ejemplo 2.1 para k = 3 Sea H; la digráfica definida como sigue: 
V(Hx) = (0,1,2,3,4,5,6,7,8,9,10,11,12,133 
F(H1)=((0,,(1,2),(2,3),3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10), 
(10,1),1,12),02,13),(13,0),(5,4),(8,7),(11,10) 
13 
12 
11 
  
48
Cuando k = 4 
V(Ha) = £0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,213 
F(H=1(0,1),(1,2),(2,3),3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10), 
(10,11),011,12),02,13),13,0),65,4),8,7),011,10),011,12),(12,13), 
(13,14),04,15),15,10),6,13,017,19),01 8,19),(19,20),(20,21),(21,0), 
(6,5),(10,9,(14,13),18,17)) 
  
49
Ejemplo 2.2. Para k> 2 sea D, la digráfica definida como sigue: para cada 
¡ € V(H,) sea T una iz-trayectoria dirigida de longitud k de tal suerte que 
TÍNTÍ=1z) TÍN$H)=i 
Y sea : 
D,= H, u Tj 
Es fácil ver que no tiene k-núcleo y Asym(D;) es una digráfica conexa. 
Para k = 3 tenemos: 
  
50
El siguiente resultado es una generalización del Teorema 11.2 
Teorema 11.3. Sea D una digráfica que satisface las siguientes 
condiciones: 
(i) Existe my V(D) tal que para cada x eV(D) existe en Asym(D) 
un xmy-camino dirigido de longitud = i (mod k) para alguna 0 <i 
<1 y un mox-camino dirigido. 
(ii) Todo ciclo dirigido y tal que ¿ (y) F 0 (mod k) se satisfacen (a) 
o (b) - 
a) Toda flecha de y es una flecha simétrica de D 
b) y tiene al menos k flechas simétricas. 
Entonces D tiene un (4 .¿ ) — núcleo. 
Asym(D) 
Cc; = xMog 
((C,)= 1 (mod k) 
C, es un mgx-camino dirigido. 
DEMOSTRACIÓN. 
Sea N = (ze V(D) l existe un zmy-camino dirigido de longitud = 0 (mod k) 
contenido en Asym(D)) 
“() Six,y e N xx y entonces dp (x,y) > k 
Sean x,y e N y supongamos que existe una xy-trayectoria dirigida T con 1 
(D) <k-1 
" Sea C, un xmp-camino dirigido de longitud = 0 (mod k) 
Sea C, un ymp-camino dirigido de longitud = 0 (mod k) 
51
Contenidos en Asym(D) y sea 
C un mex-camino dirigido contenido en Asym(D) 
El Lema 2.1 : 
y la hipótesis (11) implican que 
t (C UC) =0 (mod k) 
Si no se diera esta congruencia,.es decir si 
t(CUC;)% 0 (mod k), 
tendríamos que (C U C,) es un camino dirigido cerrado con longitud 0 
(mod k) y está contenido en Asym(D). Por el Lema 2.1 C U C, contendría 
un ciclo de longitud £ 0 (mod k) contenido en Asym(D). 
CONTRADICCIÓN. 
(y todos los ciclos o eran simétricos o contienen k > 1 flechas simétricas.) 
Análogamente £(Cy U CU T) =0 (mod k) : 
Por lo tanto 
t(CucC;y=(CyuUCuUT) 
52
por lo cual 
ULT+ Cy) = (Cy) +HUCIFe(T) 
por lo tanto 
t(C)y= (0) +e(T) 
y como £(C,) =£(C,) = 0 (mod k) 
tenemos £(T) = 0 (mod k) contradicción con la hipótesis. 
Ejemplo del Teorema 2.3 
vi 
va 
v6 
v3 
-Ys 
[v va) es un (3,2)-núcleo de D y se satisface que la longitud del ciclo 
dirigido C = [v;,v6,Vs,Va,v3,V1] tiene.£ (C) É O (mod k)y tiene al menos 3 
flechas simétricas. 
53
Capítulo HI 
“¿-núcleos en digráficas” 
El objetivo de este capítulo es obtener una caracterización de una 
digráfica ciclicamente k-partita y fuertemente conexa. Como una 
consecuencia, obtendremos una condición suficiente para que una 
digráfica tenga un k-núcleo. 
El primer teorema del capítulo es el Teorema 11.11% Sea D una 
digráfica fuertemente conexa, D es una digráfica cíclicamente k- 
partita si y sólo si existe una subdigráfica fuertemente conexa H 
C D tal que todo ciclo de longitud % 0 (mod k;) tiene al menos dos 
flechas en F(D) - F(H). 
Este teorema es una caracterización de una digráfica cíclicamente k- 
partita. 
Una digráfica D se llama cíclicamente k-partita (k > 2) si uno puede 
hacer una partición del conjunto V(D) = Vo + V, +... +Vy., tal que si 
(u,v) es una flecha de D entonces ue V¡ y veVis, (notación mod 
k). En el caso de que k = 2 obtenemos la digráfica bipartita en el 
sentido usual. 
El otro teorema que veremos en el capítulo es el Teorema 111.2%, 
Sea D una digráfica tal que Asym(D) es fuertemente conexa. 
Además suponemos que para cada ciclo dirigido y tal que 
¿(y ) £ 0 (mod k;) se satisface (a) o (b). 
(a) Toda flecha de y es una flecha simétrica de D 
(b) y tiene por lo menos k flechas simétricas. 
Entonces D tiene un k-núcleo. 
54
M] 
v: 
Vi 3 
Va 
v9 
vs 
Vg 
V 
va 6 
[v,,v4,v7) es un 3-núcleo 
En este capítulo obtenemos una caracterización de las digráficas 
ciclicamente k-partitas fuertemente conexas, generalizaremos el 
capitulo I en el que una digráfica bipartita tiene un núcleo, y 
obtendremos una condición suficiente para que una digráfica tenga 
un k-núcleo. 
Recordemos el siguiente Lema que será usado en la demostración 
del Teorema HI 1 
Lema 1.1% Todo camino dirigido cerrado de longitud 0 (mod Ly), 
k >2 contiene un ciclo dirigido de longitud É 0 (mod k). 
Teorema INL1% Sea D una digráfica fuertemente conexa, D es 
una digráfica cíclicamente k-partita si y sólo si existe una 
subdigráfica fuertemente conexa H c D tal que todo ciclo de 
longitudF 0 (mod k) tiene al menos dos flechas en F(D) — F(H). 
55
Demostración. => 
Es claro que si D es una digráfica fuertemente conexa y cíclicamente 
k-partita, entonces todo ciclo dirigido de D tiene longitud = 0 (mod 
k). Así cuando D es una digráfica fuertemente conexa y ciclicamente 
k-partita, la subdigráfica H = D satisface las propiedades requeridas. 
<= Supongamos ahora que existe una subdigráfica fuertemente 
conexa H < D tal que todo circuito de longitud É 0 (mod k;) tiene al 
menos dos flechas en F(D) — F(B), 
Sea mo e V(D) y para cada 0<i<k-l sea N; < V(D) definida 
como sigue : 
-N;= fz e V(D) | existe un mpgz-camino dirigido contenido en H de 
longitud = i (mod k)) 
i. Afirmamos que N;¡ A N;¡= Y parai%j, ij e (0,1,....k-13. 
Suponemos que existe un ze N; A N; entonces existe un moz-camino 
dirigido T, contenido en H tal que € (T¡) = i (mod k) y existe un 
mpz-camino dirigido T¿ contenido en H tal que € (T>) = j (mod k), 
puesto que H es fuertemente conexa existe un zmp-camino dirigido 
Tx contenido en H; 
56
(Ti) =1i(modk) - 
¿(T,) =j(modk) . 
¿(T¡U T3) = (Ti) + e(T5) 
¿(T2U T3) = (To) + £CT3) 
¿(T, U T3) = 0 (mod k) porque si 
-¿(T,¡UT3)É O (modk) entonces 
T, UT, es un camino dirigido cerrado de £É 0 (mod k) por el Lema 
1.1 contendría un ciclo y € T, U T3 y T, U T3 Cc H por lo tanto 
tendríamos un ciclo dirigido de longitud 4 0 (mod k) contenido en 
H contradiciendo la hipótesis, por lo tanto 
¿(Tu Ty) = 0 (mod k) análogamente £(Tau T3) = 0 (mod k) 
por lo tanto ¿(T,) + £(T3) =£(T,) + ¿(T3) (mod k) 
por lo tanto ¿(T,) =£(T») (mod k) (14). Y 
ii Afirmamos que cada N; es un conjunto independiente de D (¡.e. 
no existe flecha de D con ambos puntos terminales en N; ) 
Sean x,y € N; y suponemos que (x,y) e F(D) 
Mo 
57
Sea T, un mpx-camino dirigido contenido en H 
T, un mpy-camino dirigido contenido en H tal que £(T,) =¿(T,) =1 
(mod k) y sea T un ymg-camino dirigido contenido en H (T existe 
puesto que H es fuertemente conexa). Ya que Ty U T es un camino 
dirigido cerrado contenido en H se sigue que £(T,yU T) = 0 (mod k) 
ya que si ¿(T,U Ty? 0 (mod k) por el Lema 1.1 contendría un ciclo 
de longitud% 0 (mod k) y contenido en H Y T,uU (y) UT es un 
camino dirigido cerrado con a lo más una flecha en F(D) —F(H) del 
Lema 1.1 y de la hipótesis que ¿(T,U (x,y)u T= ¿(T,UT)=0 
(mod k) Porque si ¿(T,yu T)É 0 (mod k) contendría un ciclo de 
longitud % 0 (mod k) con a lo más una flecha en F(D) — Fay 
t(T,U (xy) U T) =¿(Tyu T)=0 (mod k) 
(Ty) +£(uy) + UR =0 (Ty) +££1 (modk) 
¿(T,) + 1 =£(T,) (mod k) 
¡+ 1=i(modk) 
1 =0 (modk) Y 
iii Toda flecha con punto final inicial en N; tiene punto final 
terminal en N;+¡ (notación mod k) y V(D) = Uso N;. 
Sea (x,y) una flecha con punto final inicial en N; se sigue de (ii) que 
ye Nj para alguna j e (0,l,...k-13-(13. Sea T, un mpx-camino 
dirigido contenido en H con £ (T,) = 1 (mod k), T, un mpy-camino 
dirigido contenido en H con £( T,) =j (mod k) y T un ympg-camino 
dirigido contenido en H (recuérdese que tal camino existe porque H 
es fuertemente conexa). Tenemos T,Uu (xy) U T es un camino 
dirigido cerrado con a lo más una flecha en V(D) — V(H) así se sigue 
del Lema 1.1 y de la hipótesis que £(T,U (x,y) U T) = 0 (mod k) 
(Sic(T,U (uy) UT) £ 0 (mod k) tendríamos un ciclo de 
longitud + 0 (mod k) con a lo más una flecha en F(D) — FEOY ) 
también £(T, u T)= 0 (mod k) (Si Si £(T, U T) £ 0 (mod k) 
tenemos que por Lema 1.1 Ty UY T contiene un ciclo de 
longitud É 0 mod k y sería un ciclo de longitud $ 0 (mod k) 
58
contenido en HY ) por lo tanto ¿(T,) + 1 =€(T,) (mod k) yj=i+1 
(mod k) y porque j e(0,1,....k-1) se sigue quej=1 +1. 
Concluimos de (i), (ii) y (iii) y de la definición (**) que D es 
ciclicamente k-partita.O c.q.q.d. 
  
Teorema 11.2. Sea D una digráfica tal que Asym(D) es 
fuertemente conexa. Además suponemos que para cada ciclo 
dirigido y tal que € (y ) + 0 (mod k;) se satisface (a) o (b). 
(a) . Toda flecha de y es una flecha simétrica de D 
(b) y tiene por lo menos k flechas simétricas. 
Entonces D tiene un k-núcleo. 
Demostración. . 
i) Sea mp € V(D) y para cada 0 <i<h sea N; € V(D) definida 
" "como sigue . 
N;¡= (z e V(D) | existe un moz-camino dirigido de longitud = i (mod 
k) contenido en Asym(D)) 
59
  
i) NAN=2 parai*j, ij e (0,1,....k-13. 
Supongamos que N; 1 N¡+ D, seaze N; AN; i Aj, 
C, es un mpz-camino dirigido en Asym(D) con £(C;) =i (mod k) 
C, es un mpz-camino dirigido en Asym(D) con €(C2) =j (mod k) 
Como Asym(D) es fuertemente conexa existe Cy un camino dirigido 
de za my en Asym(D), 
entonces ¿(CU C3)=t(C, )+£(C3) 
Cu Cy es un camino dirigido cerrado en Asym(D) ¿(C, U C3) = 0 
(mod k) porque si no tendríamos que €, U Cg es un camino dirigido 
de longitud £ 0 (mod k) y por lo tanto contiene un ciclo dirigido de 
longitud £ 0 (mod k) y asimétrico, contradiciendo (a) y (b). 
Análogamente, ¿(C¿U C3)=0 (mod k) 
¿(CU C;)=0 (mod k) 
¿(CU C3)=0 (mod k) 
Por lo tanto ¿(CU C3)=8(C¿U (3) 
e(C, ) +05) =e(Co ) +0 
de aqui t(C, ) =£(C> y paraizj.Y 
60
he 
N;¡n N;= JD ya tengo partición de V(D) 
  
N, “Na 
ti) Para: X,y € Ni, x % y, doy) >k 
Suponemos que existe una xy-trayectoria dirigida T en D con 
e(T)<k-1 
C, es un mpx-camino dirigido asimétrico tal que (Cy) =1 (mod k) 
Cy es un moy-camino dirigido asimétrico tal que ¿(C,) =1 (mod k) 
Existe C un ymo-camino dirigido tal camino existe por ser Asym(D) 
fuertemente conexa 
Xx 
C, 1 
m bee 
a,
Contradiciéndose entonces (C, UY T U C) es un camino dirigido cerrado con a 
lo más k-1 flechas simétricas , por lo tanto £(C,W Tu C) £ 0 (mod k), 
sit(C,U TuC) £0 (mod k), contendría un ciclo de longitud 0 (mod k) no 
simétrico y con a lo más k-1 flechas simétricas. Contradiciéndose la hipótesis. 
Análogamente 
¿(Cy u C)=0 (mod k), 
¿(CU TU )=0 (mod k), 
t(CyU C)=t(C,UTUC), 
(Cy) + UEÍ = (Cy) + LEÍ + (T), 
(Cy) =e(C)+e(T), 
y £(T)=0 (mod k). Contradicción 
porque habíamos supuesto que 1<£(T)<k-1 
iii) Cada flecha asimétrica con punto final inicial en N; tiene punto final 
terminal en N;+, notación mod k) y 
k-1 
VOD)= UN; 
¡=0 
Tenemos que demostrar que dada una flecha asimétrica xy con x EN; tiene 
y ENia 
k-1 
V(D)= UN; 
i=0 
Sea (u,v) una flecha asimétrica, existe un mpgu-camino dirigido C, con 
€ (C;) = i (mod k), C; C Asym (D) por lo tanto C, U (u,v) es un camino 
dirigido asimétrico de my a v con € (C, U (u,v)) =£(C;) + 1 =i +1(mod k), por 
lo tanto v € Ni+/, €.q.d. 
tt 
62
Capítulo IV 
Una condición suficiente para la existencia de é-núcleos en 
Digráficas 
En este capítulo veremos una condición suficiente para la existencia 
de k-núcleos en digráficas. 
Presentamos una generalización del teorema de Kwasnik sobre la 
existencia de k-núcleos en digráficas fuertemente conexas, el cual es 
una generalización del Teorema de Richardson: 
El resultado principal de este capítulo es el Teorema 1V.1. Sea D 
una digráfica tal que Asym (D) es fuertemente conexa y cada 
ciclo dirigido de longitud 3 tiene al menos dos flechas simétricas. 
Si para cada ciclo dirigido y de D con l (y) 4 0 (mod k) se 
satisfacen (a) ó (b), donde: 
(a) y tiene dos flechas simétricas, 
(b) y tiene cuatro cuerdas cortas 
entonces D tiene un k-núcleo (k > 2). 
Para la demostración del Teorema IV.] vamos a utilizar y demostrar 
el Lema IV.1. "Sea D una digráfica, u, v, w € V(D), T, es una 
trayectoria dirigida de u a v, T, es una vw-trayectoria dirigida de 
longitud a lo más 1 (posiblemente v = w), T, es una wu-trayectoria 
dirigida y denotamos por y=T, UT, UT. Sit (NÉ 0 (mod k), k > 
2, entonces existe un ciclo dirigido C contenido en y con t (C)JF 0 
(mod k) y vértices u*,v*,w” e V(D), tal que [ 12, Cyv? les es una 
subtrayectoria de T,, [ v, Cw” ] es una subtrayectoria de T>, y 
[ w”,C,u? ] es una subtrayectoria de T,, (posiblemente £ (T)=0y 
posiblemente £ [ v*, Cyw” ] = 0)”. 
* Denotamos a [ x=”, C,v” ] como el subcamino dirigido de u a v 
contenido en C). 
63
Teorema [M Kwasnik] Sea D una digráfica fuertemente conexa, si 
todo ciclo de D tiene longitud =0 (mod K), k > 2. Entonces D tiene 
un k-núcleo. : 
vi Ya 
Va V3 
y7 Na Va 
Va vs 
D 
En esta digráfica todo ciclo dirigido de D tiene longitud = 0 (mod k), 
k>2. 
D tiene un 2-núcleo que es N = [v,, Va, Vs, Va) 
El resultado principal de este capítulo es el Teorema I1V.] y para 
demostrarlo es necesario demostrar primero el siguiente Lema. 
64
Lema I V.L Sea D una digráfica, uu, v, w € V(D), T, es una 
trayectoria dirigida de u a v, T, es una vw-trayectoria dirigida de 
longitud a lo más 1 (posiblemente v = w), T, es una wu-trayectoria 
dirigida y denotamos por y=T, OT, OT, Sit(N ¿0 (mod K), 
k 2 2, entonces existe un ciclo dirigido C contenido en y con 
Ct (C)É 0 (mod K) y vértices u*,v”,w” € V(D), tal que [ %, Cv" ] (en 
donde [ w, Cjv? ] denota la trayectoria dirigida de u' a v' 
contenida en C) es una subtrayectoria de T,, [ v”, C,w” ] es una 
subtrayectoria de Ta, y  [w',Cu' ] es una subtrayectoria de T,, 
(posiblemente t(T) =0 y posiblemente € [ v”, C,w” ] =0). 
Demostración. 
ví 
u 
O v 
» 
Ta 
a w 
T; 
La demostración será por inducción sobre € (y) 
Si £ (y) = 2, claramente y es un ciclo requerido con las propiedades 
requeridas. 
< 
65
Supongamos que el resultado es válido para y” con las propiedades 
del Lema 2.1 tal que £(y') <n y sea y =T, U T, U Ty con € (y) =n. 
Si V(T) MN V(T3) = [uj, entonces v % w, y es un ciclo dirigido y el 
resultado es inmediato. 
T, 
Si MT) NO V(T3) + (fu), tomamos z el primer vértice de T; 
diferente de u que está en T3. Ya que 1 (y) %0 (mod k) tenemos que al 
menos una de las siguientes afirmaciones se cumple: 
  
66
a) ¿([u, T¡z]u[z, T3,.u ]) 0 (mod k) 
b) ¿([z, T,w]u T2zU[ v, T3,z 1) £ 0 (mod k) 
Si (a) se cumple tomamos y” =([u, T¡jz]u[z, Tzu), w =u, y = 
w” = z, claramente 1 (y?) < n, y por la hipótesis de inducción sobre y 
tenemos que existe un ciclo dirigido C contenido en y” y por lo tanto 
en y con las propiedades requeridas. 
Si (b) se cumple tomamos y? = [z,T¡,w] U Ta U [v,T3,z] 
w = y” =w” =z claramente £ (y) < n y por la hipótesis de inducción 
tenemos que existe un ciclo C < y” y por lo tanto contenido en y con 
las propiedades requeridas.7 c.q.d. 
1 
Teorema 1V.1. “Sea D una digráfica tal que Asym (D) es 
fuertemente conexa y cada ciclo dirigido de longitud 3 tiene al 
menos dos flechas simétricas. Si para cada ciclo dirigido y de D 
con 1 (y) £ 0 (mod k) se satisfacen (a) ó (b), donde: 
(a) y tiene dos flechas simétricas, 
(b) y tiene cuatro cuerdas cortas 
entonces D tiene un k-núcleo (k > 2). 
v1 
vo 
Vg 
va 
Va 
Va 
v7 
VA 
Va 
67
DEMOSTRACIÓN: 
Sea mo € V(D) y para cada 0 < i < k sea N; < V(D) definida como 
sigue: 
N; = [z € v(D)! la trayectoria dirigida más corta desde mp a z 
contenida en Asym (D) tiene longitud =i (mod k) ; 
k-1 
(1). UN;=V() 
Por ser Asym (D) fuertemente conexa para un z e V(D) existe una 
trayectoria (tomamos la más corta) asimétrica de my a z. Esta es 
congruente con algún 0 < i < k (mod k), por lo tanto z e N;. Por lo 
tanto 
k-1 
V(D) = UN =V(D) 
(2). Toda flecha de D con punto final inicial en N; tiene punto final 
terminal en N;,, (notación módulo k). 
Sea (x,y) una flecha con punto terminal inicial en N; y tomamos la 
trayectoria dirigida más corta T, de my a x contenida en Asym(D), la 
trayectoria dirigida más corta Ty de mp a y, y T la trayectoria 
dirigida más corta de y a mp contenida en Asym(D), notaremos que 
tales trayectorias existen porque Asym(D) es fuertemente conexa. 
68
  
(3.).4(T ) = 1 (mod k) 
Esto es consecuencia de la definición de N; y del hecho que x € N;. 
(3.3). T, no tiene cuerda corta en D. 
Ya que T, es la trayectoria dirigida más corta de mo a x contenida en 
Asym(D). Sea T, = [mo = Zo, Zi»... Zn = X] 
Si (2, 2342) 0< 1 < n-2 es una cuerda corta de T, tenemos [Z;, Zi+1, 
Zi»»,z] es un triángulo dirigido con a lo más una flecha simétrica 
nótese que si (Z;, z; + 2) es flecha asimétrica tendríamos T”, (Zo, Za, 
.ZisZis2)-,Z) Una mpx trayectoria dirigida contenida en Asym(D) 
contradiciendo la elección de T, (porque (f(Z;,Zi+1), (Zi+1,Zi+2)) E 
F(T,) c F(Asym(D)) contradiciendo los supuestos del Teorema 2.1. 
Concluimos que T, no tiene cuerdas cortas en D. 
Similarmente podemos demostrar las siguientes dos afirmaciones: 
(3.3). F, no tiene cuerda corta en D 
(3.4). T no tiene cuerda corta en D. 
Ahora analizaremos los dos posibles subcasos: 
(Caso 1.) y € Tx 
"Sy
Aquí analizaremos los diferentes subcasos 
(Caso 1.a) 1 ([mo,T.,y] Y T)F 0 (mod k) 
En este caso se sigue del Lema 2.1 (tomando u = My, V= W= y = Zi, 
w 
O y 
Zi 
T,=[mo Ty]  Ta=[v=w=y=z¡]y T3=T 
que existe un ciclo dirigido C contenido en [mo Ty] + T con 
¿(C)É 0 (mod k) y vértices u”,v”,w' tales que [u”,C,v”] es una 
subtrayectoria de T y v' = w [ w,C,w” ] es subtrayectoria de T y 
tenemos 
(1.a.1) C c Asym(D) 
esto se sigue del hecho de que € < [mo, Ty] Y T <T, UT < Asym 
(D) 
70
(1.2.2) [u”,C,v*] no tiene cuerda corta 
Es una consecuencia de (3.2) y del hecho de que [u*,C,v*] es una 
subtrayectoria de [mo,T,,y] la cual es una subtrayectoria de T,.. 
Similarmente 
(1.a.3) [v”,C,u*] no tiene cuerda corta. 
Ya que 1(C ) ¿ 0 (mod k) se sigue de (1.1.1) y los supuestos del 
Teorema 2.1 que C tiene cuatro cuerdas cortas. Sea 
C=[u =Zp, Z1, ..0,Zi21, Zi VW”, Zi+jo0.0> Zp> Zo] 
Tenemos de (1.a.2) y (1.a.3) que las únicas posibles cuerdas cortas 
de C son (Z;.1, Zi+1) y (Zp,Z1) contradiciendo las hipótesis del Teorema 
2.1. 
21 T, A y 4 
— > 
mo ( Zi 
E 
Zn T 
(Caso 1.b) 1 ([y,T,x] Y [Ex,yD E 0 (mod k) 
En este caso tenemos el ciclo dirigido 
C= [y, Tx] Y [x.y] = [y = Wo, Wo, ....Wn=X, Wo] 
Con €(C )É 0 (mod k). Ya que [y,T,,x] es una subtrayectoria de T, y 
T, C Asym (D) tenemos que la única posible flecha simétrica de C 
es (x,y). Por lo tanto se sigue de los supuestos del Teorema 2.1 que 
C tiene cuatro cuerdas cortas. Pero se sigue de (3.2) y del hecho que 
[y,T,.x] es una subtrayectoria de T, que las únicas cuerdas cortas 
posibles de C son: (Wp.1, Wo) Y (Wn, wr), contradiciendo los 
supuestos del Teorema 2.1 
Así el único caso posible es: 
(Caso 1.c) € ([y,T,,x] uv T) = 0 (mod k) y £ ([y.,T,,x] U (y) = 0 
(mod k) 
mn
en este caso tenemos que 
¿([mo, Ty] Y T) + (ly, Tox] Y [x,y]) = 0 (mod k) 
es decir £(T, U [x,y] y T) = 0 (mod k) 
Por lo tanto ¿(T, U [x,y] y T) =¿([mo,Tx.y] Y T) (mod k) y se sigue 
que ¿(T, U [x,y] ) = 1 ([mo,T,.y] ) (mod k). Entonces 
1 ([mo,T,.y] ) =1(T,) + 1 (mod k) 
y tenemos de (3.1) que | ([mo,T,.y] ) =1+1 (mod k) 
Finalmente nótese que siendo T, la trayectoria dirigida más corta de 
mo a x contenida en Asym(D) y [mo,T,,y] es una subtrayectoria 
dirigida de T, tenemos que [mo,T,.y] es la trayectoria dirigida más 
corta de mo a y contenida en Asym(D). Concluimos de la definición 
de Ni, que y € Ni. 
(Caso 2) y € T, 
Mo     T, 
En este caso probaremos que £(T,) = ¡+1 (mod k) 
De nuevo analizaremos varios casos posibles. 
(Caso 2.a) ¿(Ty UT) % 0 (mod k) 
En este caso se sigue del Lema 2.1 (Tomando u = mp, v = w = y, T, 
=T,, T, = (v = w = y) y Tz = T) que existe un ciclo dirigido C de 
longitud £(C) 40 (mod k) 
72
w,v =w e V(C) tal que [u”, C, v”] es una subtrayectoria de T, y 
[v”, C, u”] es una subtrayectoria de T. Ya que T, c Asym(D) y Tc 
Asym(D) tenemos que Cc Asym(D). 
Por lo tanto se sigue de los supuestos del Teorema 2.1 que C tiene 
cuatro cuerdas cortas. Pero se sigue de (3.3), (3.4) y por los hechos: 
que [u”, C, v”] es una subtrayectoria de T, y [v”, C, u'] es una 
subtrayectoria de T que 
si C=[u? = Zp, 21, ..0,Zi-1, Zi Y, Zitto=»"» Zn» Zo] 
entonces, las únicas posibles cuerdas cortas de C son: (Zp.1, Zo) y 
(Z;.1, Zi+1), contradiciendo la hipótesis del Teorema 2.1. 
(Caso 2.b) £(T, U [x,y] UT)É 0 (mod k) 
(Tomando u = mo, V = Xx, w= y, T, = T,, T¿ = (y) y T3 = T) que 
existe un ciclo dirigido C de longitud ¿(C)% 0 (mod k) u?, v”, w” € 
V (C ) tal que [u?, C, v”] es una subtrayectoria de T,, [v”, C, w”] es 
una subtrayectoria de [x,y] (posiblemente v” = w”) y [w”,C,u”] es 
una subtrayectoria de Tz. Ya que T, < Asym(D) y T < Asym(D) 
tenemos que la única flecha simétrica de C es (x,y). Por lo tanto se 
sigue de los supuestos del Teorema 2.1 que C tiene cuatro cuerdas 
cortas. Además; si C = [u? = Zo, Zj, «Zi, Zi VW, Zi WI, Zi4250=->Zm 
Zo] entonces se sigue de (3.2), (3.4) y por los hechos: 
T 
Zn] po 
Zn Zi+1 
73
Zn-1 
  
[u”,C,v”] es una subtrayectoria de T,, [w”,C,u”] es una subtrayectoria 
de T, que las únicas posibles cuerdas cortas de C son (Z;.1, Zi+1) y 
(Zi,Zi12), y (Zm 21), contradiciendo la hipótesis del Teorema 2.1. 
contradiciendo los supuestós del Teorema IV.1 
Concluimos de los casos (2.a) y (2.b) que 
(Caso 2.c) £(T, UT) =0 (mod k) y 
¿(Tu [x.y] UT) = 0 (mod k) 
Por lo tanto 
¿(Ty 0 T) =e(T, U [x.y] UT) (mod k) 
así : 
(Ty) =£(T, U [xy] ) =e(T,) + 1 (mod k) 
y siendo ¿(T,) = i (mod k) tenemos £ (Ty) = ¡+ 1 (mod k) 
y concluimos que ye Nj+1. 
Claramente se sigue de (1), (2) y (3) que cada N; (0 < 1 < k-1) es un 
k-núcieo de D y el Teorema IV.1 está demostrado. 
74
Referencias: 
[1]. V. Neumann-Lara, Seminúcleos de una digráfica, An. Inst. 
Mat. II Univ. Nac. Autónoma México (1971). 
[2]. M.Richardson, Extension Theorems for solutions, Ann. Math. 
(2) 58 (1953), p. 573. 
[3]. P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 
(1980) 93-101. 
[4]. Galeana -Sánchez Hortensia, On the existence of (4. £)-Kernels 
in Digraphs, Ann. Discrete Math. 85 (1990) 99-102. 
[5]. Galeana -Sánchez Hortensia, On the existence of kernels and 
¿-kernels in Digraphs, Ann. Discrete Math. 110 (1992) 251-255. 
[6]. M. Kwassnik, The generalization of Richardson Theorem, 
Discussiones Math. IV (1981) 11-14. 
[7]. Galeana Sánchez H. Rincón Mejía H. A sufficient condition 
for the existence of é-kernels in digraphs. 
75