خوارزميتان فعالتان لحساب دائم مصفوفة باستخدام نظرية البيانات الموجهة

Abstract

نظراً لأهمية دائم مصفوفة في العديد من التطبيقات مثل التوافقيات و نظرية البيان و إيجاد المعاملات الواحدية في بيان موجه و حساب حلقات هاملتون في بيان و نظرية التلوين والإحصاء والاحتمالات وغيرها، دأب الباحثون بالبحث عن صيغ تحليلية لحساب القيمة الدقيقة لدائم مصفوفة إلا أن حساب هذه الصيغ صعب للغاية و ذلك نظرا للكلفة الحسابية العالية لدى تطبيقها عند حساب دائم مصفوفة. و كما هو الحال في المحدد فإنه لا توجد طرائق فعالة لحساب دائم مصفوفة حتى وإن تركز تطبيق هذه الطرائق على مصفوفات (0,1) والتي تلعب دورا هاما جدا في نظرية البيان و الأشجار و لذلك لا تزال المسألة مفتوحة مما يجعلها مجالا هاما و أرضية خصبة للبحث. لهذه الأسباب، نصف في هذه المقالة، خوارزميتين جديدتين فعالتين لإيجاد دائم مصفوفة مربعة من المرتبة .  تعتمد هاتان الخوارزميتان على البيان الموجه الموافق للمصفوفة . أخيرا، نبين من خلال بعض تجارب المحاكاة العددية فعالية كل من الخوارزميتين بلغة البرمجة C++ و نقارن النتائج الحاصلة بخوارزمية باكس و فرانكلين.

We describe in this paper two efficient algorithms for finding the permanent of a square  matrix  of order . These algorithms depend on the digraph corresponding to the matrix . Because of the importance of matrices permanents in several applications such as Combinatorics, Graph theory, Statistics and Probability, the researchers started to find closed and analytical forms for computing the permanent of matrix. But computing the permanent is a difficult problem. For these reasons, in this paper, we describe two efficient algorithms for finding the exact value of the permanent of a square matrix  of order . These two algorithms depend on the digraph corresponding to the matrix . Finally, some numerical experiments are carried out on an Compatible PC with C++ codes to illustrate the efficiency of the proposed algorithms. The obtained results have been compared with those obtained by the algorithm proposed by Bax and Franklin.