Contribution À L'étude De La Classe Des Graphes De Cercles Tangents

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

Ce manuscrit s’est porté sur l’étude d’une classe de graphes d’intersection et l’ordre correspondant introduit par ABBAS et VINCKE (۱۹۹٤), appelée graphe (ordre ) de cercles tangents. Un graphenon orienté est appelé graphe de cercles tangents si ses sommets peuvent être mis en correspondance biunivoque avec un ensemble de cercles tangents à une droite supposée horizontale de telle manière à ce que deux sommets soient relies par une arête de si et seulement si leurs cercles correspondants intersectés. Ces graphes sont une représentation d’un modèle d’une structure d’ordre dont la relation de préférence stricte n’est pas nécessairement transitive. On a rappelé ses propriétés et les rapports avec d'autres graphes (ordre s) bien connus. Notamment, on a montré l’inclusion de deux sous-classes de graphes d’intervalles dans les graphes de cercles tangents : les graphes d’arborescence comparabilité et les graphes à seuil, comme on a aussi proposé une méthode de représentation des graphes d’arbres par des cercles tangents. Ainsi, on a discuté les problèmes d’optimisations dans cette catégorie de graphe plus exactement le problème de coloration et le problème de partition minimum en cliques dans les graphes de cercles tangents transitifs.

روابط وملفات

التعريف والنوع

رقم الوثيقة

f24bd015-9f22-4ab4-bd4f-cc5926a41fdc

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل ماجيستير

نوع الملف

word

أسماء الملفات

1378703_1.docx, 1378703_2.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":"Karima Guellali","title_ar":"اعداد","title_en":"Preparation"},{"name_ar":"منصف عباس","title_ar":"اشراف","title_en":"Supervision"}]

اللغة

French

المصدر والدورية

اسم المصدر

Contribution À L'étude De La Classe Des Graphes De Cercles Tangents

المحتوى والصفحات

عدد الصفحات

0

ترجمة الملخص

This manuscript went on the study of a class of intersection graphs and the order corresponding introduced by ABBAS and VINCKE (۱۹۹٤), called tangent circles graph (order). A non-directed graph is called tangent circles graph if its vertex can be put one by one in correspondence with a set of tangent circles on a presumably horizontal line in such manner so that two vertex are connected by an edge of if and only if their corresponding circles are intersected. These graphs are a representation of a model of an order structure whose strict preferably relation is not necessarily transitive. One pointed out its properties and the relationship with other graphs (orders) well-known. In particular, we showed the inclusion of two subclasses of interval graphs in the tangent circles graphs: the arborescence comparability graphs and the threshold graphs, as we also proposed a method of acyclic graphs representation by tangent circles. Thus, we discussed the optimizations problems in this category of graph more exactly the problem of coloring and the problem of minimum partition clique in the transitive tangent circles graphs.

كلمات الباحثين

arborescence comparability graph, arbre, clique partition, coloration, graphe à seuil, graphe d’arbore scence comparabilité, graphe de cercles tangents, ordre de cercles tangents, partition en cliques, tangent circle graph, tangent circle order, threshold graph, tree

إشراف وإعداد

الإشراف

منصف عباس

الإعداد

Karima Guellali

الاقتباسات الببليوغرافية