4.3.4.2. two parameters/one final graph

Proposition 14

πŒπ€π—_𝐍𝐂𝐂=0β‡”πŒπ€π—_𝐍𝐒𝐂𝐂=0

Proposition 15

πŒπ€π—_ππ’π‚π‚β‰€πŒπ€π—_𝐍𝐂𝐂

Proof 15 πŒπ€π—_𝐍𝐒𝐂𝐂 is a lower bound of the size of the largest connected component since the largest strongly connected component is for sure included within a connected component.

Proposition 16

πŒπ€π—_𝐍𝐂𝐂=0β‡”πŒπˆπ_𝐍𝐂𝐂=0

Proposition 17

𝐌𝐈𝐍_ππ‚π‚β‰€πŒπ€π—_𝐍𝐂𝐂

Proposition 18

πŒπ€π—_𝐍𝐂𝐂=0⇔𝐍𝐀𝐑𝐂=0

Proposition 19

πŒπ€π—_𝐍𝐂𝐂>0⇒𝐍𝐀𝐑𝐂β‰₯max(1,πŒπ€π—_𝐍𝐂𝐂-1)

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ:πŒπ€π—_𝐍𝐂𝐂>0⇒𝐍𝐀𝐑𝐂β‰₯max(1,2Β·πŒπ€π—_𝐍𝐂𝐂-2)

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐀𝐑𝐂β‰₯πŒπ€π—_𝐍𝐂𝐂 2

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂β‰₯πŒπ€π—_𝐍𝐂𝐂-1

Proof 19 Β 

(19) πŒπ€π—_𝐍𝐂𝐂-1 arcs are needed to connect πŒπ€π—_𝐍𝐂𝐂 vertices that belong to a given connected component containing at least two vertices. And one arc is required for a connected component containing a single vertex.

(20) Similarly, when the graph is symmetric, 2Β·πŒπ€π—_𝐍𝐂𝐂-2 arcs are needed to connect πŒπ€π—_𝐍𝐂𝐂 vertices that belong to a given connected component containing at least two vertices.

(21) Finally, when the graph is reflexive, symmetric and transitive, πŒπ€π—_𝐍𝐂𝐂 2 arcs are needed to connect πŒπ€π—_𝐍𝐂𝐂 vertices that belong to a given connected component.

(22) When the initial graph corresponds to a path, the minimum number of arcs of a connected component involving n vertices is equal to n-1.

Proposition 20

πŒπ€π—_𝐍𝐂𝐂=0β‡’ππ’πˆππŠ=0

Proposition 21

ππ’πˆππŠβ‰₯1β‡’πŒπ€π—_𝐍𝐂𝐂β‰₯2

Proof 21 Since we do not have any isolated vertex a sink is connected to at least one other vertex. Therefore, if the graph has a sink, there exists at least one connected component with at least two vertices.

Proposition 22

πŒπ€π—_𝐍𝐂𝐂=0β‡’ππ’πŽπ”π‘π‚π„=0

Proposition 23

ππ’πŽπ”π‘π‚π„β‰₯1β‡’πŒπ€π—_𝐍𝐂𝐂β‰₯2

Proof 23 Since we do not have any isolated vertex a source is connected to at least one other vertex. Therefore, if the graph has a source, there exists at least one connected component with at least two vertices.

Proposition 24

πŒπ€π—_𝐍𝐂𝐂=0⇔𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0

Proposition 25

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πŒπ€π—_𝐍𝐂𝐂

Proposition 26

πŒπ€π—_𝐍𝐒𝐂𝐂=0β‡”πŒπˆπ_𝐍𝐒𝐂𝐂=0

Proposition 27

𝐌𝐈𝐍_ππ’π‚π‚β‰€πŒπ€π—_𝐍𝐒𝐂𝐂

Proposition 28

πŒπ€π—_𝐍𝐒𝐂𝐂=0⇔𝐍𝐀𝐑𝐂=0

Proposition 29

𝐍𝐀𝐑𝐂β‰₯πŒπ€π—_𝐍𝐒𝐂𝐂

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ:𝐍𝐀𝐑𝐂β‰₯2Β·πŒπ€π—_𝐍𝐒𝐂𝐂

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐀𝐑𝐂β‰₯πŒπ€π—_𝐍𝐒𝐂𝐂 2

Proof 29 (32) In a strongly connected component at least one arc has to leave each vertex. Since we have at least one strongly connected component of πŒπ€π—_𝐍𝐒𝐂𝐂 vertices this leads to the previous inequality.

Proposition 30

πŒπ€π—_𝐍𝐒𝐂𝐂=0⇔𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0

Proposition 31

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πŒπ€π—_𝐍𝐒𝐂𝐂

Proof 31 By definition of πŒπ€π—_𝐍𝐒𝐂𝐂.

Proposition 32

𝐌𝐈𝐍_𝐍𝐂𝐂=0β‡”πŒπˆπ_𝐍𝐒𝐂𝐂=0

Proposition 33

𝐌𝐈𝐍_𝐍𝐂𝐂β‰₯𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

Proof 33 By construction 𝐌𝐈𝐍_𝐍𝐂𝐂 is an upper bound of the number of vertices of the smallest strongly connected component.

Proposition 34

𝐌𝐈𝐍_𝐍𝐂𝐂=0⇔𝐍𝐀𝐑𝐂=0

Proposition 35

𝐌𝐈𝐍_𝐍𝐂𝐂>0⇒𝐍𝐀𝐑𝐂β‰₯max(1,𝐌𝐈𝐍_𝐍𝐂𝐂-1)

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ:𝐌𝐈𝐍_𝐍𝐂𝐂>0⇒𝐍𝐀𝐑𝐂β‰₯max(1,2·𝐌𝐈𝐍_𝐍𝐂𝐂-2)

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂 2

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂-1

Proof 35 Similar to PropositionΒ 19.

Proposition 36

πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš:(𝐌𝐈𝐍_𝐍𝐂𝐂+1)·𝐍𝐂𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» +1

Proof 36 By definition of πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš.

Proposition 37

𝐌𝐈𝐍_𝐍𝐂𝐂=0⇔𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0

Proposition 38

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂

Proposition 39

𝐌𝐈𝐍_ππ‚π‚βˆ‰min𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -1 2+1,𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1

Proof 39 On the one hand, if 𝐍𝐂𝐂≀1, we have that 𝐌𝐈𝐍_𝐍𝐂𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗. On the other hand, if 𝐍𝐂𝐂>1, we have that 𝐌𝐈𝐍_𝐍𝐂𝐂+𝐌𝐈𝐍_𝐍𝐂𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 and that 𝐌𝐈𝐍_𝐍𝐂𝐂+𝐌𝐈𝐍_𝐍𝐂𝐂+1≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» , which by isolating 𝐌𝐈𝐍_𝐍𝐂𝐂 and by grouping the two inequalities leads to 𝐌𝐈𝐍_𝐍𝐂𝐂≀min𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2,𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -1 2. The result follows.

Proposition 40

𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=0⇔𝐍𝐀𝐑𝐂=0

Proposition 41

𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ:𝐍𝐀𝐑𝐂β‰₯2·𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 2

Proof 41 Similar to PropositionΒ 29.

Proposition 42

𝐌𝐈𝐍_𝐍𝐒𝐂𝐂=0⇔𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0

Proposition 43

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

Proposition 44

𝐍𝐀𝐑𝐂=0⇔𝐍𝐂𝐂=0

Proposition 45

𝐍𝐀𝐑𝐂β‰₯𝐍𝐂𝐂

Proof 45 Each connected component contains at least one arc (since, by hypothesis, each vertex has at least one arc).

Proposition 46

𝐍𝐀𝐑𝐂=0⇔𝐍𝐒𝐂𝐂=0

Proposition 47

𝐍𝐀𝐑𝐂β‰₯𝐍𝐒𝐂𝐂

πš—πš˜ πš•πš˜πš˜πš™:𝐍𝐀𝐑𝐂β‰₯2·𝐍𝐒𝐂𝐂

Proof 47 57 (respectivelyΒ 58) holds since each strongly connected component contains at least one (respectively two) arc(s).

Proposition 48

𝐍𝐀𝐑𝐂β‰₯ππ’πˆππŠ

Proof 48 Since isolated vertices are not allowed, each sink has a distinct ingoing arc.

Proposition 49

𝐍𝐀𝐑𝐂β‰₯ππ’πŽπ”π‘π‚π„

Proof 49 Since isolated vertices are not allowed, each source has a distinct outgoing arc.

Proposition 50

𝐍𝐀𝐑𝐂=0⇔𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0

Proposition 51

𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡:𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗

𝐚𝐫𝐜_𝐠𝐞𝐧=𝐢𝐻𝐴𝐼𝑁:𝐍𝐀𝐑𝐂≀2·𝐍𝐕𝐄𝐑𝐓𝐄𝐗-2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(≀):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰₯):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(<):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(>):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 -𝐍𝐕𝐄𝐑𝐓𝐄𝐗

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπ‘ŒπΆπΏπΈ:𝐍𝐀𝐑𝐂≀2·𝐍𝐕𝐄𝐑𝐓𝐄𝐗

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1

Proof 51 62 holds since each vertex of a digraph can have at most 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 successors. The next items correspond to the maximum number of arcs that can be achieved according to a specific arc generator.

Note that, when the equality is reached in 62, the corresponding extreme graph is in fact the graph initially generated. The same observation holds for inequalities 63 to 71. As a consequence all U-arcs have to be turned into T-arcs.

Proposition 52

2·𝐍𝐀𝐑𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 52 By induction on the number of vertices of a graph G:

  1. If 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G) is equal to 1 or 2 PropositionΒ 52 holds.

  2. Assume that 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)β‰₯3.

    • Assume there exists a vertex v such that, if we remove v, we do not create any isolated vertex in the remaining graph. We have 𝐍𝐀𝐑𝐂(G)β‰₯𝐍𝐀𝐑𝐂(G-v)+1. Thus 2·𝐍𝐀𝐑𝐂(G)β‰₯2·𝐍𝐀𝐑𝐂(G-v)+1. Since by induction hypothesis 2·𝐍𝐀𝐑𝐂(G-v)β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G-v)=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-1 the result holds.

    • Otherwise, all the connected components of G are reduced to two elements with only one arc. We remove one of such connected component (v,w).

      Thus 𝐍𝐀𝐑𝐂(G)=𝐍𝐀𝐑𝐂(G-{v,w})+1. As by induction hypothesis, 2·𝐍𝐀𝐑𝐂(G-{v,w})β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G-{v,w})=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-2 the result holds.

Note that, when the equality is reached in 52, the corresponding extreme graph is in fact a perfect matching of the graph. As a consequence all U-arcs that do not belong to any perfect matching have to be turned into F-arcs.

Proposition 53

𝐚𝐫𝐜_𝐠𝐞𝐧=𝐿𝑂𝑂𝑃:𝐍𝐀𝐑𝐂=𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 53 From the definition of 𝐿𝑂𝑂𝑃.

Proposition 54

𝐍𝐂𝐂=0⇔𝐍𝐒𝐂𝐂=0

Proposition 55

𝐍𝐂𝐂≀𝐍𝐒𝐂𝐂

Proof 55 Holds since each connected component contains at least one strongly connected component.

Note that, when the equality is reached in 55, each connected component of the corresponding extreme graph is strongly connected. As a consequence all sink vertices of the graph induced by the T-vertices and the T-arcs should have at least one successor.

Proposition 56

𝐍𝐂𝐂=0⇔𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0

Proposition 57

𝐍𝐂𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗

πš—πš˜ πš•πš˜πš˜πš™:2·𝐍𝐂𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 57 77 (respectivelyΒ 78) holds since each connected component contains at least one (respectively two) vertex.

Note that, when the equality is reached in 77, the corresponding extreme graph does not contain any arc between two distinct vertices. As a consequence any U-arc between two distinct vertices is turned into a F-vertex.

Proposition 58

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš: 𝐍𝐕𝐄𝐑𝐓𝐄𝐗≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -(𝐍𝐂𝐂-1)

Proof 58 Holds since between two β€œconsecutive” connected components of the initial graph there is at least one vertex that is missing.

Proposition 59

𝐍𝐒𝐂𝐂β‰₯ππ’πˆππŠ+1

Proof 59 Since each sink cannot belong to a circuit and since no isolated vertex is allowed at least one extra non-sink vertex is required the result follows.

Proposition 60

𝐍𝐒𝐂𝐂β‰₯ππ’πŽπ”π‘π‚π„+1

Proof 60 Since each source cannot belong to a circuit and since no isolated vertex is allowed at least one extra non-source vertex is required the result follows.

Proposition 61

𝐍𝐒𝐂𝐂=0⇔𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0

Proposition 62

𝐍𝐒𝐂𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 62 PropositionΒ 62 holds since each strongly connected component contains at least one vertex.

Proposition 63

πšŠπšŒπš’πšŒπš•πš’πšŒ:𝐍𝐒𝐂𝐂=𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 63 In a directed acyclic graph we have that each vertex corresponds to a strongly connected component involving only that vertex.

Proposition 64

𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0β‡’ππ’πˆππŠ=0

Proposition 65

𝐍𝐕𝐄𝐑𝐓𝐄𝐗>0β‡’ππ’πˆππŠ<𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 65 Holds since each sink must have a predecessor that cannot be a sink and since each vertex has at least one arc.

Proposition 66

𝐍𝐕𝐄𝐑𝐓𝐄𝐗=0β‡’ππ’πŽπ”π‘π‚π„=0

Proposition 67

𝐍𝐕𝐄𝐑𝐓𝐄𝐗>0β‡’ππ’πŽπ”π‘π‚π„<𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 67 Holds since each source must have a successor that cannot be a source and since each vertex has at least one arc.