وقت التغطية

في الرياضيات، يُعرف زمن التغطية لسلسلة ماركوف محدودة بأنه عدد الخطوات التي تقطعها السلسلة، بدءًا من حالة ابتدائية معينة، حتى الخطوة الأولى التي يتم فيها الوصول إلى جميع الحالات. وهو متغير عشوائي يعتمد على سلسلة ماركوف واختيار الحالة الابتدائية. أما زمن التغطية لرسم بياني متصل غير موجه، فهو زمن التغطية لسلسلة ماركوف التي تسلك مسارًا عشوائيًا على الرسم البياني، حيث تنتقل في كل خطوة من رأس إلى جار عشوائي منتظم لهذا الرأس. ^{[ 1 ]}

لقد تمت دراسة أوقات تغطية الرسوم البيانية على نطاق واسع في علوم الحاسوب النظرية لتطبيقات تتضمن تعقيد الاتصال من الدرجة الأولى ، ونظرية الرسوم البيانية الجبرية ، ودراسة الرسوم البيانية الموسعة ، ونمذجة تقنية شبكات الحاسوب Token Ring . ^{[ 1 ]}

يمكن تفسير مشكلة جامع القسائم ، وهي مشكلة كلاسيكية في نظرية الاحتمالات ، على أنها نتيجة لمتوسط ​​وقت تغطية الرسم البياني الكامل.${\displaystyle K_{n}}$يكون${\displaystyle n\ln n(1+o(1))}$لكل شخص آخر${\displaystyle n}$في الرسم البياني ذي الرؤوس n، يكون وقت التغطية المتوقع على الأقل مساوياً لهذه الصيغة. ^{[ 2 ]} أي${\displaystyle n}$يحتوي الرسم البياني الموسع المنتظم للرؤوس أيضًا على وقت تغطية متوقع${\displaystyle \Theta (n\log n)}$من أي رأس بداية، وبشكل أعم، فإن زمن تغطية أي رسم بياني منتظم هو$${\displaystyle O\left({\frac {n\log n}{1-\lambda _{2}}}\right),}$$أين${\displaystyle \lambda _{2}}$هي ثاني أكبر قيمة ذاتية للرسم البياني، مُعَيَّرة بحيث تكون أكبر قيمة ذاتية هي واحد. ^{[ 1 ]} لأي قيمة ذاتية عشوائية${\displaystyle n}$في الرسوم البيانية ذات n رأس، من أي رأس بداية، يكون وقت التغطية على الأكثر$${\displaystyle \left({\frac {4}{27}}+o(1)\right)n^{3},}$$وتوجد رسوم بيانية يكون زمن تغطيتها المتوقع بهذا القدر. ^{[ 3 ]} في الرسوم البيانية المستوية ، يكون زمن التغطية المتوقع هو${\displaystyle \Omega (n\log ^{2}n)}$و${\displaystyle O(n^{2})}$[ ^{4 ]​}

• زمن الوصول ، عدد الخطوات اللازمة للوصول إلى مجموعة من الحالات لأول مرة