منتديات جواهر ستار التعليمية
أهلا وسهلا بك زائرنا الكريم ، في منتديات جواهر ستار التعليميه
المرجو منك أن تقوم بتسجـيل الدخول لتقوم بالمشاركة معنا. إن لم يكن لـديك حساب بعـد ، نتشرف بدعوتك لإنشائه بالتسجيل لديـنا . سنكون سعـداء جدا بانضمامك الي اسرة المنتدى

مع تحيات الإدارة



أهلا وسهلا بك إلى منتديات جواهر ستار التعليمية.
أهلا وسهلا بك زائرنا الكريم، إذا كانت هذه زيارتك الأولى للمنتدى، فيرجى التكرم بزيارة صفحة التعليمـــات، بالضغط هنا.كما يشرفنا أن تقوم بالتسجيل بالضغط هنا إذا رغبت بالمشاركة في المنتدى، أما إذا رغبت بقراءة المواضيع والإطلاع فتفضل بزيارة القسم الذي ترغب أدناه.

الرئيسيةموقع دراسة الراس .و .جالتسجيلدخول
!~ آخـر 10 مواضيع ~!
شارك اصدقائك شارك اصدقائك حلول تمارين الكتاب المدرسي للغة الفرنسية للسنة الرابعة متوسط
شارك اصدقائك شارك اصدقائك واقع ظروف العــــمل والحوادث المـــهنية بالمؤسسات الجزائرية
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت جيولوجيا لغات للثالث الثانوي 2017.
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت ايطالي للثالث الثانوي 2017
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت الماني للثالث الثانوي 2017.
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت اسباني للثالث الثانوي 2017.
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت لغة عربية للثالث الثانوي 2017.
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت فرنسي للثالث الثانوي 2017.
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت الاحياء لغات للثالث الثانوي 2017.
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت الكيمياء لغات للثالث الثانوي 2017.
شارك اصدقائك شارك اصدقائك من الوزارة بوكليت الفيزياء لغات للثالث الثانوي 2017
شارك اصدقائك شارك اصدقائك اختبار شهر فيفري في مادة اللغة العربية السنة الثالثة ابتدائي
شارك اصدقائك شارك اصدقائك امتحان شهر جانفـــــــي في اللغـــــة العربيـــــــــــــــــة الثانية ابتدائي
شارك اصدقائك شارك اصدقائك الصف الثالثة ابتدائي(ب) اختبار شهر فيفري في اللغة العربية
شارك اصدقائك شارك اصدقائك اختبار الفصل الثاني في مادة اللغة س3
السبت 21 يناير - 19:33:58
الخميس 19 يناير - 15:16:27
الإثنين 16 يناير - 16:15:36
الإثنين 16 يناير - 16:09:12
الإثنين 16 يناير - 16:04:11
الإثنين 16 يناير - 15:59:14
الإثنين 16 يناير - 15:32:34
الإثنين 16 يناير - 15:26:37
الإثنين 16 يناير - 14:09:49
الإثنين 16 يناير - 14:02:49
الإثنين 16 يناير - 13:56:48
الأحد 15 يناير - 9:09:31
الأحد 15 يناير - 9:08:57
الأحد 15 يناير - 9:08:18
الأحد 15 يناير - 9:07:34
إضغط عليشارك اصدقائكاوشارك اصدقائك لمشاركة اصدقائك!



منتديات جواهر ستار التعليمية :: منتديات الجامعة و البحث العلمي :: منتديات الجامعة و البحث العلمي :: منتدى البحوث العلمية والأدبية و الخطابات و السير الذاتيه الجاهزه

شاطر

السبت 3 ديسمبر - 15:01:35
المشاركة رقم:
Admin
Admin


إحصائيةالعضو

عدد المساهمات : 15093
تاريخ التسجيل : 16/06/2009
http://www.berberjawahir.com/
مُساهمةموضوع: Les chaînes et les cycles


Les chaînes et les cycles


ـــــــــــــــــــــــــــــــــــــ

Les chaînes et les cycles

Une chaîne est une suite d'arêtes consécutives dans un graphe, un peu comme si on se promenait sur le graphe. On la désigne par les lettres des sommets qu'elle comporte.

Une chaîne simple est une chaîne qui ne passe pas deux fois par la même arête.

Un cycle est une chaîne qui commence et se termine au même sommet.

Un cycle simple est un cycle dans lequel chaque arête est utilisée une seule fois.

[size]

La distance entre deux sommets

La distance entre deux sommets est donnée par la longueur de la chaîne la plus courte les reliant.

Il existe souvent plusieurs chaînes pouvant lier deux sommets. Pour déterminer la distance entre les sommets, on choisit donc la chaîne dont la longueur est la plus petite.

La distance entre les sommets A et B s’écrit d(A,B).


La distance entre les sommets A et C sera exprimée ainsi :

d(A,C) = 2

La distance est de 2, car on doit franchir au minimum deux arêtes pour passer du sommet A au sommet C.

La longueur d'une chaîne

La longueur d’une chaîne est déterminée par le nombre d’arêtes qui sont parcourues dans une promenade. La même arête peut donc être répétée quand on donne la longueur d’une chaîne.
La longueur est toujours égale au nombre de sommets de la chaîne -1.
 
Longueur = 2

Longueur = 5

Longueur = 6
 

Les chaînes et les cycles eulériens

Une chaîne eulérienne est une chaîne qui parcourt toutes les arêtes d’un graphe connexe une et une seule fois.
 
On peut demander s’il est possible de parcourir tel trajet en n’empruntant jamais deux fois la même route :


On voit que c’est possible en partant de Trois-Rivières ou Drummondville, mais pas en partant de Québec ou Montréal. Exemple : (T-Q-D-T-M-D)
 
Pour qu’un graphe comporte une chaîne eulérienne, il faut qu’il possède exactement 2 sommets de degré impair. Ces sommets sont situés au début et à la fin de la chaîne.
 
Lorsque la chaîne eulérienne est fermée, on l’appellera cycle eulérien. C’est donc un cycle qui passe par toutes les arêtes et qui revient à son point de départ.
 
Le cycle eulérien exige que tous les sommets du graphe soient de degré pair.

 

ABCDECA est un cycle eulérien.
Il passe une seule fois par tous les sommets du graphe.

Les chaînes et les cycles hamiltoniens

Une chaîne ou cycle hamiltonien(ne) est une chaîne ou un cycle qui passe par tous les sommets d’un graphe connexe une et une seule fois. Les chaînes hamiltoniennes sont fréquemment utilisées pour résoudre des problèmes d’optimisation (par exemple, trouver le chemin le plus court. Le problème du voyageur en est un bon exemple, voir la référence plus bas).
 
Hormis par intuition ou par essais et erreurs, la seule règle que l’on connaisse pour déterminer la présence de cycles hamiltoniens dans un graphe connexe est la suivante.

Il y a un cycle hamiltonien dans tout graphe dont chaque sommet est relié à au moins la moitié des autres sommets.
 
Cette règle n’est pas restrictive, c’est-à-dire qu’on peut trouver des graphes qui ne répondent pas à cette condition et qui comportent néanmoins une chaîne hamiltonienne.
 

Chaîne hamiltonienne : FDEABCG
Cycle hamiltonien : FDEABCGF[/size]




الموضوعالأصلي : Les chaînes et les cycles // المصدر : منتديات جاهر ستار العليمية //الكاتب: berber


توقيع : berber



_________________






الــرد الســـريـع
..



الذين يشاهدون محتوى الموضوع الآن : 20 ( الأعضاء 3 والزوار 17)



تعليمات المشاركة
صلاحيات هذا المنتدى:
لاتستطيع الرد على المواضيع في هذا المنتدى

BB code is متاحة
كود [IMG] متاحة
كود HTML معطلة


ََ

مواضيع ذات صلة

منتديات جواهر ستار  التعليمية

↑ Grab this Headline Animator

Submit Your Site To The Web's Top 50 Search Engines for Free! share xml version="1.0" encoding="UTF-8"