Microsoft Word - Math080902-f edited_checked-f3.doc 61-69 SQU Journal For Science, 14 (2009) © 2009 Sultan Qaboos University 61 Incidence Matrices of X-Labeled Graphs and an Application W.S. Jassim Department of Mathematics, College of Education Saadah, Saadah – Yemen, Email: Email: wadhahjassim@yahoo.co.uk. مع تطبيق X-المحمولة بعناصر المجموعة الوقوع للبيانات مصفوفات جاسم . وضاح س بعض التحسينات على تعريف مصفوفات الوقوع للبيانات الموجهة من أجل أن تكون أكثر ب قمنافي بحثنا هذا :خالصة . نكولص–ه التحسينات استطعنا وصف برنامج لخوارزمية بهذ . X –مة للبيانات المحمولة بعناصر المجموعة ءمال ABSTRACT: In this work, we have made some modifications to the definition of the incidence matrices of a directed graph, to make the incidence matrices more suitable for X – Labeled graphs. The new incidence matrices are called the incidence matrices of X – Labeled graphs, and we have used the new definition to give a computer program for Nickolas` Algorithm . KEYWORDS: Incidence matrix, Directed graph, X -labeled graph, Spanning tree, Cyclomatic number. 1. Introduction n Abdu (1999), Nickolas described an algorithm to change two core graphs of one type of branch points to core graphs with two or more types of branch points. Since incidence matrices of directed graphs do not deal with labeled graphs, from this point we worked to make the incidence matrices to be more suitable for X – Labeled graphs. This work is divided into three sections. In section 1, we give basic concepts about free groups and graphs. In section 2, we give the definition of the incidence matrices of X – Labeled graphs, and some definitions and results on incidence matrices of X – Labeled graphs. In section 3, we apply the concept of incidence matrices of X – Labeled graphs to give a computer program for Nickolas` Algorithm. 1.1 Basic concepts: Let F be a group and X be a subset of F . Then we say that F is a free group on X , if for any group G and any mapping : ,f X G→ there is a unique homomorphism : F Gψ → , such that )()( xfx =ψ for all x X∈ . Two free groups F and K are called isomorphic if and only if F and K have the same rank. I W.S. JASSIM 62 If a graph Γ is a collection of two sets, ( ) ( )( )is not empty setV VΓ Γ and ( )E Γ , called the set of vertices and edges respectively of the graph Γ ,together with two functions : ( ) ( ), : ( ) ( )i E V t E VΓ → Γ Γ → Γ , we say that the edge e joins the vertex ( )i e to the vertex ( )t e . The vertex ( )i e is called the initial vertex of e and ( )t e is called the terminal vertex of e . Moreover for each e in ( )E Γ there is an element ee ≠ in ( )E Γ , which is called the inverse of e , such that )()(),()( eietetei == and ee = . A subgraph Ω of a graph Γ is a graph with ( ) ( )V VΩ ⊆ Γ and ( ) ( )E EΩ ⊆ Γ such that, if )(Ω∈ Ee , then )(eiΩ , )(etΩ and e have the same meaning in Γ as they do in Ω . If Ω ≠ Γ , then we call Ω a proper subgraph. A component of a connected graph Γ is a maximal connected subgraph of Γ . The number of edges incident with the vertex v is called the degree of the vertex v and denoted by ( )d v . The vertex v is called a branch point if 3)( ≥vd . Now let F be a group and X be a subset of F . Then the graph ( , )F XΓ is called the Cayley graph of the group F with respect to X , if ( , )F XΓ has vertex set F and set of edges ( ){ }, : , ,F X w x w F x X× = ∈ ∈ such that the initial vertex of the edge ( ),w x is ( ), ,i w x w= the terminal vertex of the edge ( ),w x is ( ),t w x wx= and x is the labeled of the edge ( ),w x . The inverse edge of ( ),w x is ),( 1−xwx . The quotient graph or Cayley coset graph ( , ) /F X HΓ for a subgroup H of F has set of vertices { : , }Hw w F H F∈ ≤ and set of edges {( , ) : , }Hw x w F x X∈ ∈ such that an edge ( , ) ( , ) /Hw x F X H∈Γ takes the vertex Hw to Hwx . It is also denoted by ( )HΓ . The Core of a coset graph )(HΓ is the smallest subgraph containing all cycles. It is denoted by ( )H∗Γ . For example, if F is a free group on generators a and b , then ( )F∗Γ : a b The number of cycles in ∗Γ ( )H is called the cyclomatic number and the cyclomatic number of ∗Γ ( )H is the minimal number of edges that we can delete to make a tree. The rank of the finitely generated subgroup H of a free group on X is the cyclomatic number of ∗Γ ( )H and denoted by ( )r H . Definition 1.1 A consistent graph is a directed X – Labeled graph Γ on { , }X a b= , such that no reduced path in Γ with labeled 1−aa , aa 1− , 1−bb or bb 1− ever occurs in consistent graphs. Therefore ( , )F XΓ , ( )HΓ and ( )H∗Γ are consistent graphs. Now if ( )H∗Γ has vertices of degree 2, 3, 4, then as in [5] we can reduce the degree of the vertices into vertices of degree 2 and 3 only, by isomorphic embedding of F into a free group K on { },u v , via the map : F Kθ → with 21 )(,)( vbuva == − θθ and taking the graph into a new set of labels },{ vu . INCIDENCE MATRICES OF X-LABELED GRAPHS 63 Proposition 1.2: If ( )H∗Γ has vertices of degree 2, 3 only, then # ( ( )) ( ) 1 2 Br H r H ∗Γ = + , where # ( ( ))Br H∗Γ is the number of branch points in ( )H∗Γ . Proof: ( ) 2 # ( ( ))d v E H∗= Γ∑ . ( ( ) 2) 2(# ( ( )) # ( ( )))d v E H V H∗ ∗− = Γ − Γ∑ , and the number of edges in the spanning tree of ( )H∗Γ = # ( ( )) 1V H∗Γ − . Therefore we have the following : ( ( ) 2)d v −∑ = (the number of edges in )(H∗Γ - the number of edges in the spanning tree of ( )H∗Γ - 1). Since ( )r H = the number of edges in )(H∗Γ - the number of edges in the spanning tree of ( )H∗Γ , so ∑ − )2)(( vd = )1)((2 −Hr )1( , and also 2)( −vd ) = int 0 1 pobranchaisv otherwise if ⎩ ⎨ ⎧ . Thus ∑ =− )2)(( vd ))((# HBr ∗Γ . Therefore 12 ))((# )( + Γ = ∗ HBr Hr . Definition 1.3: For any two branch points u and v in )(H∗Γ , we say that u and v are neighboring branch points if they are connected by a (reduced) path which does not contain any branch point. Definition 1.4: The product of core graphs )(* HΓ and )(* KΓ is the graph )(~)( ** KH Γ×Γ with set of vertices ))}(()),((:),{())(())(( **** KVvHVuvuKVHV Γ∈Γ∈=Γ×Γ and edges })),((),()),((),(:)),,{(( ** XyKEyvHEyuyvu ∈Γ∈Γ∈ . If ∗Γ (H), )(K∗Γ and )(* KH ∩Γ are the core graphs of the finitely generated subgroups ,H k and KH ∩ respectively of a free group F on },{ baX = and )(~)( ** KH Γ×Γ is the product of core graphs )(* HΓ and )(* KΓ defined above, then )(* KH ∩Γ may identified with a core of a connected component of )(~)( ** KH Γ×Γ and )(* HΓ has only four types of branch points as follows: b – sources b – sinks a – sources a - sinks 2. Incidence matrices of X –Labeled graphs In this section we will give the definition of incidence matrices of X – Labeled graphs and some definitions and results related to it. As we know there are two types of matrices to describe graphs, which are called adjacency (or vertex incidence) matrices and incidence matrices. Recall that the incidence matrices of W.S. JASSIM 64 directed graphs Γ are without loops and with n vertices and m edges ( i.e. it is mn × matrices ][ ijx , where mjni ≤≤≤≤ 1,1 ) such that : ⎪ ⎩ ⎪ ⎨ ⎧ =− = = )(1 0 )(1 ji ji ji ij evif ewithincedencenotisvif eivif x τ All edges e in X – Labeled graphs ( )),(~)(),,(),(),( …KHXFHH ∗∗∗ Γ×ΓΓΓΓ are labeled 1−∪∈ XXx and the incidence matrices of directed graphs do not deal with the labels of edges, so we will put more conditions on the incidence matrices of directed graphs as below. Definition 2.1: Let Γ be any X – Labeled graph without loops ( where },{ baX = ) , then the incidence matrix of the X – Labeled graph Γ is an mn × incidence matrix ][ ijx , where mjni ≤≤≤≤ 1,1 ) with ijx entries such that Xxlabelese ewithincident Xxlablese ande notisv andei v if v if if x x x j j j j i j i i ij ∈ ∈ = = ⎪ ⎩ ⎪ ⎨ ⎧ = − )( )( 0 1 τ N.B. Incidence matrices of X – Labeled graphs Γ will be denoted by )(ΓXM . Now if },{ baX = and the X –Labeled graph Γ has loops with labeling a or b , then choose a mid point on all edges labeled a or b to make all of them two edges labeled aa or bb respectively. Therefore in the rest of this work we will assume that all X – Labeled graphs Γ are without loops. Definition 2.2: Let )(ΓXM be an incidence matrices of X – Labeled graphs Γ . If )(ΓXM does not contain any row ir with non zero entries ijx and ikx in 1−∪ XX such that ikij xx = , then )(ΓXM is called a consistent incidence matrix of X – Labeled graphs Γ . Now let )(ΓXM be an mn × incidence matrix ][ ijx of X – Labeled graphs Γ and let ir and jc be a row and a column in )(ΓXM respectively. If ijx is a non – zero entry in the row ir , then ir is called an incidence row with the column jc at the non – zero entry ijx 1−∪∈ XX and if Xxij ∈ , then the row ir is called the starting row ( denoted by ))( jcs of the column jc and the row ir is called the ending row ( denoted by )( jce ) of the column jc if 1−∈ Xxij . If the rows ir and kr are incident with column jc at the non – zero entries ijx and kjx respectively, then we say that the rows ir and kr are adjacent. If jc and hc are two distinct columns in )(ΓXM such that the row ir is incident with the columns jc and hc at the non – zero entries ijx and ihx respectively (where 1, −∪∈ XXxx hij ), then we say that jc and hc are adjacent columns. For each column c there is an inverse column denoted by c such that )()(),()( cscececs == and cc = . The degree of a row ir of )(ΓXM is the number of the columns incident on ir and is denoted by )deg( ir . If INCIDENCE MATRICES OF X-LABELED GRAPHS 65 the row ir is incident with at least three distinct columns jc , hc and kc at the non – zero entries, then the row ir is called a branch row. If the row ir is incident with only one column jc at the non zero entry ijx 1−∪∈ XX and all other entries of ir are zero, then the row ir is called isolated row. A scale in )(ΓXM is a finite sequence of form kkk rcrcrcrS k ,,,,,,, 121 112211 − ∈ −− ∈∈= … , where ,1≥k ,∓∈= jj rcs j =∈ )( and kjcsrce jjj j ≤≤== ++ ∈ 1),()( 11 . The starting row of a scale kkk rcrcrcrS k ,,,,,,, 121 112211 − ∈ −− ∈∈= … is the starting row 1r of the column 1c and the ending row of the scale S is the ending row kr of the column 1−kc and we say that S is a scale from 1r to kr and S is a scale of length k for 21 −≤≤ kj . If )()( SeSs = , then the scale is called closed scale. If the scale S is reduced and closed, then S is called a circuit or a cycle. If )(ΓXM has no cycle, then )(ΓXM is called a forest incidence matrix of X – Labeled graph Γ . Two rows ir and kr in )(ΓXM are called connected if there is a scale S in )(ΓXM containing ir and kr . Moreover, )(ΓXM is called connected if any two rows ir and kr in )(ΓXM are connected by a scale S . If )(ΓXM is connected and forest, then )(ΓXM is called a tree incidence matrix of X – Labeled graph Γ . Let Ω be a subgraph of Γ , then )(ΩXM is called a subincidence matrix of )(ΓXM , if the set of rows and columns of )(ΩXM are subsets of )(ΓXM and if c is a column in )(∆XM . Then )(),( cecs and c have the same meaning in )(ΓXM as they do in )(ΩXM . If )()( Γ≠Ω XX MM , then )(ΩXM is called a proper subincidence matrix of )(ΓXM . A component of )(ΓXM is a maximal connected subincidence matrix of )(ΓXM . If )(ΩXM is a subincidence matrix of )(ΓXM , and every two rows ir and kr in )(ΓXM are joined by at least one scale S in )(ΩXM , then )(ΩXM is called a spanning incidence matrix of )(ΓXM , and )(ΩXM is called a spanning tree of )(ΓXM if )(ΩXM is a spanning and tree incidence matrix. The inverse of )(ΓXM is an incidence matrix of 1−X - labeled graph Γ . Now by direct calculations and the definition above, we can prove the following results. Lemma 2.3: If )(ΓXM is a tree incidence matrix of X – Labeled graph Γ with n rows, then )(ΓXM has n – 1 columns. Lemma 2.4: If )(ΓXM is an incidence matrix of X – Labeled graph Γ with n rows and m columns, then mr n i i 2)deg( 1 =∑ = , where ni ≤≤1 . Corollary 2.5: If )(ΓXM is a finite incidence matrix of X – Labeled graph Γ , then )(ΓXM has even number of rows of odd degree. Lemma 2.6: The cyclomatic number ))(( ΓXMC of a finite incidence matrix of X – Labeled graph Γ is equal to r k+#c-# , where c# , r# and k are the number of columns, the number of rows and the number of components of )(ΓXM respectively. Corollary 2.7: If )(ΓXM is a connected incidence matrix of X – Labeled graph Γ with r rows and c columns, then 1##))(( +−=Γ rcMC X . W.S. JASSIM 66 3. An application of incidence matrices of X – Labeled graphs In this section we will represent the core graphs )(H∗Γ of finitely generated subgroups H of a free group F generated by },{ baX = in the form of incidence matrices of core graphs ))(( HM X ∗Γ and then we will describe Nickolas` Algorithm (Nickolas, 1985) in the form of incidence matrices of X – Labeled graphs, but before that we give some results and definitions that will be used in the rest of the paper. Since the core graphs )(H∗Γ of finitely generated subgroups H of a free group F generated by },{ baX = are X – Labeled graphs, they may be represented by incidence matrices of X – Labeled graphs Γ which are denoted by ))(( HM X ∗Γ . Lemma 3.1: Let ))(( HM X ∗Γ be an incidence matrix of a core graph )(H∗Γ of a finitely generated subgroup H of a free group F generated by },{ baX = with n rows of degree two and three only and m columns , then 1 2 )))(((# )))((( + Γ =Γ ∗ ∗ HMBrHMC XX , where )))(((# HMBr X ∗Γ is the number of branch rows of ))(( HM X ∗Γ . Proof: Since ∑ = = n i i mr 1 2)deg( , so ∑ −=− )(2)2)(deg( nmri . But ∑ ∗Γ=− )))(((#)2)(deg( HMBrr Xi and nmHMC X −=−Γ∗ 1)))((( . Therefore 1 2 )))(((# )))((( + Γ =Γ ∗ ∗ HMBrHMC XX . Corollary 3.2: Let ))(( HM X ∗Γ be an incidence matrix of a core graph )(H∗Γ of a finitely generated subgroup H of a free group F generated by },{ baX = with n rows of degree two and three only, then ( )r H = 1 2 )))(((# + Γ∗ HMBr X . Definition 3.3: Let ))(( HM X ∗Γ and ))(( KM X ∗Γ be the incidence matrices of core graphs )(H∗Γ and )(K∗Γ respectively, of a finitely generated subgroup H of a free group F generated by },{ baX = . The product of ))(( HM X ∗Γ and ))(( KM X ∗Γ is the incidence matrix ))((~))(( KMHM XX ∗∗ Γ×Γ of X – Labeled graph of the product of )(H∗Γ and )(K∗Γ with set of rows vuv :),{( and u are rows in ))(( HM X ∗Γ and ))(( KM X ∗Γ respectively } and set of columns :),{( ji cc ic and jc are columns in ))(( HM X ∗Γ and ))(( KM X ∗Γ ,respectively} , and they have the same non – zero entries 1−∪∈ XXx . Lemma 3.4: Let ))(( HM X ∗Γ and ))(( KM X ∗Γ be the incidence matrices of core graphs )(H∗Γ and )(K∗Γ respectively, of a finitely generated subgroup H of a free group F generated by },{ baX = . Then INCIDENCE MATRICES OF X-LABELED GRAPHS 67 the incidence matrices of the product )(~)( KH ∗∗ Γ×Γ (denoted by ))(~)(( KHM X ∗∗ Γ×Γ ) is the same as the product ))((~))(( KMHM XX ∗∗ Γ×Γ . Proof: By the definition of the product of core graphs and definition 3.3 the result follows. Lemma 3.5: Let ))(( HM X ∗Γ be defined as above and have 2n branch rows. If all branch rows of ))(( HM X ∗Γ are of one type b – sources, say , then there are at least n rows with only two non – zero entries axbx ikij == − ,1 and all other entries are zero. Proof: Since all possibilities of scales joining two neighboring branch rows are 654321 ,,,,, SSSSSS such that 122111 + = kkk ijijiji rcrcrcrS ; where 1i r is the starting row of the column 1j c at the non – zero entry bx ji =11 and 1+kir is the ending row of the columns kjc at the non – zero entry 1 11 −= ++ ax kk ji , 122112 + = mmm ijijiji rcrcrcrS ; where 1i r is the starting row of the column 1j c at the non – zero entry bx ji =11 and 1+mir is the ending row of the column mjc at the non–zero entry ax mm ji =+1 , 122113 + = ttt ijijiji rcrcrcrS ; where 1i r is the starting row of the column 1j c at the non – zero entry bx ji =11 and 1+ti r is the ending row of the columns kj c at the non–zero entry bx tt ji = +1 ; 12114 + = ggg ijiiji rcrrcrS ; where 1i r is the starting row of the column 1j c at the non – zero entry ax ji =11 and 1+gir is the ending row of the columns gj c at the non–zero entry 1 1 −= + ax gg ji , 12115 + = hhh ijiiji rcrrcrS ; where 1i r is the starting row of the column 1j c at the non–zero entry ax ji =11 and 1+tir is the ending row of the columns kjc at the non- zero entry ax tt ji = +1 , and 12116 + = ddd ijiiji rcrrcrS ; where 1i r is the starting row of the column 1j c at the non – zero entry 1 11 −= ax ji and 1+tir is the ending row of the columns kjc at the non–zero entry 1 1 −= + ax tt ji . Since ))(( HM X ∗Γ is a consistent incidence matrix of X – Labeled graph Γ , so the scales 54321 ,,,, SSSSS and 6S must contain rows fir with a non – zero entries 1−= bx vf ji , and ax uf ji = or 1−= ax uf ji only and all other entries are zero. Also ))(( HM X ∗Γ has 2n branch rows and all of them are of one type b – source row, so suppose that ))(( HM X ∗Γ has 1s scales of type 1S , 2s scales of type 2S , 3s scales of type 3S , 4s scales of type 4S , 5s scales of type 5S and 6s scales of type 6S . Therefore we have nssssss 3654321 =+++++ )1( . Since each branch row ir of ))(( HM X ∗Γ has exactly one non – zero entry axij = , and the scale of type 2S ending with the row mir at the non - zero entries ax mm ji = , scales of types 4S starting with the row 1ir at the non – zero entry ax ji =11 and scales of types 5S starting and ending with the rows 1i r and hi r at the non – zero entries ax ji =11 and ax hji =1 respectively. Therefore ))(( HM X ∗Γ has 2 4 5 2 2)2 (s s s n+ + = . Hence from (2) we have 2 4 5 32 ( )s s s n+ + < . From (3) and (1) we have nsss >++ 631 , since each of the scales 31 , SS and 6S has at least one row with non – zero entries 1−= bxij and axiz = , and all other entries are zero. W.S. JASSIM 68 Nickolas [5] gave an algorithm to change core graphs )(H∗Γ and )(K∗Γ of two finitely generated subgroups H and K of a free group F generated by },{ baX = , which have only one type of branch points , b – sources,say, into new core graphs with two or more types of branch points. Therefore we will represent Nickolas` algorithm in the form of incidence matrices of X –Labeled graphs in order to give a computer program to change the type of branch points of core graphs with only one type of branch points into two or more types of branch points. Now let ))(( HM X ∗Γ and ))(( KM X ∗Γ be incidence matrices of X –Labeled core graphs )(H∗Γ and )(K∗Γ respectively, such that ))(( HM X ∗Γ and ))(( KM X ∗Γ have branch rows of one type, b – sources, say, then we will use the representation of Nickolas` algorithm to change ))(( HM X ∗Γ and ))(( KM X ∗Γ into two incidence matrices of X –Labeled core graphs ))(( HM kX ∗Γ and ))(( KM kX ∗Γ with two types or more of branch rows, after k – times . The steps are given below: 0) Delete all zero columns and zero rows if they appear; )0∗ If the branch rows are not of one type, then stop. Otherwise, change the non – zero entries to make all branch rows of type b – sources by reversing the labeling of the columns and then proceed to step 1; 1 ) If ir is the ending and the starting row of the columns jc and kc at 1−= bxij and bxik = respectively and all other entries of ir are zero, and tr is the ending row of the column kc , then add tr and ir to a new row tr ′ , and if there is no such a row ir , then proceed to step II; II ) If gi rr , and tr are rows such that ir is the ending and the starting row of the columns jc and kc at 1−= bxij and axik = respectively, and gr is the ending row of the columns kc and hc at 1−= ax gk and 1−= bx gh respectively and all other entries of ir and gr are zero, and also tr is the starting row of the column hc at bxth = , then add it rr , and gr to have a new row tr ′ , and if there is no such rows, then proceed to step III; III ) If ir is the ending and the starting row of the columns jc and kc at 1−= bxij and axik = respectively and all other entries of ir are zero, and tr is the ending row of the column kc at 1−= axtk , then add tr and ir to have a new row tr ′ , and if there is no such a row then return to step 0 above. Note: In the program of the above Algorithm we will consider 1−a and 1−b as a− and b− respectively and then will represent a and b by 1 and 2 respectively. The representation of Nickolas` Algorithm in the form of incidence matrices of X –Labeled graphs is well defined, which means the representation of Nickolas` Algorithm satisfying the following conditions: 1) At each step of the representation of Nickolas` Algorithm, we get consistent incidence matrices of X – Labeled graphs because step I is applied to non – branch rows ir and tr to give a non – branch row tr ′ with non – zero entries 1−′ = bx jt and ax ht =′ or 1− ′ = ax ht , so step I always gives consistent incidence matrices of X –Labeled graphs . Also step II is applied on non – branch rows of ))(( HM X ∗Γ which do not contain non – branch rows ir with non – zero entries 1−= bxij and bxih = so step II always gives, either non – branch INCIDENCE MATRICES OF X-LABELED GRAPHS 69 rows tr ′ with non – zero entries 1− ′ = ax jt and 1− ′ = bx ht or a branch row with non – zero entries 1− ′ = bx ht , ax jt =′ and 1− ′ = ax lt . While step III is applied on non – branch row ir with non – zero entries 1−= bxij and axik = , and the row tr which is either a non – branch row with non – zero entries 1−= axtk and bxth = or axth = , or tr is a branch row of type b – sources , so when we apply step III either we have a non - branch row tr ′ with non zero entries 1− ′ = bx jt and bx ht =′ or 1− ′ = bx jt and ax ht =′ , or tr ′ is a branch row with non – zero entries 1−′ = bx jt , bx ht =′ and ax lt =′ . Therefore step III always gives consistent incidence matrices of X –Labeled graphs. 2) The representation of Nickolas` Algorithm preserves the number of branch rows in ))(( HM X ∗Γ , because it is applied on non – branch rows, so apply steps I, II and III reduce the non – branch rows only and then the number of branch rows in ))(( HM X ∗Γ will be still the same as before and the type of branch rows may change only. 3)The representation of Nickolas` Algorithm preserves the number of branch rows in ))((~))(( KMHM XX ∗∗ Γ×Γ , because each row in ))((~))(( KMHM XX ∗∗ Γ×Γ comes from the product of two rows ir and tr in ))(( HM X ∗Γ and ))(( KM X ∗Γ respectively and the removed rows are non – branch rows which contain a non zero entries 1−= bxij , and ))(( HM X ∗Γ and ))(( KM X ∗Γ have no branch row with non –zero entry 1−= bxij . Therefore whatever happens to ))(( HM X ∗Γ and ))(( KM X ∗Γ , then will happen to the maximum connected submatrix of ))((~))(( KMHM XX ∗∗ Γ×Γ . 4) Each time we return to step ∗0 of the representation of Nickolas` Algorithm, we must apply one of the steps 1, 2 or 3 , because if step 1 and 2 do not apply , the step 3 must apply by Lemma 3.5. 5) In each time we return to step ∗0 we have fewer rows ; this comes from reducing at least two rows to a single row. 6) The algorithm must stop after a finite time, because each time we reduce the total number of rows by at least one row, and then we have at least two different types of branch rows of ))(( HM X ∗Γ and ))(( KM X ∗Γ . 4. References ABDU, K.A. 1999. Representing Core graphs and Nickolas`s Algorithm. M.Sc .Thesis, Baghdad University. LYNDON, R.C. and SCHUPP, P.E. 1977. Combinatorial group theory. Ergebniss Vol. 89, Berlin – Heidelberg – New York, Springer. MAGNUSS, W., KARRASS, A. and SOLITER, D. Combinatorial group theory. New York. John wiley and sons Inc 1966. NICKOLAS, P. 1985. Intersecton of finitely generated free groups. Bull. Austral. Math. Soc. 31: 339 – 349. SARVATIUS, B. 1983. A short proof of a theorem of Burns. Math. 71: 551 – 565. Received 2 September 2008 Accepted 29 April 2009