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

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

Untitled Document
أبحث عن شيء أخر
زكاة الذهب والفضة
2024-11-05
ماشية اللحم في الولايات المتحدة الأمريكية
2024-11-05
أوجه الاستعانة بالخبير
2024-11-05
زكاة البقر
2024-11-05
الحالات التي لا يقبل فيها الإثبات بشهادة الشهود
2024-11-05
إجراءات المعاينة
2024-11-05

لماذا يرفض البعض وجود الحكومة ؟
13-02-2015
علم الاصول في فكر الامام الباقر
21-8-2016
Triangle Triangle Picking
14-2-2020
APOA وحدات بروتينات
20-1-2021
أنواع الصياغة التشريعية للقواعد الانضباطية وعيوبها
2023-11-12
خصائص القرار الإداري المطعون فيه بالإلغاء
2024-04-14

Independence Number  
  
1721   04:43 مساءً   date: 1-5-2022
Author : Bollobás, B
Book or Source : "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83
Page and Part : ...


Read More
Date: 19-5-2022 1580
Date: 15-5-2022 1211
Date: 4-3-2022 1373

Independence Number

The (upper) vertex independence number of a graph, often called simply "the" independence number, is the cardinality of the largest independent vertex set, i.e., the size of a maximum independent vertex set (which is the same as the size of a largest maximal independent vertex set). The independence number is most commonly denoted alpha(G), but may also be written beta(G) (e.g., Burger et al. 1997) or beta_0(G) (e.g., Bollobás 1981).

The independence number of a graph is equal to the largest exponent in the graph's independence polynomial.

The lower independence number i(G) may be similarly defined as the size of a smallest maximal independent vertex set in G (Burger et al. 1997).

The lower irredundance number ir(G), lower domination number gamma(G), lower independence number i(G), upper independence number alpha(G), upper domination number Gamma(G), and upper irredundance number IR(G) satsify the chain of inequalities

 ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)

(1)

(Burger et al. 1997).

The ratio of the independence number of a graph G to its vertex count is known as the independence ratio of G (Bollobás 1981).

For a connected regular graph G on n>1 vertices with vertex degree k and smallest graph eigenvalue s,

 alpha<=(n(-s))/(k-s)

(2)

(A. E. Brouwer, pers. comm., Dec. 17, 2012).

For r the graph radius,

 alpha>=r

(3)

(DeLa Vina and Waller 2002). Lovasz (1979, p. 55) showed that when rho is the path covering number,

 alpha>=rho,

(4)

with equality for only complete graphs (DeLa Vina and Waller 2002).

The matching number nu(G) of a graph G is equal to the independence number alpha(L(G)) of its line graph L(G).

By definition,

 alpha(G)+tau(G)=|G|,

(5)

where tau(G) is the vertex cover number of G and n=|G| its vertex count (West 2000).

Known value for some classes of graph are summarized below.

graph G alpha(G) OEIS values
alternating group graph AG_n   A000000 1, 1, 4, 20, 120, ...
n-Andrásfai graph (n>=3) n A000027 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-antiprism graph (n>=3) |_2n/3_| A004523 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ...
n-Apollonian network 3^(n-1) A000244 1, 3, 9, 27, 81, 243, 729, 2187, ...
complete bipartite graph K_(n,n) n A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
complete graph K_n 1 A000012 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
complete tripartite graph K_(n,n,n) n A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
cycle graph C_n (n>=3) |_n/2_| A004526 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ...
empty graph K^__n n A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-folded cube graph (n>=2) 2^(n-2)-1/4(1-(-1)^n)(n-1; (n-1)/2) A058622 1, 1, 4, 5, 16, 22, 64, 93, 256, ...
grid graph P_n square P_n [n^2/2] A000982 1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
grid graph P_n square P_n square P_n [n^3/2] A036486 1, 4, 14, 32, 63, 108, 172, 256, 365, 500, ...
n-halved cube graph   A005864 1, 1, 4, 5, 16, 22, 64, 93, 256, ...
n-Hanoi graph 3^(n-1) A000244 1, 3, 9, 27, 81, 243, 729, 2187, ...
hypercube graph Q_n 2^(n-1) A000079 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
n-Keller graph {4   for n=1; 5   for n=2; 2^n   otherwise A258935 4, 5, 8, 16, 32, 64, 128, 256, 512, ...
(n,n)-king graph (n>=2) |_(n+1)/2_|^2 A008794 1, 4, 4, 9, 9, 16, 16, 25, 25
(n,n)-knight graph (n>=2) {4   for n=2; (1+(-1)^(n+1)+2n^2)/4   otherwise A030978 4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
Kneser graph K(n,k) (n-1; k-1)    
n-Mycielski graph {1   for n=1,2; 3·2^(n-3)-1   otherwise A266550 1, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ...
Möbius ladder M_n (n>=3) 2[n/2]-1 A109613 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ...
odd graph O_n {1   for n=1; (2n-2; n-2)   otherwise A000000 1, 1, 4, 15, 56, 210, 792, 3003, 11440, ...
n-pan graph 1+|_n/2_| A000000 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ...
path graph P_n [n/2] A004526 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...
prism graph Y_n (n>=3) 2|_n/2_| A052928 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ...
n-Sierpiński carpet graph     4, 32, 256, ...
n-Sierpiński gasket graph     1, 3, 6, 15, 42, ...
star graph S_n {1   for n=1; n-1   otherwise A028310 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
triangular graph T_n (n>=2) |_n/2_| A004526 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...
n-web graph (n>=3) 1/4[6n+(-1)^n-1]/4 A032766 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ...
wheel graph W_n |_(n-1)/2_| A004526 1, 2, 2, 3, 3, 4, 4, 5, 5, ...

Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using GraphData[graph"IndependenceNumber"].


REFERENCES

Bollobás, B. "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.

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

Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).

DeLa Vina, E. and Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.

Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.

Skiena, S. "Maximum Independent Set" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A000079/M1129, A000244/M2807, A000982/M1348, A004523, A004526, A005864/M1111, A008794, A028310, A030978, A032766, A036486, A052928, A058622, A109613, A258935, and A266550West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.




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


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

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