Maximum Independent Edge Set

An independent edge set, also called a matching, of a graph  is a subset of the edges such that no two edges in the subset share a vertex in . A maximum independent edge set an independent edge set containing the largest possible number of edges among all independent edge sets for a given graph.

A maximum independent edge set, also called a maximum matching, of a graph can be computed in the Wolfram Language with FindIndependentEdgeSet[g].

The size of a maximum independent edge set is known as the matching number or edge independence number.

A maximum independent edge set is not equivalent to a maximal independent edge set, which is simply an independent edge set that cannot be extended to a larger independent edge set. Every maximum independent edge set is also a maximal independent edge set, but the converse is not true.

Given an edge cover of a graph, all edges not in the cover define an independent set (Skiena 1990, p. 218). Gallai (1959) showed that the size of the minimum edge cover plus the size of the maximum independent edge set equals the number of vertices of a graph.

The blossom algorithm can be used to find a maximum independent edge set in a general graph, while the simpler Hungarian maximum matching algorithm can be used for bipartite graphs.

---

REFERENCES

Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.

Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial Optimization. New York: Wiley, 1998.

Hopcroft, J. and Karp, R. "An  Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.

Pemmaraju, S. and Skiena, S. "Maximum Independent Set." §7.5.3 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. 

Cambridge, England: Cambridge University Press, p. 318, 2003.

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.

Zwick, U. "Lecture Notes on: Maximum Matching in Bipartite and Non-Bipartite Graphs." http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. 2009.

اخر الاخبار

اخبار العتبة العباسية المقدسة

مجموعة العميد التربوية تعقد اجتماعًا لمناقشة الاستعدادات الخاصة بالموسم التدريبي الصيفي

قسم الإعلام ينظم ورشة تدريبية حول تطبيق (إعلامي) لعدد من منتسبي قسم حفظ النظام

قسم الشؤون الخدمية ينفذ حملة لتنظيف الشوارع المحيطة بصحن مرقد أبي الفضل العباس (عليه السلام)

وفد العتبة العباسية المقدسة يزور شعبة الإعداد البدني للاطّلاع على برنامج تأهيل المنتسبين الجدد

المزيد

الآخبار الصحية

ماذا يحدث إذا تناولنا الطعام مرة واحدة فقط في اليوم

اكتشاف عوامل خطر غير متوقعة لمرض الكبد الدهني

فيروس هانتا والسفينة الموبوءة.. تحديث من الصحة العالمية

طبيب يحسم الجدل السجائر الإلكترونية وعلاقتها بالسرطان

المزيد

الآخبار التكنلوجية

لأول مرة في الولايات المتحدة.. تشغيل مفاعل مصغر نووي يغذي الذكاء الاصطناعي بالطاقة

الكشف عن تفاصيل أول عملية ناجحة لاستعادة انتاج الحيوانات المنوية

أطلس يكشف خفايا الجسم البشري بدقة أرفع بـ50 مرة من شعر الإنسان

المتحف المصري الكبير يتحول إلى "أيقونة خضراء" بدعم ياباني

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength