View of Computation of Maximal Matching in Cantor Fractal Set and Fractal Hilbert Curve

4485

Computation of Maximal Matching in Cantor Fractal Set and Fractal Hilbert Curve

P.Tharaniya

, G.Jayalalitha

1Research Scholar, Department of Mathematics,VELS Institute of Science, Technology and Advanced Studies,Chennai, India. E-mail:[email protected].

2Professor, Department of Mathematics,VELS Institute of Science, Technology and Advanced Studies, Chennai, India. E-mail:[email protected]

ABSTRACT

The aim of this chapter gives more valuable information about many Fractal Graphs. It analyses the structure, implementation of vertices, Edges and angles of two different Fractal Graphs for all Iteration.One is Cantor Set which is one dimensional fractal graph and secondis Hilbert curve which is one of the types of Fractal Antenna and two dimensional Fractal Graph also. It finds out the implementation of Vertices and Edges at all iteration follows the Constant Formulae in the Fractal Graph. This chapter shows that in which formulae is applied for the implementation of vertices and Edges in the Fractal Graph.Matching is one of the very important and more scope topic in Graph Theory. Calculation of Maximal Matching is one of the major evaluations in this chapter. It finds the new formulae separately for calculating cardinality in Matching which is depending on the total number of vertices and total number of edges in the corresponding Iteration of the given Fractal Graph. Calculation of Maximal Matching can be determined by using Iterative Methods and also it can be implemented by Theorem.

KEYWORDS

Vertex, Edge, Matching, Maximum Matching, Maximal Matching, Similarity, Fractals, Mathematical Induction.

AMS Classification key: 05C07, 05C70, 91B68, 28A80, C53, 51N3.

Introduction-Fractal Graph

Fractal[5] is the new branch of Mathematics which is related to Graph Theory[3]. Most of the Physical Matter of Nature and Artic does not have the proper Geometric shape of Euclidean Geometry. Fractal Geometry[4] has many ways of defining, computing, surveying and anticipating and forecasting of such Natural Phenomena. Fractals have the major area of construction of nature. Fractals displays all over the world of nature and shows that the characterization of essence of our lives. Everyone on this world has seen a fractal in their life; even up so do not even know it. It is not possible to define the natural things in our nature such as trees, rivers, plants, landscape, and leaves and so on, as geometric images. Matching is the major part of Graph Theory. It has many applications in real life like Medical, Architecture and Computer Science and so on.

Matching

A Matching[1] in Graph Theory consists of all non-touching edges. Itdoes not have loop inside the graph and also without sharing a common vertex between them. In which of the vertices lies in the set of non-adjacent edges is called saturated which vertex is not belongs to the set of matching is called as unsaturated. Maximum matching[2] is nothing but consists of maximum number of non-adjacent edges taken from the given graph.

Cardinality

Cardinality[6] means that the count of number of edges in matching set. Always maximum Matching cardinality is higher than other matching cardinality.

Maximum Matching

Maximum Matching set those are having maximum number of edges or Maximum Cardinality value in the Given Graph is called as Maximum Matching Set. The total number of edges in this set is called as Cardinality of Maximum Matching [7].

Maximal Matching

Maximal Matching[10] is the Superior matching that does not possible to allow even a single edge. It consist minimum number of edges in the Matching Set. But those edges are adjacent with all the vertices in the given graph, no one vertex is missing to adjacent themselves. This set of collection of edges in the given graph is called maximal matching set. Number of edges belongs to this set is called as Maximal Matching Cardinality[11]. Its cardinality is always less than the total number of edges in the graph which is except from topological dimension which is the single line from the unit interval [0, 1].

Cantor Set

History & Construction

Cantor set[6] is a single line segment which has the set of points lying on it. Henry John Stephen smith discovered it.

It was implemented and most famous by Georg Cantor in later. Cantor defined the set in a single edge at initial stage with 2 vertices which is named as Cantor ternary set in later. Its construction is very simple. It built by subsidiary rule[12]. It built by eliminating the middle of the line portion which has been splitted into three parts. It implies two edges with four vertices. Again these two edges are splitted into three parts and also eliminating the middle third of the line portion. It makes four non-adjacent edges with eight vertices. In this manner, repeat the same with the remaining shortest line portions. Cantor quoted this special cantor set is most familiar and moderate compact set[13].

It is considered by Fractal Graph. Each portion of a line segment satisfies the main rule of self- similarity of Fractal Graph. It is an example of string fractal.

Calculation of Vertices and Edges in Cantor Set Iteration 1

In the first Iteration, Cantor set consists of the set of numbers in the interval [0,1]. Start with single edge. (i.e.2⁰ = 1).

Number of vertices is 2. (i.e.2¹).

Fig. 1.Initial Iteration of Cantor Set Iteration 2

In the second Iteration, the single edge can be partitioned into three parts; each part has length 1/3. Start with elimination the open middle third (1/3, 2/3) from the interval [0,1] and considering only two line segments [0, 1/3] U [2/3, 1]. Here it gives (i.e.2¹ ) non-adjacent edges. It has four vertices (i.e.2² ) vertices.

Fig. 2.Second Iteration of Cantor Set Iteration 3

In the third Iteration, Again the remaining edges are partitioned into three parts, each partition has length 1/9. Again eliminating the open middle third of the remaining partitioned edges i.e. eliminating the open interval (1/9,2/9) and (7/9,8/9), leaving the four line segment [0, 1/9] ∪ [2/9, 1/3] ∪ [2/3, 7/9] ∪ [8/9, 1].Totally it has four ( i.e.2² ) non- adjacent edges and eight (i.e. 2³) vertices.

Fig. 3.Third Iteration of Cantor Set Continue the same process in the upcoming Iteration at infinite times.

Iteration n

In the n^th Iteration, the single edge has partitioned into 2^𝑛−1 non-adjacent edges and it has 2^𝑛 vertices where n is a

4487

Matching in Cantor Set

In Cantor set consists of all non-adjacent edges in all iteration[8]. Obviously, this collection of edges in Cantor set considered as Matching set those are considering non-adjacent edges. Therefore, the number of edges in cantor set for all iteration is considered as Matching Cardinality[15]. In other rule, it can be calculated by the half of the number of vertices in the corresponding Iteration of Cantor set. Maximum Matching Cardinality and Maximal Matching Cardinality both are remains the same value in cantor set. It is shown as Table 1.

Table1. Maximum Matching & Maximal Matching In Cantor Set ITERATION

n

NO OF VERTICES

2^𝑛

NO OF EDGES

2^𝑛−1

MAXIMUM MATCHING

MAXIMAL MATCHING

1 2 1 1 1

2 4 2 2 2

3 8 4 4 4

4 16 8 8 8

5 32 16 16 16

Fig. 4. Different Iteration of Cantor Set

Hilbert Curve

Hilbert Curve[9] is one of the famous structures ofFractal Antenna. It is very useful to which is the most famous and worth Structure of Antenna when compared to other model of Antennas. This type of Fractal Design has self- similarityitself[16]. In this type of Self-similarity fractal antenna design gives more interpretation, effective length and variations. It is better than other antenna available in the world. It can transmit electromagnetic radiation over the total surface area. Metamaterial used to build Hilbert Curve.

Construction & Calculation of Vertices and Edges in Hilbert Curve Iteration 1

Start at unit square without top side[14]. Basically it looks like U shape but in the bended curve should be straightened[17]. It can be drawn at 2 X 2 grids. U shape started at left side corner cell, move downward then move right side move and move upward. It can be shown in the Figure no 5. Arrow marks indicated the movement of edges in further. To finish the move at the right corner of cells of Grids.

Calculation of Vertices and Edges in Iteration 1

In this Hilbert Curve[18] consists of 4^𝑛 number of vertices in all iteration where n is the number of Iteration, it is real no and it is increased by one in upcoming Iteration. It is open walk without crossing edges. Therefore it consists number of edges is equal to less than one from number of vertices in all Iteration. In the first Iteration started with three edges.

Number of vertices is 4. (i.e.4¹)

Fig. 5.Initial Iteration of Hilbert Curve Iteration 2

In the second Iteration, Each square box of grid in the first Iteration can be multiplied into 2 x 2 grids. The second Iteration of Hilbert Curve can be represented in 4 x 4 grids.The straightened U Shape or square box without top can be placed in all 2 x 2 grids in order wise. Every 2 x 2 grid should be numbered in bold letters in the above figure 5.

The direction of open square part is differed in 2 x 2 grids. Second Iteration started at first cells of2 x 2 grids. Here the direction of first open square part is rightward. In second 2 x 2 grids, the direction of open square part is leftward.

In third and fourth 2 x 2 grid, the direction of open square part moves upward. The edges named as A, B & C are joined edges which is used to join the square box in all 2 x 2 grid. Finally we get self-similarity fractal Hilbert curve in second Iteration. It is shown as in Figure no 6. Arrow mark shows the direction of movement[19].

Calculation of Vertices and Edges in Iteration 2

In the second Iteration, Number of vertices is 16. (i.e.4²).Number of Edges is 15.

Fig. 6.Second Iteration of Hilbert Curve Iteration 3

In the third Iteration, Again 2 x 2 grids can be expanded into 4 x 4 grids. Now it gives 8 x 8 grids. The same pictures of second iteration should be placed in every 4 x 4 grids it is mentioned as A, B, C, and D in the given Figure no 7. In first 4 x 4 grids has the pictures in rightward direction, second 4 x 4 grids has picture in leftward, Third and Fourth grids has the picture in upward direction. The arrow mark indicates the edges which are used to join pictures in 4 x 4 grids. In the following figure shows the third Iteration of Hilbert Curve.

4489

In the second Iteration, Number of vertices is 64. (i.e.4³) Number of Edges is 63

Fig. 7.Third Iteration of Hilbert Curve Continue the same process in all upcoming Iteration.

Result

Calculation of Vertices and Edges shows that it follows a constant ratio of implementation in all Iteration. Increase of Vertices follows the multiple of 4 elements. In the first Iteration4¹ vertices, second Iteration4²vertices, third Iteration 4³ vertices which implies, in the n^th Iteration of Hilbert Curve has 4^𝑛 vertices. It is open connected path length.

Obviously it is 2 – regular graph. By the property of Graphs [20],

The number of edges of open walk = No of vertices – 1 E (G) = V (G) – 1

Theorem

Hilbert curve consists 4 ⁿ number of vertices and 4ⁿ-1 number of edges in all iterations.Maximal Matching Cardinality is calculated by the following formulae,

Maximal Matching cardinality = 𝑵𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒆𝒅𝒈𝒆𝒔

𝟑 .

Proof

Let to prove the theorem by Iteration method [3].

Step 1: This theorem can be proved for an Initial Iteration. Here n=1.

Number of Vertices =4^𝑛= 4¹= 4

Number of Vertices =4^𝑛− 1 = 4¹− 1= 3(It is shown as figure no 5).

Maximal Matching cardinality = Number of edges

3 = ³

3= 1. Theorem is proved.

Fig. 8.Maximal Matching in Initial Iteration of Hilbert Curve Step 2:This theorem can be proved for Second Iteration. Here n=2.

Number of Vertices =4ⁿ= 4²= 16

Number of Vertices =4ⁿ− 1 = 4²− 1= 15 (It is shown as figure no 6).

Maximal Matching cardinality = Number of edges

3 = ¹⁵

3= 5

Fig. 9.Maximal Matching in Second Iteration of Hilbert Curve Step 3: This theorem can be proved for Third Iteration. Here n=3.

Number of Vertices =4ⁿ= 4³= 64

Number of Vertices =4ⁿ− 1 = 4³− 1= 63 (It is shown as figure no 7).

Maximal Matching cardinality = Number of edges

3 = ⁶³

3= 21

Fig. 10.Maximal Matching in Third Iteration of Hilbert Curve

4491

In the n^th Iteration, Hilbert Curve has 𝟒^𝒏− 𝟏number of edges and 𝟒^𝒏number of vertices.

Result : Maximal Matching cardinality =𝑵𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒆𝒅𝒈𝒆𝒔 𝟑 = ^{𝟒𝒏−𝟏}

𝟑 for all n >0

Table 2.Calculation of Maximal Matching Cardinality

ITERATION n FIGURE

NO. OF VERTICES

𝟒^𝐧

NO. OF EDGES E(G)=

V(G)-1

MAXIMAL MATCHING CARDINALITY M(G)=^𝑬(𝑮)

𝟑

I 2 4 3 1

II 4 16 15 5

III 6 64 63 21

IV 8 256 255 85

V 10 1024 1023 341

VI 12 4096 4095 1365

Conclusion

In this paper apply the concept of Maximal Matching in the Fractal Graph likeCantor Set and Hilbert Curve which is the famous structure of Fractal Antenna. Here it analyse the Structure, Properties, Calculation of number of Vertices as well as edges and at last give two General Formula for the calculation of Maximum Matching Cardinality in those Fractal Graph by the method of Iterative Function. In the future work, let us derive the General Formula for Maximal Matching Cardinality in Various Fractal Antenna Curve like Peano Curve. This is new study to combine the concepts of Matching and Fractal Graphs.

References

[1] Even S, Karivo,(1975) An Algorithm for Maximum Matching in General Graphs, FOC, pp. 100-112.

[2] J.F. Buss and P.W. Shor. (1984), On the page number of planar graphs. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 98– 100. ACM.

[3] R.Suguna., P.Tharaniya., G.Jayalalitha.,(2020)Maximum Matching in Sierpenski Arrow Head Curves., Journal of Advanced Research in Dynamical & Control Systems, 12(3), pp. 1380-1385.

[4] Kenneth Falconer, (2014), Fractal Geometry Mathematical Foundation and Applications, ThirdEdition, WILEY.

[5] J.M.Blackledge, A.K.Evans, M.J.Turner, (2014),Fractal Geometry Mathematical Methods Algorithms, Application, Elsevier.

[6] H. Bruhn, A. Georgakopoulos, P. Sprüssel, (2010)Every rayless graph has an unfriendly partition,Combinatoric, pp. 521-532.

[7] P.Tharaniya, G.Jayalalitha, Maximum Matching in Fractal Graph(2019),The International Journal of Analytical and Experimental Modal Analysis, XI(X), pp. 138-143.

[8] A.Anitha, P.Tharaniya, S.Senthil, G.Jayalalitha.(2020). Analyzation of MaximumMatching and Maximal Matching in VariousGraphs.International Journal of Pharmaceutical Research, 12(3), 778-782.

[9] K. Kawarabayashi, et al (2012) On the excluded minor structure theorem for graphs of large tree-width,J.

4493

[10] Bostjan Bresar,Douglas F. Rall, (2009), Fair Reception and Vizing’s Conjecture, Journal of Graph Theory.

Pp 45-54.

[11] Ananchuen N, Plummer MD (2007), 3-Factor-criticality in domination critical graphs. Discrete Math307, pp 3006–3015.

[12] J. F. Fink, M. S. Jacobson, L. F. Kinch and J. Roberts,(1985). On graphs having domination number half their order. Period. Math. Hungar, 16, pp 287-293.

[13] D. C. Fisher et al (1994). Fractional domination of strong direct products. Discrete Appl. Math., 50(1), pp 89-91.

[14] Goodrich et al (2015). Section 13.1: Graph terminology and representations. Algorithm Design and Applications, Wiley, pp. 355–364.

[15] Harary, Frank (1969). Graph Theory, Reading Massachusetts: Addison-Wesley.

[16] B. Bresar. (2001). On Vizing’s conjecture. Discuss. Math. Graph Theory, 21(1), pp 5-11.

[17] Douglas B.West. (2000). Introduction to Graph Theory. Second Edition, Prentice Hall.

[18] R.Balakrishnan, et al(2015). Graph Theory and its Applications. Narosa Publications.