D:\User\sbornik_38_pdf\35.DVI


Mathematical Problems of Computer Science 38, 82{83, 2012.

Remar ks on E volutionar y H amiltonian Gr aph T heor y

Zh .G. N iko g h o s ya n ¤

Institute for Informatics and Automation Problems
National Academy of Sciences

E-mail: zhora@ipia.sci.am

W e p r e s e n t a n a p p r o p r ia t e c o m p le m e n t t o t h e la r g e p a le t t e o f e vo lu t io n a r y t h e o r ie s ( s u c h
a s e vo lu t io n a r y p s yc h o lo g y, e c o n o m ic s , c o m p u t a t io n , a lg o r it h m , p r o g r a m m in g , g a m e t h e o r y,
t h o u g h t a n d s o o n ) b y a n e w d is c ip lin e c o n c e r n in g m a t h e m a t ic s .

Th e c o n c e p t o f NP -c o m p le t e n e s s wa s in t r o d u c e d in 1 9 7 1 b y S t e p h e n Co o k [1 ], wh o
c o n je c t u r e d t h a t NP -c o m p le t e p r o b le m s a r e n o t s o lva b le in p o lyn o m ia l t im e . To d a y, t h is
c o n je c t u r e s e e m s m u c h m o r e r e a s o n a b le m o t iva t e d b y t h e fa c t t h a t t h e d e ve lo p m e n t s a r is in g
a r o u n d va r io u s NP -c o m p le t e p r o b le m s h a ve u n d e r g o n e a n a t u r a l g r a d u a l g r o wt h a n d e vo lu -
t io n , g e n e r a t in g a g r e a t d ive r s it y. Th e s e d e ve lo p m e n t s p r o vid e a n e xc lu s ive va lu a b le d o m a in
b e yo n d b io lo g y wit h c o n t in u o u s ly g r o win g d ive r s it y a n d we ll d e s c r ib e d e n vir o n m e n t -o r ig in s -
g e n e s t r u c t u r e s r e la t io n s .

W e fo c u s o n o n e o f t h e m o s t h e a vily s t u d ie d a r e a s in g r a p h t h e o r y, t h a t jo in s t o g e t h e r
a n u m b e r o f N P -c o m p le t e c yc le p r o b le m s , c a lle d la r g e c yc le s t h e o r y - a s im p li¯ e d ve r s io n
o f we ll-kn o wn h a m ilt o n ia n g r a p h t h e o r y, t o s h o w t h a t t h e in d ivid u a ls ( c la im s , p r o p o s it io n s ,
le m m a s , c o n je c t u r e s , t h e o r e m s ) o n t h is s u b je c t e vo lve a n d a d a p t t o t h e ir e n vir o n m e n t g e n e r -
a t in g a g r e a t d ive r s it y b y a n it e r a t ive p r o c e s s fr o m s im p lic it y t o c o m p le xit y, fr o m p r im it ive
b e g in n in g s ( s u c h a s " e ve r y c o m p le t e g r a p h is h a m ilt o n ia n " ) t o b e s t p o s s ib le t h e o r e m s b y
c e r t a in h e r e d it a r y m e c h a n is m s .

L a r g e c yc le s t h e o r y p la ys t h e r o le o f a g e n e r a l e n vir o n m e n t a n d va r io u s s t a t e m e n t s ,
in c lu d in g c la im s , p r o p o s it io n s , le m m a s c o n je c t u r e s a n d t h e o r e m s , p la y t h e r o le o f in d ivid u a ls
in a p o p u la t io n .

Th is s im p li¯ e d a n d va lu a b le m o d e l h a s a n u m b e r o f a d va n t a g e s wit h r e s p e c t t o b io l-
o g y a n d c a n b e u s e fu l t o wa r d s b e t t e r u n d e r s t a n d in g t h e u n ive r s a l m e c h a n is m s t o e xp la in
e vo lu t io n in a wid e va r ie t y o f d o m a in s o u t s id e o f b io lo g y.

( a 1 ) L a r g e c yc le s t h e o r y, o r ig in a t e d a b o u t 6 0 ye a r s a g o , e vo lve s m u c h m o r e r a p id ly t h a n
livin g fo r m s o n E a r t h , o r ig in a t e d a b o u t 3 .7 b illio n ye a r s a g o .

( a 2 ) Th e o r ig in s o f t h e o r e m s in la r g e c yc le s t h e o r y c a n b e s t r o n g ly d e t e r m in e d b y e xa c t
b r a n c h in g s o f t h e t r e e o f d e ve lo p m e n t s .

( a 3 ) Ge n e t ic u n it s a n d h e r e d it a r y m e c h a n is m s in la r g e c yc le s t h e o r y a r e m u c h m o r e s im -
p le r t h a n g e n e s t r u c t u r e s o f livin g fo r m s .

W e d is t in g u is h t h e fo llo win g e vo lu t io n m e c h a n is m s in la r g e c yc le s t h e o r y:
( b 1 ) im p r o ve m e n t s ( ve r t ic a l e vo lu t io n ) ,
( b 2 ) m o d ī c a t io n s ( h o r iz o n t a l e vo lu t io n ) ,
( b 3 ) ve r t ic a l g e n e r a liz a t io n s ( ve r t ic a l e vo lu t io n le a p b a s e d o n in d u c t ive r e a s o n in g ) ,

8 2



Zh. Nikoghosyan 8 3

( b 4 ) h o r iz o n t a l g e n e r a liz a t io n s ( h o r iz o n t a l e vo lu t io n le a p b a s e d o n in d u c t ive r e a s o n in g ) ,
( b 5 ) in vo lvin g n e w g e n e t ic u n it s ( g e n o m e e xt e n s io n ) .

De¯nition 1. Im p r o ve m e n t is o n e o f t h e fo llo win g p r o c e d u r e s :
( c1 ) r e la xin g o n e o f t h e c o n d it io n s in t h e o r e m s a n d p r e s e r vin g t h e c o n c lu s io n ,
( c2 ) s t r e n g t h e n in g t h e c o n c lu s io n a n d p r e s e r vin g t h e c o n d it io n s .

De¯nition 2. Mo d i¯ c a t io n is o n e o f t h e fo llo win g p r o c e d u r e s :
( d 1 ) r e la xin g o f s o m e c o n d it io n s , a t t h e s a m e t im e s t r e n g t h e n in g s o m e o t h e r s , u n d e r t h e

s a m e c o n c lu s io n ,
( d 2 ) r e la xin g o f s o m e c o n d it io n s , a t t h e s a m e t im e r e la xin g t h e c o n c lu s io n ,
( d 3 ) s t r e n g t h e n in g o f s o m e c o n d it io n s , a t t h e s a m e t im e s t r e n g t h e n in g t h e c o n c lu s io n .

De¯nition 3. V e r t ic a l g e n e r a liz a t io n is a le a p in im p r o ve m e n t p r o c e s s b a s e d o n in d u c t ive
r e a s o n in g t o wa r d ¯ n d in g b e s t p o s s ib le r e s u lt s .
De¯nition 4. H o r iz o n t a l g e n e r a liz a t io n is a le a p in m o d i¯ c a t io n p r o c e s s b a s e d o n in d u c t ive
r e a s o n in g t o wa r d ¯ n d in g b e s t p o s s ib le r e s u lt s .

W e d e a l a s p e c ia l a t t e n t io n t o s o c a lle d " fu n d a m e n t a l t h e o r e m s " , b y o b s e r vin g t h a t a ll
t h e o r e m s in la r g e c yc le s t h e o r y h a ve d e s c e n d e d fr o m a n u m b e r o f c o m m o n a n c e s t o r s via g e n -
e r a liz a t io n s , c a lle d fu n d a m e n t a l t h e o r e m s . R e m e m b e r , t h a t t h e t e r m " fu n d a m e n t a l r e s u lt "
is u s e d in va r io u s ¯ e ld s o f s c ie n c e t o c h a r a c t e r iz e m a in ly t h e c e n t r a l a n d m o s t im p o r t a n t
r e s u lt s in t h e a r e a .

R e fe r e n c e s

[1 ] S .A . Co o k, Th e Co m p le xit y o f Th e o r e m -P r o vin g P r o c e d u r e s , P r o c e e d in g s , Th ir d A n -
n u a l A CM S ym p o s iu m o n t h e t h e o r y o f c o m p u t in g , A CM, N e w Y o r k ( 1 9 7 1 ) 1 5 1 -1 5 8 .

8 3