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

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

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية
عمليات خدمة الكرنب
2024-11-28
الأدعية الدينية وأثرها على الجنين
2024-11-28
التعريف بالتفكير الإبداعي / الدرس الثاني
2024-11-28
التعريف بالتفكير الإبداعي / الدرس الأول
2024-11-28
الكرنب (الملفوف) Cabbage (من الزراعة الى الحصاد)
2024-11-28
العلاقات مع أهل الكتاب
2024-11-28


Matching  
  
1856   07:18 مساءً   date: 8-5-2022
Author : Lovász, L. and Plummer, M. D
Book or Source : Matching Theory. Amsterdam, Netherlands: North-Holland, 1986.
Page and Part : ...


Read More
Date: 13-4-2022 1694
Date: 1-4-2022 2123
Date: 1-5-2022 1752

Matching

 

A matching, also called an independent edge set, on a graph G is a set of edges of G such that no two sets share a vertex in common.

It is not possible for a matching on a graph with n nodes to exceed n/2 edges. When a matching with n/2 edges exists, it is called a perfect matching. When a matching exists that leaves a single vertex unmatched, it is called a near-perfect matching.

While not all graphs have perfect matchings, a largest matching (commonly known as a maximum matching or maximum independent edge set) exists for every graph. The size of this maximum matching is called the matching number of G and is denoted nu(G).

The number of matchings in a graph is sometimes called the Hosoya index.

A maximal independent edge set, which is different from a maximum independent edge set, is a matching that cannot be enlarged by simply adding an edge. Such matchings are easy to compute, but are not necessarily maximum independent edge sets. A maximal independent edge set on a general graph can be found using MaximalMatching[g] in the Wolfram Language package Combinatorica` , but not using a using built-in function in the Wolfram Language.

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. A maximum independent edge set can be computed in the Wolfram Language using FindIndependentEdgeSet[g].

Let the number of distinct k-matchings of a graph with n vertices be denoted Phi_k. Then Phi_0(G)=1 (since the empty set consisting of no edges is always a 0-matching) and Phi_1(G)=m, where m is the edge count of G.

The matching polynomial is defined by

 mu(x)=sum_(k=0)^(nu(G))(-1)^kPhi_kx^(n-2k)

and the matching-generating polynomial by

 M(x)=sum_(k=0)^(nu(G))Phi_kx^k.

The numbers of distinct k-matchings for various specials classes of graphs are summarized in the following table, where n! denotes a factorial, n!! is a double factorial, (n; k) is a binomial coefficient, and delta_k is the discrete delta function.

graph Phi_k
complete graph K_n (n!)/((2k)!!(n-2k)!)
complete bipartite graph K_(n,n) k!(n; k)^2
cycle graph C_n n/(n-k)(n-k; k)
empty graph K^__n delta_k
path graph P_n (n-k; k)

REFERENCES

Hopcroft, J. and Karp, R. "An n^(5/2) Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.

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

Pemmaraju, S. and Skiena, S. "Matching." §8.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 343-351, 2003.

Skiena, S. "Matching." §6.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 240-246, 1990.

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




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


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

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