DOI: https://doi.org/10.47974/jdmsc-2572
تاريخ النشر: 2026-01-01
المؤلف: T. M. Rajalaxmi وآخرون
الموضوع الرئيسي: نظرية الرسوم البيانية وتطبيقاتها
نظرة عامة
في نظرية الرسوم البيانية، تعتبر المؤشرات الطوبوغرافية من الثوابت الأساسية التي تصف بنية الرسوم البيانية. من بين هذه المؤشرات، يعتبر مؤشر وينر ذا أهمية خاصة لأنه يقيس مجموع جميع المسافات الأقصر داخل طوبوغرافيا الرسم البياني. منذ تقديمه في منتصف القرن العشرين، وجد مؤشر وينر تطبيقات في مجالات متنوعة مثل نظرية الشبكات، نظرية الرسوم البيانية الكيميائية، تحليل الشبكات الاجتماعية، والتركيبات.
تركز هذه الدراسة على مؤشر وينر لطوبوغرافيا شبكة C₆C₄، التي تتكون من ربط دورات من الدرجة 6 (C₆) والدرجة 4 (C₄) في تكوين يشبه الشبكة. يستخرج المؤلفون صيغًا فريدة لحساب مؤشر وينر لهذه الشبكات C₆C₄، مستفيدين من طول الأسلاك لتسهيل هذا التحليل. تساهم هذه النتائج في فهم أعمق للخصائص الهيكلية لترتيبات الرسوم البيانية المعقدة.
مقدمة
تؤكد مقدمة هذه الورقة على أهمية نظرية الرسوم البيانية كأداة متعددة الاستخدامات عبر مختلف التخصصات العلمية، لا سيما في نمذجة الهياكل الجزيئية في الكيمياء. تبرز مؤشر وينر، وهو مؤشر طوبوغرافي اقترحه هارولد وينر في عام 1947، والذي يقيس مجموع المسافات بين جميع أزواج الرؤوس في الرسم البياني. تم تطبيقه في البداية للتنبؤ بالخصائص الديناميكية الحرارية للألكانات، ومنذ ذلك الحين وجد مؤشر وينر تطبيقات أوسع في نظرية الشبكات والعلوم الحاسوبية، مما يساعد في تقييم كفاءة الاتصال في فئات مختلفة من الرسوم البيانية، بما في ذلك رسوم الطواحين وسلاسل البوليمينو.
تستكشف الورقة أيضًا طوبوغرافيا الشبكة، التي تدمج أنماط التبليط السداسي والمربع، مما يوفر مزايا في الاتصال ومرونة التوجيه مع تقليل المسافات الاتصالية. يتم وضع هذه البنية الهجينة كبديل متفوق لأنماط التبليط التقليدية، مثل الشبكات المربعة والشبكات السداسية، التي قد تقدم تحديات من حيث المسافات المتوسطة وتعقيد التنفيذ. يهدف المؤلفون إلى تحديد مؤشر وينر لطوبوغرافيا الشبكة، مؤكدين على إمكانيته في تعزيز تصميمات الشبكات القابلة للتوسع ومنخفضة الكمون. ستتناول الأقسام اللاحقة الأسس الرياضية لمؤشر وينر، وبناء طوبوغرافيا الشبكة، وآثار نتائجهم على الأبحاث المستقبلية.
نقاش
في هذا القسم، يتركز النقاش حول مؤشر وينر، وهو مقياس حاسم لتقييم كفاءة الاتصال في الرسوم البيانية، لا سيما في سياق طوبوغرافيا الشبكة. يقيس مؤشر وينر المسافة الإجمالية بين جميع أزواج الرؤوس، مما يجعله أداة مهمة لتقييم تكاليف الاتصال في الشبكات، بما في ذلك الهياكل الجزيئية والأجهزة التشفيرية. تبرز الورقة أن مؤشر وينر المنخفض يرتبط بمسارات اتصال أقصر، مما يعزز الأداء والأمان في تصميمات الأجهزة. يستكشف المؤلفون أيضًا تضمينات الرسوم البيانية، التي تسهل نشر الخوارزميات المتوازية من خلال رسم المهام الحاسوبية بكفاءة عبر المعالجات، مما يقلل من تكاليف الاتصال.
توسع الدراسة الأبحاث السابقة من خلال التحقيق في مؤشر وينر لرسم بياني كامل مضمن داخل طوبوغرافيا الشبكة. تتميز طوبوغرافيا الشبكة بترابطها المنظم، وقطرها المعتدل، وخصائصها الأويلرية، مما يجعلها مناسبة للحوسبة المتوازية وأنظمة الاتصال المقاومة للأخطاء. يستخرج المؤلفون صيغًا لمؤشر وينر بناءً على طول الأسلاك للتضمين، مما يوضح كفاءته وقابليته للتوسع لتطبيقات في شبكات الاتصال. يختتمون بالإشارة إلى الإمكانية للبحث المستقبلي لاستكشاف مؤشر وينر في الهياكل الرسومية الهجينة وسلوكيات الشبكة الديناميكية، مع تحديد التحدي المتمثل في تحديد مؤشر وينر لطوبوغرافيا الشبكة التعسفية كمشكلة مفتوحة.
DOI: https://doi.org/10.47974/jdmsc-2572
Publication Date: 2026-01-01
Author(s): T. M. Rajalaxmi et al.
Primary Topic: Graph theory and applications
Overview
In graph theory, topological indices serve as crucial graph invariants that characterize the structure of graphs. Among these, the Wiener index is particularly significant as it quantifies the sum of all shortest-path distances within a graph’s topology. Since its introduction in the mid-20th century, the Wiener index has found applications in diverse fields such as network theory, chemical graph theory, social network analysis, and combinatorics.
This study focuses on the Wiener index of the C₆C₄ mesh topology, which is formed by interconnecting cycles of order 6 (C₆) and order 4 (C₄) in a mesh-like configuration. The authors derive unique formulas for calculating the Wiener index of these C₆C₄ meshes, leveraging the wirelength of their respective embeddings to facilitate this analysis. These findings contribute to a deeper understanding of the structural properties of complex graph arrangements.
Introduction
The introduction of this paper emphasizes the significance of graph theory as a versatile tool across various scientific disciplines, particularly in modeling molecular structures in chemistry. It highlights the Wiener index, a topological index proposed by Harold Wiener in 1947, which quantifies the sum of distances between all pairs of vertices in a graph. Initially applied to predict thermodynamic properties of alkanes, the Wiener index has since found broader applications in network theory and computational science, aiding in the assessment of connectivity efficiency in various graph classes, including windmill graphs and polyomino chains.
The paper further explores the mesh topology, which integrates hexagonal and square tiling patterns, offering advantages in connectivity and routing flexibility while minimizing communication distances. This hybrid structure is positioned as a superior alternative to traditional tiling patterns, such as square grids and hexagonal meshes, which may present challenges in terms of average distances and implementation complexity. The authors aim to determine the Wiener index for the mesh topology, asserting its potential for enhancing scalable and low-latency network designs. Subsequent sections will delve into the mathematical foundations of the Wiener index, the construction of the mesh topology, and the implications of their findings for future research.
Discussion
In this section, the discussion centers on the Wiener index, a crucial metric for evaluating communication efficiency in graphs, particularly in the context of mesh topologies. The Wiener index quantifies the aggregate distance between all pairs of vertices, making it instrumental for assessing communication costs in networks, including molecular structures and cryptographic hardware. The paper highlights that a lower Wiener index correlates with shorter communication paths, enhancing performance and security in hardware designs. The authors also explore graph embeddings, which facilitate parallel algorithm deployment by efficiently mapping computational tasks across processors, thereby reducing communication costs.
The study extends previous research by investigating the Wiener index of a complete graph embedded within a mesh topology. The mesh topology is characterized by its structured interconnection, moderate diameter, and Eulerian properties, making it suitable for parallel computing and fault-tolerant communication systems. The authors derive formulas for the Wiener index based on the wirelength of the embedding, demonstrating its efficiency and scalability for applications in communication networks. They conclude by noting the potential for future research to explore the Wiener index in hybrid graph structures and dynamic mesh behaviors, while also identifying the challenge of determining the Wiener index for arbitrary mesh topologies as an open problem.
