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

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

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية
{افان مات او قتل انقلبتم على اعقابكم}
2024-11-24
العبرة من السابقين
2024-11-24
تدارك الذنوب
2024-11-24
الإصرار على الذنب
2024-11-24
معنى قوله تعالى زين للناس حب الشهوات من النساء
2024-11-24
مسألتان في طلب المغفرة من الله
2024-11-24

برمنغنات البوتاسيوم
10-6-2018
الترسل في الدعاء
2024-09-08
الـتصنـيع الـدولـي وإدارة المـخـزون
2024-01-23
السبورات الصيفية Summer Spores
4-5-2020
مصر تحت حكم الاجانب
12-1-2017
جولة لغويّة في اسباب النزول
24-04-2015

Rank Polynomial  
  
1336   04:07 مساءً   date: 20-4-2022
Author : Biggs, N. L
Book or Source : Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press
Page and Part : ...


Read More
Date: 11-5-2022 1791
Date: 15-3-2022 1509
Date: 27-3-2022 1244

Rank Polynomial

The rank polynomial R(x,y) of a general graph G is the function defined by

 R(x,y)=sum_(S subset= E(G))x^(r(S))y^(s(S)),

(1)

where the sum is taken over all subgraphs (i.e., edge sets) and the rank r(S) and co-rank s(S) of the subgraph S is given by

r(S) = n-c

(2)

s(S) = m-n+c

(3)

for a subgraph with n vertices, m edges, and c connected components (Biggs 1993, p. 73).

The rank polynomial is multiplicative over graph components, so for a graph G having connected components G_1G_2, ..., the rank polynomial of G itself is given by

 R_G=R_(G_1)R_(G_2)....

(4)

It is given in terms of the Tutte polynomial T(x,y) as

 R(x,y)=x^(n-c)T(x^(-1)+1,y+1).

(5)

The chromatic polynomial pi(x) and rank polynomial of a general graph G with n vertices are related by

 pi(x)=x^nR(-x^(-1),-1)

(6)

(Biggs 1993, p. 75).

Trivially,

 R(x,x)=(x+1)^m,

(7)

where m is the number of edges of the graph (Biggs 1993, p. 74).

The following table summarizes rank polynomials for some common classes of graphs.

graph rank polynomial
banana tree (1+x)^(nk)
book graph S_(n+1) square P_2 ([1+3x(x+1)]^n(y-x)+x(y+1){1+x[3+x(3+y)]}^n)/y
centipede graph (x+1)^(2n-1)
cycle graph C_n x^(n-1)(y-x)+(x+1)^n
gear graph (x[x^2(y+4)+3x+1-s]^n+x[x^2(y+4)+3x+1+s]^n-2^(n+1)x^(2n+1)+2^nyx^(2n))/x
ladder rung graph nP_2 (1+x)^n
pan graph x^(n-1)(y-x)+(x+1)^(n+1)
path graph P_n (1+x)^(n-1)
star graph S_n (1+x)^n
sunlet graph C_n circledot K_1 (1+x)^n[(1+x)^n+x^(n-1)(y-x)]

The following table summarizes recurrence equations for rank polynomials of common classes of graphs.

graph recurrence
book graph S_(n+1) square P_2 p_n=(x^2y+6x^2+6x+2)p_(n-1)-(3x^2+3x+1)(x^2y+3x^2+3x+1)p_(n-2)
cycle graph C_n p_n=(2x+1)p_(n-1)-x(x+1)p_(n-2)
gear graph p_n=(1+3x+5x^2+x^2y)p_(n-1)-x^2(2+5x+5x^2+y+2xy+2x^2y)p_(n-2)+(x^4(1+x)^2(1+y))p_(n-3)
helm graph p_n=(x+1)(xy+4x+1)p_(n-1)-x(2x+1)(x+1)^2(y+2)p_(n-2)+x^2(x+1)^4(y+1)p_(n-3)
ladder graph L_n p_n=(1+3x+4x^2+x^2y)p_(n-1)-x^2(x+1)^2(y+1)p_(n-2)
pan graph p_n=(2x+1)p_(n-1)-x(x+1)p_(n-2)
sunlet graph C_n circledot K_1 p_n=(x+1)(2x+1)p_(n-1)-x(x+1)^3p_(n-2)
wheel graph W_n p_n=(1+4x+xy)p_(n-1)-x(2x+1)(y+2)p_(n-2)+x^2(x+1)(y+1)p_(n-3)

Nonisomorphic graphs do not necessarily have distinct rank polynomials. The following table summarizes some co-rank graphs.

rank polynomial graphs
1 empty graph K^__n
1+x (3,2)(4,2)(5,2)(6,2)(7,2)(8,2), path graph P_2
1+3x+3x^2+x^2y triangle graph, (4,6)(5,8)(6,10)(7,12)(8,14)
(1+x)^2 (4,3)(5,3)(5,6)(6,3)(7,3)(7,8)(8,3)(8,9)(2,6)-fiveleaper graph, (4,5)-fiveleaper graph, (2,3)-knight graph, 2-ladder rung graph, path graph P_3
(1+x)^3 claw graph, (5,4)(5,7)(5,9)(6,4)(6,8)(6,11)(7,4)(7,9)(7,13)(7,58)(8,4)(8,10)(8,15)(8,88)(3,6)-fiveleaper graph, 3-ladder rung graph, path graph P_4
(1+x)(1+3x+3x^2+x^2y) paw graph, (5,10)(5,20)(6,12)(6,37)(7,14)(7,60)(8,16)(8,91)
1+4x+6x^2+4x^3+x^3y square graph, C_4(5,14)(6,22)(7,30)(8,38)
1+5x+10x^2+8x^3+2x^2y+5x^3y+x^3y^2 diamond graph, (5,15)(6,23)(7,31)(8,39)
1+6x+15x^2+16x^3+4x^2y+15x^3y+6x^3y^2+x^3y^3 tetrahedral graph, (5,24)(6,58)(7,114)(8,199)

REFERENCES

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 73, 97, and 101, 1993.

Godsil, C. and Royle, G. "Rank Polynomial" and "Evaluations of the Rank Polynomial." §15.9-15.10 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 355-358, 2001.




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


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

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