خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين

Authors

  • جبران جبران
  • صلاح محمد

Abstract

تدرس هذه المقالة خوارزمية لإيجاد التماثل بين بيانين هاملتونيين 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 .

Downloads

Published

2018-12-09

How to Cite

1.
جبران ج, محمد ص. خوارزمية لإيجاد التماثلIsomorphism)) بين بيانين هاملتونيين. TUJ-BA [Internet]. 2018Dec.9 [cited 2024May7];26(3). Available from: https://journal.tishreen.edu.sy/index.php/bassnc/article/view/5294

Issue

Vol. 26 No. 3 (2004): العلوم الأساسية

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

The authors retain the copyright and grant the right to publish in the magazine for the first time with the transfer of the commercial right to the Tishreen University Journal -Basic Sciences Series  

 Under a CC BY- NC-SA 04 license that allows others to share the work with of the work's authorship and initial publication in this journal. Authors can use a copy of their articles in their scientific activity, and on their scientific websites, provided that the place of publication is indicted in Tishreen University Journal -Basic Sciences Series .  The Readers have the right to send, print and subscribe to the initial version of the article, and the title of Tishreen University Journal -Basic Sciences Series   Publisher

 

journal uses a CC BY-NC-SA license which mean

You are free to:

  • Adapt — remix, transform, and build upon the material
  •  
  • The licensor cannot revoke these freedoms as long as you follow the license terms.

 

  • Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • NonCommercial — You may not use the material for commercial purposes.
  • ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
  • No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.