Application Of Minimal Spanning Tree Search Algorithms To The Resolution Of Graph Problems: Case Of Salting And Snow Removal Of The Road Network Of The City Of Tiaret

Résumé: The main objective of this study is to treat a primordial subject of the optimization of graph and network problems, namely the problem of finding the spanning tree of minimum weight, which consists of identifying and determining the tree which connects all vertices of a graph using a set of edges whose cost is minimal. Through this research study we address the problem of salting and snow removal from the road network of the city of Tiaret during winter by the municipal authorities and services. Our mission is to determine a partial road network (sub-network) from the initial road network of the town of Tiaret, which will have to be salted and cleared of snow by these authorities and services. The application of graph theory techniques for modeling the problem, and the use of the main search algorithms for the minimum weight spanning tree, allowed the study to propose the optimal subnetwork which contains the main roads of the road network of the city of Tiaret, to salt and clear snow at the lowest possible cost. الهدف الرئيسي من هذه الدراسة هو معالجة موضوع أساسي يتعلق بأمثلية مسائل نظرية البيان والشبكات، وهي مشكلة البحث عن الشجرة الممتدة ذات الوزن الأدنى، التي تقوم على تحديد الشجرة التي تربط جميع قمم بيان باستخدام مجموعة من الاحرف بأقل تكلفة. من خلال هذه الدراسة البحثية نتناول مشكلة التمليح وإزالة الثلوج من شبكة الطرق لمدينة تيارت خلال فترة الشتاء من قبل السلطات و المصالح البلدية. مهمتنا هو تحديد شبكة طرق جزئية و فرعية من شبكة الطرق الأولية لمدينة تيارت، و التي سيتعين تمليحها و إزالة الثلوج منها . إن تطبيق كل من تقنيات نظرية البيان لنمذجة المشكلة، و استخدام الخوارزميات الرئيسية للبحث عن الشجرة الممتدة ذات الوزن الأدنى، أتاح للدراسة اقتراح الشبكة الفرعية و الجزئية المثلى التي تتضمن الطرق الاساسية لشبكة طرق مدينة تيارت، الواجب على السلطات و المصالح البلدية تمليحها وإزالة الثلوج منها بأقل تكلفة ممكنة.

Publié dans la revue: مجلة اقتصاديات شمال افريقيا