المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية
الفرعون رعمسيس الثامن
2024-11-28
رعمسيس السابع
2024-11-28
: نسيآمون الكاهن الأكبر «لآمون» في «الكرنك»
2024-11-28
الكاهن الأكبر (لآمون) في عهد رعمسيس السادس (الكاهن مري باستت)
2024-11-28
مقبرة (رعمسيس السادس)
2024-11-28
حصاد البطاطس
2024-11-28


Rectilinear Crossing Number  
  
1864   01:56 صباحاً   date: 3-4-2022
Author : Ábrego, B. M. and Fernández-Merchant, S
Book or Source : "A Lower Bound for the Rectilinear Crossing Number." Graphs and Comb. 21,
Page and Part : ...


Read More
Date: 8-4-2022 1592
Date: 15-3-2022 1034
Date: 29-3-2022 2001

Rectilinear Crossing Number

 

The rectilinear crossing number of a graph G is the minimum number of crossings in a straight line embedding of G in a plane. It is variously denoted rcr(G)cr^_(G) (Schaefer 2017), RCN(G), or nu^_(G).

It is sometimes claimed that the rectilinear crossing number is also known as the linear or geometric(al) crossing number, but evidence for that is slim (Schafer 2017).

A disconnected graph has a rectilinear crossing number equal to the sums of the rectilinear crossing numbers of its connected components.

When the (non-rectilinear) graph crossing number satisfies cr(G)<=3,

 rcrnu(G)=rcr(G)

(1)

(Bienstock and Dean 1993). While Bienstock and Dean don't actually prove equality for the case rcr(G)=3, they state it can be established analogously to rcr(G)<=2. The result cannot be extended to cr<=4, since there exist graphs G with cr(G)=4 but rcr(G)=m for any m>=4 (Bienstock and Dean 1993; Schaefer 2017, p. 54).

G. Exoo (pers. comm., May 11-12, 2019) has written a program which can compute rectilinear crossing numbers for cubic graphs up to around 20 vertices and up to 11 or 12 vertices for arbitrary simple graphs.

The smallest simple graphs for which rcr(G)>cr(G) occur on 8 nodes. The four such examples as summarized in the following table.

graph cr(G) rcr(G)
16-cell graph K_(4×2) 6 8
(8,5)-Turán graph 9 10
8-double toroidal graph 8 9 10
complete graph K_8 18 19

For a complete graph K_n of order n>=10, the rectilinear crossing number is always larger than the general graph crossing number. For the complete graph K_n with n=1, 2, ..., rcr(K_n) is 0, 0, 0, 0, 1, 3, 9, 19, 36, 62, ... (OEIS A014540; White and Beineke 1978, Scheinerman and Wilf 1994). Although it had long been known that rcr(K_(10)) was either 61 or 62 (Singer 1971, Gardner 1986), it was finally proven to be 62 by Brodsky et al. (2000, 2001). The case n=11 was settled in 2004, and found to be 102. The Rectilinear Crossing Number Project (http://www.ist.tugraz.at/staff/aichholzer/crossings.html) has found all values for n<=17, and from very recent mathematical considerations, the rectilinear crossing numbers for n=19 and n=21 are also known. At the moment, the smallest value remaining unsettled is n=20.

RectilinearCrossingNumberK

The following table summarizes known results (Rectilinear Crossing Number Project), and embeddings with minimal rectilinear crossing numbers are illustrated above (Read and Wilson 1998, pp. 282-283, with the erroneous embedding for K_9 corrected).

n rcr(K_n) non-isomorphic embeddings
3 0  
4 0  
5 1 1
6 3 1
7 9 3
8 19 2
9 36 10
10 62 2
11 102 374
12 153 1
13 229 4534
14 324 20
15 447 16001
16 603 36
17 798 >=37269
18 1029 >=1
19 1318 >=13243
20 [1652,1657] >=6
21 2055 ?
22 [2521,2528] ?
23 [3075,3077] ?
24 [3690,3699] ?
25 [4426,4430] ?

Upper limits have been provided by Singer (1971), who showed that

 rcr(K_n)<=1/(312)(5n^4-39n^3+91n^2-57n),

(2)

and Jensen (1971), who showed that

 rcr(K_n)<=7/(432)n^4+O(n^3).

(3)

The best known bounds are given by

 (3/8+epsilon)(n; 4)+O(n^3)<rcr(K_n)<0.3807(n; 4)+O(n^3),

(4)

where epsilon approx 10^(-5). The upper bound is due to Aichholzer et al. (2002) and the lower bound to Lovász et al. (2004). A slightly weaker bound of 3/8(n; 4) was independently proved by Ábrego and Fernández-Merchand (2003). The small epsilon term in the lower bound is significant because it shows that the crossing number and the rectilinear crossing number of complete graphs differ in the leading term. In particular, it is known that there are non-rectilinear embeddings of K_n with 3/8(n; 4)+O(n^3) crossings (Moon 1965, Guy 1967).

Letting

 rho=lim_(n->infty)(rcr(K_n))/((n; 4)),

(5)

the best bounds known are

 0.290<(61)/(210)<=rho<=5/(13)<0.385,

(6)

where (n; k) is a binomial coefficient and the exact value of rho is not known (Finch 2003).

The rectilinear crossing number has an unexpected connection with Sylvester's four-point problem (Finch 2003).


REFERENCES

Ábrego, B. M. and Fernández-Merchant, S. "A Lower Bound for the Rectilinear Crossing Number." Graphs and Comb. 21, 293-300, 2005.

Aichholzer, O. "On the Rectilinear Crossing Number." http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/.

Aichholzer, O.; Aurenhammer, F.; and Krasser, H. "On the Crossing Number of Complete Graphs." In Proc. 18th Ann. ACM Symp. Comp. Geom., Barcelona, Spain, pp. 19-24, 2002.

Bienstock, D. and Dean, N. "New Results on Rectilinear Crossing Numbers and Plane Embeddings." J. Graph Th. 16, 389-398, 1992.

Bienstock, D. and Dean, N. "Bounds for Rectilinear Crossing Numbers." J. Graph Th. 17, 333-348, 1993.

Brodsky, A.; Durocher, S.; and Gethner, E. "Toward the Rectilinear Crossing Number of K_n: New Drawings, Upper Bounds, and Asymptotics." http://www.cs.ubc.ca/spider/abrodsky/papers/reccr_n.ps.gz.Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of K_(10) is 62." 22 Sep 2000.

 http://arxiv.org/abs/cs.DM/0009023.Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of K_(10) is 62." Electronic J. Combinatorics 8, No. 1, R23, 1-30, 2001. 

http://www.combinatorics.org/Volume_8/Abstracts/v8i1r23.html.Finch, S. R. "Rectilinear Crossing Constant." §8.18 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 532-534, 2003.

Gardner, M. Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, 1986.Guy, R. K. "A Combinatorial Problem." NABLA (Bull. Malayan Math. Soc.) 7, 68-72, 1967.

Guy, R. K. "Crossing Numbers of Graphs." In Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 

(Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972.

Harary, F. and Hill, A. "On the Number of Crossings in a Complete Graph." Proc. Edinburgh Math. Soc. 13, 333-338, 1962/1963.

Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.

Jensen, H. F. "An Upper Bound for the Rectilinear Crossing Number of the Complete Graph." J. Combin. Th. B 10, 212-216, 1971.

Klee, V. "What is the Expected Volume of a Simplex Whose Vertices are Chosen at Random from a Given Convex Body." Amer. Math. Monthly 76, 286-288, 1969.

Lovász, L.; Vesztergombi, K.; Wagner, U.; and Welzl, E. "Convex Quadrilaterals and k-Sets." In Towards a Theory of Crossing Numbers (Ed. J. Pach). Providence, RI: Amer. Math. Soc., pp. 139-148, 2004.

Moon, J. "On the Distribution of Crossings in Random Complete Graphs." J. Soc. Indust. Appl. Math. 13, 506-510, 1965.

Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.

Rectilinear Crossing Number Project. http://dist.ist.tugraz.at/cape5/.Schaefer, M. "The Graph Crossing Number and its Variants: A Survey." Elec. J. Combin., DS21, Version 3, Dec. 22, 2017.

Scheinerman, E. and Wilf, H. S. "The Rectilinear Crossing Number of a Complete Graph and Sylvester's 'Four Point' Problem of Geometric Probability." Amer. Math. Monthly 101, 939-943, 1994.

Singer, D. "The Rectilinear Crossing Number of Certain Graphs." Unpublished manuscript, 1971.

Quoted in Gardner, M. Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, 1986.S

loane, N. J. A. Sequence A014540 in "The On-Line Encyclopedia of Integer Sequences."White, A. T. and Beineke, L. W. "Topological Graph Theory." In Selected Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson). New York: Academic Press, pp. 15-49, 1978.

Wilf, H. "On Crossing Numbers, and Some Unsolved Problems." In Combinatorics, Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993 (Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997.




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.