4.3.4.9. five parameters/two final graphs

πŒπ€π—_𝐍𝐂𝐂 1 , πŒπ€π—_𝐍𝐂𝐂 2 , 𝐌𝐈𝐍_𝐍𝐂𝐂 1 , 𝐌𝐈𝐍_𝐍𝐂𝐂 2 , 𝐍𝐂𝐂 1

Proposition 151

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: 𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β·max(0,𝐍𝐂𝐂 1 -1)+πŒπ€π—_𝐍𝐂𝐂 1 + 𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β·max(0,𝐍𝐂𝐂 1 -2)+πŒπ€π—_𝐍𝐂𝐂 2 ≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™»

Proof 149 The left -hand side ofΒ 151 corresponds to the minimum number of vertices of the two final graphs provided that we build the smallest possible connected components.

Proposition 152

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: 𝐍𝐂𝐂 1 ≀(πŒπ€π—_𝐍𝐂𝐂 1 Β―>0)+Ξ± Ξ²+Ξ± mod Ξ²β‰₯max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 1 Μ²) β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -max(1,πŒπ€π—_𝐍𝐂𝐂 1 Μ²)-max(1,πŒπ€π—_𝐍𝐂𝐂 2 Μ²)),β€’ Ξ²=max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 1 Μ²)+max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 2 Μ²).

Proof 150 The maximum number of connected components is achieved by building non -empty groups as small as possible, except for two groups of respective size max(1,πŒπ€π—_𝐍𝐂𝐂 1 Μ²) and max(1,πŒπ€π—_𝐍𝐂𝐂 2 Μ²), which have to be built.

Proposition 153

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: πŒπ€π—_𝐍𝐂𝐂 1 Β·max(0,𝐍𝐂𝐂 1 -1)+𝐌𝐈𝐍_𝐍𝐂𝐂 1 + πŒπ€π—_𝐍𝐂𝐂 2 ·𝐍𝐂𝐂 1 +𝐌𝐈𝐍_𝐍𝐂𝐂 2 β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™»

Proof 151 The left -hand side ofΒ 153 corresponds to the maximum number of vertices of the two final graphs provided that we build the largest possible connected components.

Proposition 154

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: 𝐍𝐂𝐂 1 β‰₯(πŒπ€π—_𝐍𝐂𝐂 2 Β―<𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» )+Ξ± Ξ²+Ξ± mod Ξ²>πŒπ€π—_𝐍𝐂𝐂 2 Β― β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β―-𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β―,β€’ Ξ²=max(1,πŒπ€π—_𝐍𝐂𝐂 1 Β―)+max(1,πŒπ€π—_𝐍𝐂𝐂 2 Β―).

Proof 152 The minimum number of connected components is achieved by taking the groups as large as possible except for two groups of respective size 𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β― and 𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β―, which have to be built.

Proposition 155

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: πŒπ€π—_𝐍𝐂𝐂 2 ≀max(𝐌𝐈𝐍_𝐍𝐂𝐂 2 ,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -Ξ±),πš πš’πšπš‘: β€’Ξ±=𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β·max(0,𝐍𝐂𝐂 1 -1)+πŒπ€π—_𝐍𝐂𝐂 1 + 𝐌𝐈𝐍_𝐍𝐂𝐂 2 +𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β·max(0,𝐍𝐂𝐂 1 -3)

Proof 153 If 𝐍𝐂𝐂 1 ≀1 we have that πŒπ€π—_𝐍𝐂𝐂 2 β‰€πŒπˆπ_𝐍𝐂𝐂 2 . Otherwise, when 𝐍𝐂𝐂 1 >1, we have that 𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β·max(0,𝐍𝐂𝐂 1 -1)+πŒπ€π—_𝐍𝐂𝐂 1 +𝐌𝐈𝐍_𝐍𝐂𝐂 2 +πŒπ€π—_𝐍𝐂𝐂 2 +𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β·max(0,𝐍𝐂𝐂 1 -3)≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» . 𝐍𝐂𝐂 1 -3 comes from the fact that we build the minimum number of connected components in the second final graph (i.e., 𝐍𝐂𝐂 1 -1 connected components) and that we have already built two connected components of respective size 𝐌𝐈𝐍_𝐍𝐂𝐂 2 and πŒπ€π—_𝐍𝐂𝐂 2 . By isolating πŒπ€π—_𝐍𝐂𝐂 2 in the previous expression and by grouping the two inequalities the result follows.

Proposition 156

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§πŒπˆπ_𝐍𝐂𝐂 1 >1∧𝐌𝐈𝐍_𝐍𝐂𝐂 2 >1: 𝐍𝐂𝐂 1 ≀(πŒπ€π—_𝐍𝐂𝐂 1 >0)+Ξ± Ξ²+((Ξ± mod Ξ²)+1β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂 1 ), πš πš’πšπš‘: β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 1 -πŒπ€π—_𝐍𝐂𝐂 2 +1),β€’ Ξ²=𝐌𝐈𝐍_𝐍𝐂𝐂 1 +𝐌𝐈𝐍_𝐍𝐂𝐂 2 -2.

Figure 4.3.9. Illustration of PropositionΒ 156. Configuration achieving the maximum number of connected components for G 1 according to the size of the smallest and largest connected components of G 1 and G 2 and to an initial number of vertices (πŒπ€π—_𝐍𝐂𝐂 1 =4,πŒπ€π—_𝐍𝐂𝐂 2 =5,𝐌𝐈𝐍_𝐍𝐂𝐂 1 =3,𝐌𝐈𝐍_𝐍𝐂𝐂 2 =4,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» =14,Ξ±=max(0,14-4-5+1)=6,Ξ²=max(2,3+4-2)=5,𝐍𝐂𝐂 1 =(4>0)+6 5+(((6 mod 5)+1)β‰₯3)=2)
ctrs/ncc1_leq_maxncc_minncc

Proof 154 The maximum number of connected components of G 1 is achieved by:

  • Building a first connected component of G 1 involving πŒπ€π—_𝐍𝐂𝐂 1 vertices,

  • Building a first connected component of G 2 involving πŒπ€π—_𝐍𝐂𝐂 2 vertices,

  • Building alternatively a connected component of G 1 and a connected component of G 2 involving respectively 𝐌𝐈𝐍_𝐍𝐂𝐂 1 and 𝐌𝐈𝐍_𝐍𝐂𝐂 2 vertices,

  • Finally, if this is possible, building a connected component of G 1 involving 𝐌𝐈𝐍_𝐍𝐂𝐂 1 vertices.

Proposition 157

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§πŒπˆπ_𝐍𝐂𝐂 1 >1∧𝐌𝐈𝐍_𝐍𝐂𝐂 2 >1: 𝐍𝐂𝐂 1 β‰₯(𝐌𝐈𝐍_𝐍𝐂𝐂 1 >0)+Ξ± Ξ²+((Ξ± mod Ξ²)+1>πŒπ€π—_𝐍𝐂𝐂 2 ), πš πš’πšπš‘: β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -𝐌𝐈𝐍_𝐍𝐂𝐂 1 -𝐌𝐈𝐍_𝐍𝐂𝐂 2 +1),β€’ Ξ²=πŒπ€π—_𝐍𝐂𝐂 1 +πŒπ€π—_𝐍𝐂𝐂 2 -2.

Figure 4.3.10. Illustration of PropositionΒ 157. Configuration achieving the minimum number of connected components for G 1 according to the size of the smallest and largest connected components of G 1 and G 2 and to an initial number of vertices (πŒπ€π—_𝐍𝐂𝐂 1 =4,πŒπ€π—_𝐍𝐂𝐂 2 =5,𝐌𝐈𝐍_𝐍𝐂𝐂 1 =3,𝐌𝐈𝐍_𝐍𝐂𝐂 2 =4,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» =18,Ξ±=max(0,18-3-4+1)=12,Ξ²=max(2,4+5-2)=7,𝐍𝐂𝐂 1 =(3>0)+12 7+(((12 mod 7)+1)>5)=3)
ctrs/ncc1_geq_maxncc_minncc

Proof 155 The minimum number of connected components of G 1 is achieved by:

  • Building a first connected component of G 2 involving 𝐌𝐈𝐍_𝐍𝐂𝐂 2 vertices,

  • Building a first connected component of G 1 involving 𝐌𝐈𝐍_𝐍𝐂𝐂 1 vertices,

  • Building alternatively a connected component of G 2 and a connected component of G 1 involving respectively πŒπ€π—_𝐍𝐂𝐂 2 and πŒπ€π—_𝐍𝐂𝐂 1 vertices,

  • Finally, if this is possible, building a connected component of G 2 involving πŒπ€π—_𝐍𝐂𝐂 2 vertices and a connected component of G 1 with the remaining vertices. Note that these remaining vertices cannot be incorporated in the connected components previously built.

πŒπ€π—_𝐍𝐂𝐂 1 , πŒπ€π—_𝐍𝐂𝐂 2 , 𝐌𝐈𝐍_𝐍𝐂𝐂 1 , 𝐌𝐈𝐍_𝐍𝐂𝐂 2 , 𝐍𝐂𝐂 2

Proposition 158

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: 𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β·max(0,𝐍𝐂𝐂 2 -1)+πŒπ€π—_𝐍𝐂𝐂 2 + 𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β·max(0,𝐍𝐂𝐂 2 -2)+πŒπ€π—_𝐍𝐂𝐂 1 ≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™»

Proof 156 Similar to PropositionΒ 151.

Proposition 159

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: 𝐍𝐂𝐂 2 ≀(πŒπ€π—_𝐍𝐂𝐂 2 Β―>0)+Ξ± Ξ²+Ξ± mod Ξ²β‰₯max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 2 Μ²) β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -max(1,πŒπ€π—_𝐍𝐂𝐂 2 Μ²)-max(1,πŒπ€π—_𝐍𝐂𝐂 1 Μ²)),β€’ Ξ²=max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 2 Μ²)+max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 1 Μ²).

Proof 157 Similar to PropositionΒ 152.

Proposition 160

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: πŒπ€π—_𝐍𝐂𝐂 2 Β·max(0,𝐍𝐂𝐂 2 -1)+𝐌𝐈𝐍_𝐍𝐂𝐂 2 + πŒπ€π—_𝐍𝐂𝐂 1 ·𝐍𝐂𝐂 2 +𝐌𝐈𝐍_𝐍𝐂𝐂 1 β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™»

Proof 158 Similar to PropositionΒ 153.

Proposition 161

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: 𝐍𝐂𝐂 2 β‰₯(πŒπ€π—_𝐍𝐂𝐂 1 Β―<𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» )+Ξ± Ξ²+Ξ± mod Ξ²>πŒπ€π—_𝐍𝐂𝐂 1 Β― β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β―-𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β―,β€’ Ξ²=max(1,πŒπ€π—_𝐍𝐂𝐂 2 Β―)+max(1,πŒπ€π—_𝐍𝐂𝐂 1 Β―).

Proof 159 Similar to PropositionΒ 154.

Proposition 162

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: πŒπ€π—_𝐍𝐂𝐂 1 ≀max(𝐌𝐈𝐍_𝐍𝐂𝐂 1 ,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -Ξ±),πš πš’πšπš‘: β€’Ξ±=𝐌𝐈𝐍_𝐍𝐂𝐂 2 Β·max(0,𝐍𝐂𝐂 2 -1)+πŒπ€π—_𝐍𝐂𝐂 2 + 𝐌𝐈𝐍_𝐍𝐂𝐂 1 +𝐌𝐈𝐍_𝐍𝐂𝐂 1 Β·max(0,𝐍𝐂𝐂 2 -3)

Proof 160 Similar to PropositionΒ 155.

Proposition 163

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§πŒπˆπ_𝐍𝐂𝐂 1 >1∧𝐌𝐈𝐍_𝐍𝐂𝐂 2 >1: 𝐍𝐂𝐂 2 ≀(πŒπ€π—_𝐍𝐂𝐂 2 >0)+Ξ± Ξ²+((Ξ± mod Ξ²)+1β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂 2 ), πš πš’πšπš‘: β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 1 -πŒπ€π—_𝐍𝐂𝐂 2 +1),β€’ Ξ²=𝐌𝐈𝐍_𝐍𝐂𝐂 1 +𝐌𝐈𝐍_𝐍𝐂𝐂 2 -2.

Proof 161 Similar to PropositionΒ 156.

Proposition 164

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§πŒπˆπ_𝐍𝐂𝐂 1 >1∧𝐌𝐈𝐍_𝐍𝐂𝐂 2 >1: 𝐍𝐂𝐂 2 β‰₯(𝐌𝐈𝐍_𝐍𝐂𝐂 2 >0)+Ξ± Ξ²+((Ξ± mod Ξ²)+1>πŒπ€π—_𝐍𝐂𝐂 1 , πš πš’πšπš‘: β€’ Ξ±=max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -𝐌𝐈𝐍_𝐍𝐂𝐂 1 -𝐌𝐈𝐍_𝐍𝐂𝐂 2 +1),β€’ Ξ²=πŒπ€π—_𝐍𝐂𝐂 1 +πŒπ€π—_𝐍𝐂𝐂 2 -2.

Proof 162 Similar to PropositionΒ 157.