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

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

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية
القيمة الغذائية للثوم Garlic
2024-11-20
العيوب الفسيولوجية التي تصيب الثوم
2024-11-20
التربة المناسبة لزراعة الثوم
2024-11-20
البنجر (الشوندر) Garden Beet (من الزراعة الى الحصاد)
2024-11-20
الصحافة العسكرية ووظائفها
2024-11-19
الصحافة العسكرية
2024-11-19

تعريف الحق
24-3-2016
صلاة ذات الرقاع
20-8-2017
ثـقافـة المـنظمة Organization Culture (لمحـة تاريخية عن نشأة دراسـات الثقافـة التنظيميـة)
7-11-2021
Lytic Development Is Divided into Two Periods
5-6-2021
The real numbers: Stevin to Hilbert
11-10-2015
نظام الحكم والسياسة عند العرب قبل الاسلام
1-2-2017

Perfect Matching  
  
1122   03:46 مساءً   date: 10-5-2022
Author : Andersen, L. D
Book or Source : "Factorizations of Graphs." §VII.5 in CRC Handbook of Combinatorial Designs, 2nd ed. Boca Raton, FL: CRC Press
Page and Part : ...


Read More
Date: 19-4-2022 1370
Date: 27-3-2022 1249
Date: 28-7-2016 1221

Perfect Matching

A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching. A perfect matching is therefore a matching containing n/2 edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices. A perfect matching is sometimes called a complete matching or 1-factor.

PerfectMatching

The nine perfect matchings of the cubical graph are illustrated above.

Note that rather confusingly, the class of graphs known as perfect graphs are distinct from the class of graphs with perfect matchings.

Precomputed graphs having a perfect matching return True for GraphData[g"PerfectMatching"] in the Wolfram Language.

While not all graphs have a perfect matching, all graphs do have a maximum independent edge set (i.e., a maximum matching; Skiena 1990, p. 240; Pemmaraju and Skiena 2003, pp. 29 and 343). Furthermore, every perfect matching is a maximum independent edge set. A graph either has the same number of perfect matchings as maximum matchings (for a perfect matching graph) or else no perfect matchings (for a no perfect matching graph).

A graph G has a perfect matching iff its matching number nu(G) satisfies

 |G|=2nu(G),

where |G|=n is the vertex count of G.

The numbers of simple graphs on n=2, 4, 6, ... vertices having a perfect matching are 1, 6, 101, 10413, ..., (OEIS A218462), and the corresponding numbers of connected simple graphs are 1, 5, 95, 10297, ... (OEIS A218463).

NoPerfectMatchingGraph

The graph illustrated above is 16-node graph with no perfect matching that is implemented in the Wolfram Language as GraphData["NoPerfectMatchingGraph"].

Every connected vertex-transitive graph on an even number of vertices has a perfect matching, and each vertex in a connected vertex-transitive graph on an odd number of vertices is missed by a matching that covers all remaining vertices (Godsil and Royle 2001, p. 43; i.e., it has a near-perfect matching).

Every claw-free connected graph with an even number of vertices has a perfect matching (Sumner 1974, Las Vergnas 1975).

Petersen's theorem states that every cubic graph with no bridges has a perfect matching (Petersen 1891; Skiena 1990, p. 244). In fact, this theorem can be extended to read, "every cubic graph with 0, 1, or 2 bridges has a perfect matching."

A result that partially follows from Tutte's theorem states that a graph G=(V,E) (where V is the vertex set and E is the edge set) has no perfect matching iff there is a set S subset= V whose removal results in more odd-sized components than |S| (the cardinality of S; Tutte 1947; Pemmaraju and Skiena 2003, p. 344).


REFERENCES

Andersen, L. D. "Factorizations of Graphs." §VII.5 in CRC Handbook of Combinatorial Designs, 2nd ed. Boca Raton, FL: CRC Press, pp. 740-755, 2007.

Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.

Faudree, R.; Flandrin, E.; and Ryjáček, Z. "Claw-Free Graphs--A Survey." Disc. Math. 164, 87-147, 1997.

Las Vergnas, M. "A Note on Matchings in Graphs." Cahiers du Centre d'Études de Recherche Opér. 17, 257-260, 1975.

Lovász, L. and Plummer, M. D. Matching Theory. Amsterdam, Netherlands: Elsevier, 1986.

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.Petersen, J. "Die Theorie der Regulären Graphen." Acta Math. 15, 193-200, 1891.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Sloane, N. J. A. Sequences A218462 and A218463.Sumner, D. P. "Graphs with 1-Factors." Proc. Amer. Math. Soc. 42, 8-12, 1974.

Tutte, W. T. "The Factorization of Linear Graphs." J. London Math. Soc. 22, 107-111, 1947.

Wallis, W. D. One-Factorizations. Dordrecht, Netherlands: Kluwer, 1997.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 107-108 and 136-145, 2000.




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


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

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