المرجع الألكتروني للمعلوماتية
القرآن الكريم وعلومه
العقائد الإسلامية
الفقه وأصوله 
الرجال والحديث 
سيرة الرسول وآله 
علوم اللغة العربية 
الأدب العربي 
الأسرة والمجتمع 
الأخلاق والأدعية 
التاريخ 
الادارة والاقتصاد 
علم الفيزياء 
علم الكيمياء 
علم الأحياء 
الرياضيات 
الهندسة المدنية 
الزراعة 
الجغرافية 
القانون 
اللغة الأنكليزية 
الأخبار 
الإعلام 
مكتبة الصور 
أقلام بمختلف الألوان 
إضاءات
مفتاح
أجوبة الإستفتاءات الشرعية
وثائقيات
تاريخ الرياضيات
الرياضيات في الحضارات المختلفة
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات | Independent Vertex Set |
 1408
 07:43 مساءً
date: 16-1-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
Date: 14-2-2017
1524
Date: 31-12-2021
1193
Date: 5-1-2022
1444
|
An independent vertex set of a graph 
is a subset of the vertices such that no two vertices in the subset represent an edge of 
. The figure above shows independent sets consisting of two subsets for a number of graphs (the wheel graph 
, utility graph 
, Petersen graph, and Frucht graph).
Any independent vertex set is an irredundant set (Burger et al. 1997, Mynhardt and Roux 2020).
The polynomial whose coefficients give the number of independent vertex sets of each cardinality in a graph 
is known as its independence polynomial.
A set of vertices is an independent vertex set iff its complement forms a vertex cover (Skiena 1990, p. 218). The counts of vertex covers and independent vertex sets in a graph are therefore the same.
The empty set is trivially an independent vertex set since it contains no vertices, and therefore no edge endpoints.
A maximum independent vertex set is an independent vertex set of a graph containing the largest possible number of vertices for the given graph, and the cardinality of this set is called the independence number of the graph.
An independent vertex set that cannot be enlarged to another independent vertex set by adding a vertex is called a maximal independent vertex set.
In the Wolfram Language, the command FindIndependentVertexSet[g][[1]] can be used to find a maximum independent vertex set, and FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All] to find all maximum independent vertex sets. Similarly, FindIndependentVertexSet[g, Infinity] can be used to find a maximal independent vertex set, and FindIndependentVertexSet[g, Infinity, All] to find all independent vertex sets. To find all independent vertex sets in the Wolfram Language, enumerate all vertex subsets 
and select those for which IndependentVertexSetQ[g, s] is true.
Independent vertex set counts for some families of graphs are summarized in the following table.
| graph family | OEIS | number independent vertex sets |
antiprism graph for  |
A000000 | X, X, 10, 21, 46, 98, 211, 453, 973, 2090, ... |
 bishop graph |
A201862 | X, 9, 70, 729, 9918, 167281, ... |
 black bishop graph |
A000000 | X, X, X, 27, 114, 409, 2066, ... |
 -folded cube graph |
A000000 | X, 3, 5, 31, 393, ... |
grid graph  for  |
A006506 | X, 7, 63, 1234, 55447, 5598861, ... |
grid graph  for  |
A000000 | X, 35, 70633, ... |
 -halved cube graph |
A000000 | 2, 3, 5, 13, 57, ... |
 -Hanoi graph |
A000000 | 4, 52, 108144, ... |
hypercube graph  |
A027624 | 3, 7, 35, 743, 254475, 19768832143, ... |
 king graph |
A063443 | X, 5, 35, 314, 6427, ... |
 knight graph |
A141243 | X, 16, 94, 1365, 55213, ... |
 -Möbius ladder |
A182143 | X, X, 15, 33, 83, 197, 479, 1153, 2787, ... |
 -Mycielski graph |
A000000 | 2, 3, 11, 103, 7407, ... |
odd graph  |
A000000 | 2, 4, 76, ... |
prism graph  for  |
A051927 | X, X, 13, 35, 81, 199, 477, 1155, 2785, ... |
 queen graph |
A000000 | 2, 5, 18, 87, 462, ... |
 rook graph |
A002720 | 2, 7, 34, 209, 1546, 13327, 130922, ... |
 -Sierpiński sieve graph |
A000000 | 4, 14, 440, ... |
 -triangular graph |
A000000 | X, 2, 4, 10, 26, 76, 232, 764, ... |
 -web graph for  |
A000000 | X, X, 68, 304, 1232, 5168, 21408, ... |
 white bishop graph |
A000000 | X, X, X, 27, 87, 409, 1657, ... |
Many families of graphs have simple closed forms for counts of independent vertex sets, as summarized in the following table. Here, 
is a Fibonacci number, 
is a Lucas number, 
is a Laguerre polynomial, 
is the golden ratio, and 
, 
, 
are the roots of 
.
| graph family | number of independent vertex sets |
| Andrásfai graph |  |
| antiprism graph |  |
book graph  |
 |
cocktail party graph  |
 |
complete bipartite graph  |
 |
complete graph  |
 |
complete tripartite graph  |
 |
 -crossed prism graph |
![2^(-n)[(7-sqrt(21))^n+(7+sqrt(21))^n]](https://mathworld.wolfram.com/images/equations/IndependentVertexSet/Inline53.svg) |
cycle graph  |
 |
empty graph  |
 |
| gear graph |  |
| helm graph |  |
| ladder graph | ![1/2[(1-sqrt(2))^(n+1)+(1+sqrt(2))^(n+1)]](https://mathworld.wolfram.com/images/equations/IndependentVertexSet/Inline60.svg) |
ladder rung graph  |
 |
Möbius ladder  |
 |
| pan graph |  |
path graph  |
 |
prism graph  |
 |
 rook graph |
 |
star graph  |
 |
| sun graph |  |
sunlet graph  |
 |
wheel graph  |
|
Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.
Gallai, T. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2, 133-138, 1959.
Hochbaum, D. S. (Ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing, p. 125, 1997.
Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.
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.
|
|
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|
