A matching in a graph is a set of independent edges. That is, it is a set of edges in which no pair shares a vertex. Given a matching M in a graph G, the vertices belonging to the edges of M are said to be saturated by M (or M-saturated). The other vertices are M-unsaturated.

Consider the graph G shown in Figure 1.1. An example of a matching in G is M₁ = {ab, ce, df}. M₂ = {cd, ab} is also a matching, and so is M₃ = {df}.

We can see that a, b, c, d are M₂-saturated and e, f,and g are M₂-unsaturated. The onlyM₁-unsaturated vertex is g.

                  FIGURE 1.1. The matching M₁.

If a matching M saturates every vertex of G,then M is said to be a perfect matching. In Figure 1.104, G1 has a perfect matching, namely {ab,ch,de,fg}.

None of G2, G3,and G4 has a perfect matching. Why is this? We will talk more about perfect matchings in Sectionof Perfect Matchings.

A maximum matching in a graph is a matching that has the largest possible cardinality. A maximal matching is a matching that cannot be enlarged by the

                                     FIGURE 1.2. Only G1 has a perfect matching

addition of any edge. In Figure 1.3, M₁ = {ae,bf,cd,gh} is a maximum matching (since at most one of gh, gi,and gj can be in any matching). The matching  M2 = {dg, af, bc} is maximal, but not maximum.

                                 FIGURE 1.3.

Combinatorics and Graph Theory, Second Edition, John M. Harris • Jeffry L. Hirst • Michael J. Mossinghoff,2000,page(101-104)

اخر الاخبار

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

قسم شؤون المعارف يحصي منجزاته العلمية لعام 2025

شعبة الخطابة الحسينية النسوية تقيم برنامج مراقي العلا التوعوي لطالبات مدارس كربلاء

معهد القرآن الكريم النسوي يقيم مجلس عزاء بذكرى وفاة السيدة زينب (عليها السلام)

قسم الشؤون الفكرية يقدم محاضرة توعوية لمجموعة من طلبة مدارس بغداد

المزيد

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

طبيب يكشف أفضل مكمل غذائي لتحسين المزاج ودعم الصحة النفسية

دراسة جديدة تكشف أضرار الأطعمة الجاهزة على القلب ؟

6 أطعمة طبيعية تهدئ الزكام دون أدوية.. تعرف عليهم

ماذا يحدث لأعراض الزكام عند تناول الثوم بانتظام؟

المزيد

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

ابتكار ثوري في بطاريات السيارات الكهربائية.. سعة أعلى 4 مرات

ماذا يحدث لجسمك عند شرب الماء الساخن يوميا؟

7 فوائد "خفية" لشرب شاي الكركديه كل يوم

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

المزيد

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

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