المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية
ENGLISH
آخر المواضيع المضافة

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

Untitled Document
أبحث عن شيء أخر
أضيف حديثاً
مـقايـيـس حركة العمالة لتـقييـم تـجربـة إعـادة الهـيكلـة
2024-11-06
مـقايـيس الجـودة والرضـا لتـقييـم تـجربـة إعـادة الهـيكلـة
2024-11-06
مقاييس الإنتاجية لتـقييـم تـجربـة إعـادة الهـيكلـة
2024-11-06
تقييم تجربة إعادة الهيكلة (مقاييس الالتزام بالخطة)
2024-11-06
السـيطـرة عـلـى مـقاومـة التـغيـير فـي المنظمـات
2024-11-06
إعـداد خـطـة إعـادة الهـيكـلـة 2
2024-11-06

وثائقيات
العباءة العربية .. إرث الآباء واعتزاز الأبناء
التاريخ / 20-09-2024

مختارات
Nucleosome-Free Regions
20-5-2019
Azotemia
24-6-2017
الإنفاق للشهرة مباح وللرياء معصية
24-8-2022
حبة البركة الشائعة​ Nigella sativa L
12-2-2021
Leo Zippin
3-11-2017
الاستثناء الواقع عقيب الجمل
5-8-2016

Independence Polynomial  
  
1403   06:11 مساءً   date: 19-4-2022
Author : Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M.
Book or Source : "Domination and Irredundance in the Queens Graph." Disc. Math. 163
Page and Part : ...


Read More
Bipartite Graph
Date: 24-3-2022 1352
Edge Cut
Date: 17-3-2022 2339
Königsberg Bridge Problem
Date: 1-3-2022 2147

Independence Polynomial

Let s_k be the number of independent vertex sets of cardinality k in a graph G. The polynomial

I(x)=sum_(k=0)^(alpha(G))s_kx^k,

(1)

where alpha(G) is the independence number, is called the independence polynomial of G (Gutman and Harary 1983, Levit and Mandrescu 2005). It is also goes by several other names, including the independent set polynomial (Hoede and Li 1994) or stable set polynomial (Chudnovsky and Seymour 2004).

The independence polynomial is closely related to the matching polynomial. In particular, since independent edge sets in the line graph L(G) correspond to independent vertex sets in the original graph G, the matching-generating polynomial of a graph G is equal to the independence polynomial of the line graph of G (Levit and Mandrescu 2005):

mu_G(x)=I_(L(G))(x).

(2)

The independence polynomial is also related to the clique polynomial C_G(x) by

C_G(x)=I_(G^_)(x),

(3)

where G^_ denotes the graph complement (Hoede and Li 1994), and to the vertex cover polynomial by

I_G(x)=x^nPsi_g(x^(-1)),

(4)

where n=|G| is the vertex count of G (Akban and Oboudi 2013).

The independence polynomial of a disconnected graph is equal to the product of independence polynomials of its connected components.

Precomputed independence polynomials for many named graphs in terms of a variable x can be obtained in the Wolfram Language using GraphData[graph, "IndependencePolynomial"][x].

The following table summarizes closed forms for the independence polynomials of some common classes of graphs. Here, s=sqrt(x^2+6x+1), t=sqrt(1+4x), and u=sqrt((x+1)(5x+1)).

graph I(x)
Andrásfai graph A_n 1+(3n-1)x(x+1)^(n-1)
barbell graph [1+(n-1)x][1+(n+1)x]
book graph S_(n+1) square P_2 2x(1+x)^n+(1+2x)^n
centipede graph ((-1+u-3x)(1-u+x)^n+(1+u+x)^n(1+u_3x))/(2^(n+1)u)
cocktail party graph K_(n×2) 1+nx(x+2)
complete bipartite graph K_(n,n) 2(x+1)^n-1
complete graph K_n 1+nx
complete tripartite graph K_(n,n,n) 3(x+1)^n-2
crossed prism graph 2^(-n)[(1+2x(2+x)-sqrt((1+2x)(1+6x)))^n+(1+2x(2+x)+sqrt((1+2x)(1+6x)))^n]
crown graph 2(x+1)^n+nx^2-1
cycle graph C_n 2(-x)^(n/2)T_n(1/(2sqrt(-x)))
gear graph x(x+1)^n+((1-t+2x)^n+(1+t+2x)^n)/(2^n)
helm graph 2^(-n)[2^nx(+x+1)^n+(x-u+1)^n+(x+u+1)^n]
ladder graph 2^(-(n+1))[(s-3x-1)(x-s+1)^n+(s+3x+1)(x+s+1)^n]
ladder rung graph nP_2 (2x+1)^n
Möbius ladder M_n 2^(-n)[-2^n(-x)^n+(x-s+1)^n+(x+s+1)^n]
pan graph ((1-t)^n(-x+t(2+x))+(1+t)^n(x+t(2+x)))/(2^(n+1)t)
path graph P_n x^((n+1)/2)F_(n+2)(x^(-1/2))
prism graph 2^(-n)[2^n(-x)^n+(1+x-s)^n+(1+x+s)^n]
star graph S_n x+(1+x)^(n-1)
sun graph (x+1)^(n-2)[1+x(x+n+2)]
sunlet graph C_n circledot K_1 2^(-n)[(u+x+1)^n+(-u+x+1)^n]
triangular graph 2^(-n/2)(-isqrt(x))^nH_n(i/(sqrt(2x)))
  =2^(n/2)(-1/x)^(-n/2)U(1/2n,1/2,1/(2x))
wheel graph W_n (-(1-t)^n-(1-t)^nt+(t-1)(1+t)^n+2^(n-1)x^2)/(2^(n+1)x)

The following table summarizes the recurrence relations for independence polynomials for some simple classes of graphs.

graph order recurrence
Andrásfai graph 3 p_n(x)=(2x+3)p_(n-1)(x)-(x+1)(x+3)p_(n-2)(x)+(x+1)^2p_(n-3)(x)
antiprism graph 3 p_n(x)=x^2p_n-3(x)+2xp_n-2(x)+p_n-1(x)
barbell graph 3 p_n(x)=3p_(n-1)(x)-3p_(n-2)(x)+p_(n-3)(x)
book graph S_(n+1) square P_2 2 p_n(x)=(3x+2)p_(n-1)(x)-(x+1)(2x+1)p_(n-2)(x)
centipede graph 2 p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
cocktail party graph K_(n×2) 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
complete bipartite graph K_(n,n) 2 p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
crossed prism graph 2 p_n(x)=(2x^2+4x+1)p_(n-1)(x)-x^2(x^2+4x+2)p_(n-2)(x)
crown graph 3 p_n(x)=(x+3)p_(n-1)(x)-(2x+3)p_(n-2)(x)+(x+1)p_(n-3)(x)
cycle graph C_n 2 p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
gear graph 3 p_n(x)=(3x+2)p_(n-1)(x)-(3x^2+3x+1)p_(n-2)(x)+(x+1)x^2p_(n-3)(x)
helm graph 3 p_n(x)=2(x+1)p_(n-1)(x)-(x+1)p_(n-2)(x)-x(x+1)^2p_(n-3)(x)
ladder graph 2 p_n(x)=(x+1)p_(n-1)(x)+xp_(n-2)(x)
ladder rung graph 1 p_n(x)=(2x+1)p_(n-1)(x)
Möbius ladder M_n 3 p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
pan graph 2 p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
path graph P_n 2 p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
prism graph Y_n 3 p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
star graph S_n 2 p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
sun graph 2 p_n(x)=2(x+1)p_(n-1)(x)-(x+1)^2p_(n-2)(x)
sunlet graph C_n circledot K_1 2 p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
web graph 3 p_n(x)=(x+1)p_(n-1)(x)+2x(x+1)^2p_(n-2)(x)+x^2(x+1)^2p_(n-3)(x)
wheel graph W_n 3 p_n(x)=2p_(n-1)(x)+(x-1)p_(n-2)(x)-xp_(n-3)(x)

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

n independence polynomial graphs
4 (1+x)(1+3x) (4,6), path graph P_4
4 1+4x+2x^2 paw graph, square graph
5 (1+x)^2(1+3x) (5,8), (5,9)
5 (1+x)(1+4x) butterfly graph, house graph, kite graph, (5,24)
5 (1+x)(1+4x+x^2) banner graph, bull graph, (5,15)
5 (1+x)(1+4x+2x^2) fork graph, (5,10), (5,14)
5 1+5x+2x^2 house X graph, wheel graph W_5
5 1+5x+3x^2 gem graph, (5,31), (4,1)-lollipop graph
5 1+5x+5x^2 cycle graph C_5, (3,2)-tadpole graph
5 1+5x+4x^2+x^3 dart graph, complete bipartite graph K_(2,3)

The independence polynomial of a tree is unimodal, and the independence polynomial of a claw-free graph is logarithmically concave.

REFERENCES

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.

Chudnovsky, M. and Seymour, P. "The Roots of the Stable Set Polynomial of a Claw-Free Graph." 2004. http://www.math.princeton.edu/÷mchudnov/publications.html.

Gutman, I. and Harary, F. "Generalizations of the Matching Polynomial." Utilitas Mathematica 24, 97-106, 1983.

Hoede, C. and Li, X. "Clique Polynomials and Independent Set Polynomials of Graphs." Disc. Math. 125, 219-228, 1994.

Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 

(Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.




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


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

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





الأخبار الصحية
مخاطر عدم علاج ارتفاع ضغط الدم
التاريخ / 2024-11-04

الأخبار العلمية
اختراق جديد في علاج سرطان البروستات العدواني
التاريخ / 2024-11-06

الساحة الاسلامية
مدرسة دار العلم.. صرح علميّ متميز في كربلاء لنشر علوم أهل البيت (عليهم السلام)
التاريخ / 2024-11-06