خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين
تدرس هذه المقالة خوارزمية لإيجاد التماثل بين بيانين هاملتونيين G1 ، G2 تعتمد هذه الخوارزمية على تمثيل البيان وفقاً لمسار طويل. يعطي هذا التمثيل للبيان خواص مثل التوازي والتقاطع بين الأضلاع وتظهر هذه الصفات بشكل واضح في مصفوفة التجاور. وهناك خواص للمسارات الطويلة مثل: المسارات الطويلة المتراتبة وال...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Arabic |
| Published: |
Tishreen University
2018-12-01
|
| Series: | مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| Online Access: | http://www.journal.tishreen.edu.sy/index.php/bassnc/article/view/5294 |
| _version_ | 1797421959396458496 |
|---|---|
| author | جبران جبران صلاح محمد |
| author_facet | جبران جبران صلاح محمد |
| author_sort | جبران جبران |
| collection | DOAJ |
| description |
تدرس هذه المقالة خوارزمية لإيجاد التماثل بين بيانين هاملتونيين G1 ، G2 تعتمد هذه الخوارزمية على تمثيل البيان وفقاً لمسار طويل. يعطي هذا التمثيل للبيان خواص مثل التوازي والتقاطع بين الأضلاع وتظهر هذه الصفات بشكل واضح في مصفوفة التجاور. وهناك خواص للمسارات الطويلة مثل: المسارات الطويلة المتراتبة والمسارات الطويلة المتقاطعة وغير المتقاطعة. سنستخدم في خوارزميتنا هذه خوارزمية ويليم كوكي وباك-تشينغ لي( لإيجاد المسار الأطول) حيث سنقدم شرحاً مفصلاً لها قبل عرضها ضمن خوارزمية التماثل المنشودة. إن هذه الخوارزمية تدرس التماثل على بيانات هاملتون وتأتي أهمية هذه الخوارزمية من اختبار كشف بيانات هاملتون والذي ينص على أن كل البيانات التي تحقق العلاقة [1,2] هي بيانات لهاملتون أي أن بيانات هاملتون هي البيانات التي يكون فيها عدد الأضلاع كبيرا ً بالنسبة لعدد الرؤوس في البيان.
This paper explains a new algorithm for isomorphic graphs. The algorithm depends on William kocay and Pak-ching Li’s algorithm (for Finding a Long Path in a Graph ). The paper says that if we have two graphs represented according to a long path, in every one, we can find the isomorphism between them by using certain properties of edges and other properties of long paths. It discusses the concepts :Parallel edges, degree ordering long paths and intersected long paths. It also defines two operations on long paths called: replacement operation and injection operation, which give a long path from another one intersected with it .
|
| first_indexed | 2024-03-09T07:25:00Z |
| format | Article |
| id | doaj.art-6a4b04da1f3a4951a52da5d321372218 |
| institution | Directory Open Access Journal |
| issn | 2079-3057 2663-4252 |
| language | Arabic |
| last_indexed | 2024-03-09T07:25:00Z |
| publishDate | 2018-12-01 |
| publisher | Tishreen University |
| record_format | Article |
| series | مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| spelling | doaj.art-6a4b04da1f3a4951a52da5d3213722182023-12-03T07:06:29ZaraTishreen Universityمجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية2079-30572663-42522018-12-01263خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيينجبران جبرانصلاح محمد تدرس هذه المقالة خوارزمية لإيجاد التماثل بين بيانين هاملتونيين G1 ، G2 تعتمد هذه الخوارزمية على تمثيل البيان وفقاً لمسار طويل. يعطي هذا التمثيل للبيان خواص مثل التوازي والتقاطع بين الأضلاع وتظهر هذه الصفات بشكل واضح في مصفوفة التجاور. وهناك خواص للمسارات الطويلة مثل: المسارات الطويلة المتراتبة والمسارات الطويلة المتقاطعة وغير المتقاطعة. سنستخدم في خوارزميتنا هذه خوارزمية ويليم كوكي وباك-تشينغ لي( لإيجاد المسار الأطول) حيث سنقدم شرحاً مفصلاً لها قبل عرضها ضمن خوارزمية التماثل المنشودة. إن هذه الخوارزمية تدرس التماثل على بيانات هاملتون وتأتي أهمية هذه الخوارزمية من اختبار كشف بيانات هاملتون والذي ينص على أن كل البيانات التي تحقق العلاقة [1,2] هي بيانات لهاملتون أي أن بيانات هاملتون هي البيانات التي يكون فيها عدد الأضلاع كبيرا ً بالنسبة لعدد الرؤوس في البيان. This paper explains a new algorithm for isomorphic graphs. The algorithm depends on William kocay and Pak-ching Li’s algorithm (for Finding a Long Path in a Graph ). The paper says that if we have two graphs represented according to a long path, in every one, we can find the isomorphism between them by using certain properties of edges and other properties of long paths. It discusses the concepts :Parallel edges, degree ordering long paths and intersected long paths. It also defines two operations on long paths called: replacement operation and injection operation, which give a long path from another one intersected with it . http://www.journal.tishreen.edu.sy/index.php/bassnc/article/view/5294 |
| spellingShingle | جبران جبران صلاح محمد خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| title | خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين |
| title_full | خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين |
| title_fullStr | خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين |
| title_full_unstemmed | خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين |
| title_short | خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين |
| title_sort | خوارزمية لإيجاد التماثلisomorphism بين بيانين هاملتونيين |
| url | http://www.journal.tishreen.edu.sy/index.php/bassnc/article/view/5294 |
| work_keys_str_mv | AT jbrạnjbrạn kẖwạrzmyẗlạyjạdạltmạtẖlisomorphismbynbyạnynhạmltwnyyn AT ṣlạḥmḥmd kẖwạrzmyẗlạyjạdạltmạtẖlisomorphismbynbyạnynhạmltwnyyn |