CALM/arwiki huggingface dataset:
الترتيب الطوبولوجي للرسم البياني الموجه هو ترتيب رؤوسه في تسلسل ، بحيث يحدث رأس بداية الحافة لكل حافة في وقت أبكر في التسلسل من قمة نهاية الحافة. لا يمكن أن يحتوي الرسم البياني الذي يحتوي على ترتيب طوبولوجي على أي دورات ، لأنه يجب توجيه الحافة في الرأس الأول للدورة بطريقة خاطئة. لذلك ، كل رسم بياني بترتيب طوبولوجي لا دوري. على العكس من ذلك ، يحتوي كل رسم بياني لا دوري موجه على ترتيب طوبولوجي واحد على الأقل. لذلك ، يمكن استخدام هذه الخاصية كتعريف بديل للرسومات البيانية الحلقية الموجهة: فهي بالضبط الرسوم البيانية التي لها ترتيب طوبولوجي.
الخصائص الرياضية.
قابلية الوصول ، الإغلاق المتعدي ، والاختزال المتعدي
يمكن صياغة علاقة قابلية الوصول في أي رسم بياني لا دوري موجه كترتيب جزئي as على رؤوس DAG. في هذا الترتيب الجزئي ، يتم ترتيب رأسين u و v على شكل u ≤ v تمامًا عندما يكون هناك مسار موجه من u إلى v في DAG ؛ أي عندما يمكن الوصول إلى v من u. [5] ومع ذلك ، قد تؤدي DAGs المختلفة إلى نفس علاقة قابلية الوصول ونفس الترتيب الجزئي. [6] على سبيل المثال ، DAG ذات الحافتين a → b و b → c لها نفس علاقة قابلية الوصول مثل الرسم البياني بثلاثة حواف a → b و b → c و a → c. كل من DAGS هذه تنتج نفس الترتيب الجزئي ، حيث يتم ترتيب الرؤوس على أنها a a b c.
إذا كانت G عبارة عن DAG ، فإن إغلاقها الانتقالي هو الرسم البياني الذي يحتوي على معظم الحواف التي تمثل نفس علاقة قابلية الوصول. لها حافة u → v كلما تمكنت من الوصول إلى v. أي أنها تتمتع بميزة لكل زوج u ≤ v ذي صلة من العناصر المميزة في علاقة قابلية الوصول لـ G ، وبالتالي يمكن اعتبارها ترجمة مباشرة لقابلية الوصول العلاقة ≤ في المصطلحات النظرية للرسم البياني. تعمل نفس طريقة ترجمة الطلبات الجزئية إلى DAGs بشكل عام: لكل مجموعة محدودة مرتبة جزئيًا (S ، ≤) ، يكون الرسم البياني الذي يحتوي على رأس لكل عضو من S وحافة لكل زوج من العناصر المرتبطة بـ u ≤ v هو تلقائيًا DAG مغلق مؤقتًا ، وله (S ، ≤) كعلاقة قابلية الوصول. وبهذه الطريقة ، يمكن تمثيل كل مجموعة محدودة مرتبة جزئيًا كعلاقة قابلية الوصول لـ DAG.
التخفيض الانتقالي لـ DAG G هو الرسم البياني ذو الحواف الأقل التي تمثل نفس علاقة قابلية الوصول مثل G. إنه رسم فرعي لـ G ، يتشكل من تجاهل الحواف u → v التي يحتوي G أيضًا على مسار أطول يربط نفس الاثنين الرؤوس. مثل الإغلاق المتعدي ، يتم تعريف الاختزال الانتقالي بشكل فريد لـ DAGs. في المقابل ، بالنسبة للرسم البياني الموجه الذي لا يكون غير دوري ، يمكن أن يكون هناك أكثر من رسم بياني فرعي أدنى واحد له نفس علاقة قابلية الوصول.
يمثل مخطط Hasse الترتيب الجزئي لتضمين المجموعة (⊆) بين المجموعات الفرعية لمجموعة من ثلاثة عناصر.
إذا كانت DAG G لها علاقة قابلية الوصول الموصوفة بالترتيب الجزئي ≤ ، فإن التخفيض الانتقالي لـ G هو رسم بياني فرعي لـ G له حافة u → v لكل زوج في علاقة التغطية ≤. تعتبر التخفيضات الانتقالية مفيدة في تصور الطلبات الجزئية التي تمثلها ، لأنها تحتوي على حواف أقل من الرسوم البيانية الأخرى التي تمثل نفس الطلبات وبالتالي تؤدي إلى رسومات بيانية أبسط. مخطط Hasse للترتيب الجزئي هو رسم للتصغير الانتقالي حيث يتم عرض اتجاه كل حافة بوضع رأس البداية للحافة في موضع أدنى من رأس النهاية.
الترتيب الطوبولوجي
يحتوي كل رسم بياني لا دوري موجه على ترتيب طوبولوجي ، وهو ترتيب للرؤوس بحيث تظهر نقطة نهاية كل حافة في وقت مبكر في الترتيب عن نقطة نهاية الحافة. يمكن استخدام وجود مثل هذا الترتيب لتوصيف DAGs: الرسم البياني الموجه هو DAG إذا وفقط إذا كان يحتوي على ترتيب طوبولوجي. بشكل عام ، هذا الترتيب ليس فريدًا ؛ يحتوي DAG على ترتيب طوبولوجي فريد إذا وفقط إذا كان يحتوي على مسار موجه يحتوي على جميع الرؤوس ، وفي هذه الحالة يكون الترتيب هو نفسه الترتيب الذي تظهر به الرؤوس في المسار.
عائلة الترتيب الطوبولوجي لـ DAG هي نفس عائلة الامتدادات الخطية لعلاقة قابلية الوصول لـ DAG ، لذا فإن أي رسمين بيانيين يمثلان نفس الترتيب الجزئي لهما نفس مجموعة الأوامر الطوبولوجية.
العد التجميعي
تمت دراسة مشكلة تعداد الرسم البياني لعد الرسوم البيانية غير الحلقية الموجهة بواسطة Robinson (1973). عدد DAGs على رؤوس n المسمى ، لـ n = 0 ، 1 ، 2 ، 3 ، ... (بدون قيود على الترتيب الذي تظهر به هذه الأرقام في الترتيب الطوبولوجي لـ DAG) هو
1 ، 1 ، 3 ، 25 ، 543 ، 29281 ، 3781503 ، ... (تسلسل A003024 في OEIS).
يمكن حساب هذه الأرقام من خلال علاقة التكرار
تخمين إريك دبليو وايسشتاين ، وماكي وآخرون. (2004) أثبت أن نفس الأرقام تحسب المصفوفات (0،1) التي تكون جميع القيم الذاتية لها أرقامًا حقيقية موجبة. البرهان حيوي: المصفوفة A هي مصفوفة مجاورة لـ DAG إذا وفقط إذا كانت A + I مصفوفة (0،1) مع جميع القيم الذاتية موجبة ، حيث أنا أشير إلى مصفوفة الهوية. نظرًا لأن DAG لا يمكن أن تحتوي على حلقات ذاتية ، يجب أن تحتوي مصفوفة تجاورها على صفر قطري ، لذا فإن إضافة I تحافظ على خاصية أن جميع معاملات المصفوفة هي 0 أو 1.
عائلات الرسوم البيانية ذات الصلة
الشجرة القطبية عبارة عن رسم بياني موجه يتكون من توجيه حواف الشجرة الحرة. كل شجرة قطب هي DAG. على وجه الخصوص ، هذا صحيح بالنسبة للأشجار التي تشكلت عن طريق توجيه جميع الحواف للخارج من جذور الشجرة.
الشجرة المتعددة (تسمى أيضًا الرسم البياني الذي لا لبس فيه أو المنغروف) هي رسم بياني موجه يوجد فيه على الأكثر مسارًا موجهًا واحدًا (في أي اتجاه) بين أي رأسين ؛ بشكل مكافئ ، هو DAG حيث ، لكل رأس v ، يكون الرسم البياني الفرعي الذي يمكن الوصول إليه من v يشكل شجرة.
مشاكل حسابية.
الفرز والاعتراف الطوبولوجي
الفرز الطوبولوجي هو مشكلة الخوارزمية لإيجاد ترتيب طوبولوجي لـ DAG معين. يمكن حلها في الوقت الخطي. تقوم خوارزمية Kahn للفرز الطوبولوجي ببناء ترتيب قمة الرأس مباشرة. يحتفظ بقائمة من الرؤوس التي ليس لها حواف واردة من رؤوس أخرى لم يتم تضمينها بالفعل في الترتيب الطوبولوجي المركب جزئيًا ؛ تتكون هذه القائمة في البداية من الرؤوس التي لا تحتوي على حواف واردة على الإطلاق. بعد ذلك ، تضيف بشكل متكرر رأسًا واحدًا من هذه القائمة إلى نهاية الترتيب الطوبولوجي المركب جزئيًا ، وتتحقق مما إذا كان يجب إضافة جيرانها إلى القائمة. تنتهي الخوارزمية عندما تتم معالجة جميع الرؤوس بهذه الطريقة. بدلاً من ذلك ، يمكن إنشاء ترتيب طوبولوجي عن طريق عكس ترقيم الطلب اللاحق لمسح الرسم البياني للبحث العمق أولاً.
من الممكن أيضًا التحقق مما إذا كان الرسم البياني الموجه هو DAG في الوقت الخطي ، إما عن طريق محاولة العثور على ترتيب طوبولوجي ثم اختبار لكل حافة ما إذا كان الترتيب الناتج صالحًا أو بدلاً من ذلك ، بالنسبة لبعض خوارزميات الفرز الطوبولوجي ، من خلال التحقق من أن الخوارزمية تطلب جميع القمم بنجاح دون تلبية شرط الخطأ.
البناء من الرسوم البيانية الدورية
يمكن تحويل أي رسم بياني غير موجه إلى DAG باختيار ترتيب إجمالي لرؤوسه وتوجيه كل حافة من نقطة النهاية السابقة بالترتيب إلى نقطة النهاية اللاحقة. يسمى الاتجاه الناتج للحواف اتجاه لا دوري. قد تؤدي الطلبات الإجمالية المختلفة إلى نفس الاتجاه غير الدوري ، لذلك يمكن أن يكون للرسم البياني n-vertex أقل من n! التوجهات غير الدورية. عدد الاتجاهات غير الدورية يساوي | χ (−1) | ، حيث χ هي كثير الحدود اللوني للرسم البياني المعطى.
إغلاق انتقالي واختزال متعد
يمكن إنشاء الإغلاق الانتقالي لـ DAG معين ، برؤوس n وحواف m ، في الوقت O (mn) باستخدام إما بحث العرض أولاً أو بحث العمق أولاً لاختبار إمكانية الوصول من كل قمة. [22] بدلاً من ذلك ، يمكن حلها في الوقت O (nω) حيث ω &lt;2.373 هي الأس لخوارزميات مضاعفة المصفوفة السريعة ؛ هذا تحسن نظري على O (mn) المرتبط بالرسوم البيانية الكثيفة.
في كل خوارزميات الإغلاق المتعدية هذه ، من الممكن التمييز بين أزواج الرؤوس التي يمكن الوصول إليها من خلال مسار واحد على الأقل بطول اثنين أو أكثر من الأزواج التي لا يمكن توصيلها إلا بمسار طوله واحد. يتكون الاختزال المتعدي من الحواف التي تشكل مسارات بطول واحد وهي المسارات الوحيدة التي تربط نقاط النهاية الخاصة بها. لذلك ، يمكن بناء الاختزال المتعدي في نفس الحدود الزمنية التقاربية مثل الإغلاق المتعدي.
مشكلة الإغلاق
تأخذ مشكلة الإغلاق كمدخل رسمًا بيانيًا دائريًا موجهًا مرجحًا للرأس وتبحث عن الحد الأدنى (أو الأقصى) لوزن الإغلاق - مجموعة من الرؤوس C ، بحيث لا تترك أي حواف C. لا دورية ، ولكن بدون عمومية أكبر ، لأنها في هذه الحالة تعادل نفس المشكلة في تكثيف الرسم البياني. يمكن حلها في زمن كثير الحدود باستخدام تقليل مشكلة التدفق الأقصى.
خوارزميات المسار
تصبح بعض الخوارزميات أبسط عند استخدامها على DAGs بدلاً من الرسوم البيانية العامة ، بناءً على مبدأ الترتيب الطوبولوجي. على سبيل المثال ، من الممكن العثور على أقصر المسارات والمسارات الأطول من قمة بداية معينة في DAGs في الوقت الخطي عن طريق معالجة القمم بترتيب طوبولوجي ، وحساب طول المسار لكل رأس ليكون الحد الأدنى أو الأقصى للطول الذي تم الحصول عليه عبر أي من حوافه الواردة. في المقابل ، بالنسبة إلى الرسوم البيانية التعسفية ، قد يتطلب أقصر مسار خوارزميات أبطأ مثل خوارزمية Dijkstra أو خوارزمية Bellman-Ford ، ومن الصعب العثور على أطول المسارات في الرسوم البيانية التعسفية.
الجدولة
تمثيلات الرسوم البيانية غير الدورية الموجهة للطلبات الجزئية لها تطبيقات عديدة في جدولة أنظمة المهام مع قيود الترتيب. فئة مهمة من المشاكل من هذا النوع تتعلق بمجموعات الكائنات التي تحتاج إلى تحديث ، مثل خلايا جدول البيانات بعد تغيير إحدى الخلايا ، أو ملفات الكائن لجزء من برنامج الكمبيوتر بعد أن تم تعديل كود المصدر الخاص به. تغير. في هذا السياق ، يمثل الرسم البياني التبعية رسمًا بيانيًا له رأس لكل كائن يتم تحديثه ، وحافة تربط بين كائنين كلما احتاج أحدهما إلى التحديث قبل الآخر. تسمى الدورة في هذا الرسم البياني التبعية الدائرية ، وهي غير مسموح بها عمومًا ، لأنه لن تكون هناك طريقة لجدولة المهام المتضمنة في الدورة باستمرار. تشكل الرسوم البيانية التبعية بدون تبعيات دائرية DAGs.
على سبيل المثال ، عندما تتغير خلية واحدة في جدول البيانات ، من الضروري إعادة حساب قيم الخلايا الأخرى التي تعتمد بشكل مباشر أو غير مباشر على الخلية التي تم تغييرها. بالنسبة لهذه المشكلة ، فإن المهام المراد جدولتها هي عمليات إعادة حساب قيم الخلايا الفردية في جدول البيانات. تنشأ التبعيات عندما يستخدم تعبير في خلية ما قيمة من خلية أخرى. في مثل هذه الحالة ، يجب إعادة حساب القيمة المستخدمة قبل التعبير الذي يستخدمها. يسمح الترتيب الطوبولوجي لرسم بياني التبعية ، واستخدام هذا الترتيب الطوبولوجي لجدولة تحديثات الخلية ، بتحديث جدول البيانات بأكمله بتقييم واحد فقط لكل خلية. [31] تظهر مشكلات مماثلة في ترتيب المهام في ملفات makefiles الخاصة بتجميع البرامج وجدولة التعليمات لتحسين برامج الكمبيوتر منخفضة المستوى.
يتم استخدام صيغة مختلفة إلى حد ما قائمة على DAG لقيود الجدولة من خلال تقنية تقييم ومراجعة البرنامج (PERT) ، وهي طريقة لإدارة المشاريع البشرية الكبيرة التي كانت أحد التطبيقات الأولى لـ DAGs. في هذه الطريقة ، تمثل رؤوس DAG معالم المشروع بدلاً من المهام المحددة التي يتعين القيام بها. بدلاً من ذلك ، يتم تمثيل المهمة أو النشاط بحافة DAG ، التي تربط بين معلمين يمثلان بداية المهمة وإكمالها. يتم تمييز كل حافة من هذا القبيل بتقدير لمقدار الوقت الذي سيستغرقه فريق من العمال لأداء المهمة. يمثل أطول مسار في DAG هذا المسار الحرج للمشروع ، وهو المسار الذي يتحكم في إجمالي الوقت للمشروع. يمكن جدولة المعالم الفردية وفقًا لأطوال المسارات الأطول المنتهية عند الرؤوس.
شبكات معالجة البيانات
يمكن استخدام الرسم البياني غير الدوري الموجه لتمثيل شبكة من عناصر المعالجة. في هذا التمثيل ، تدخل البيانات عنصر معالجة من خلال حوافها الواردة وتترك العنصر من خلال حوافه الصادرة.
على سبيل المثال ، في تصميم الدوائر الإلكترونية ، يمكن تمثيل الكتل المنطقية التوافقية الثابتة كنظام لا دوري من البوابات المنطقية التي تحسب وظيفة أحد المدخلات ، حيث يتم تمثيل مدخلات ومخرجات الوظيفة على أنها بتات فردية. بشكل عام ، لا يمكن استخدام مخرجات هذه الكتل كمدخلات ما لم يتم التقاطها بواسطة سجل أو عنصر حالة يحافظ على خصائصه غير الدورية. مخططات الدوائر الإلكترونية إما على الورق أو في قاعدة بيانات هي شكل من أشكال الرسوم البيانية غير الدورية الموجهة باستخدام مثيلات أو مكونات لتشكيل مرجع موجه إلى مكون المستوى الأدنى. الدوائر الإلكترونية نفسها ليست بالضرورة غير دورية أو موجهة.
تصف لغات برمجة تدفق البيانات أنظمة العمليات على تدفقات البيانات ، والوصلات بين مخرجات بعض العمليات ومدخلات البعض الآخر. يمكن أن تكون هذه اللغات ملائمة لوصف مهام معالجة البيانات المتكررة ، حيث يتم تطبيق نفس مجموعة العمليات المرتبطة دوريًا على العديد من عناصر البيانات. يمكن تنفيذها كخوارزمية متوازية يتم فيها تنفيذ كل عملية من خلال عملية متوازية بمجرد أن تصبح مجموعة أخرى من المدخلات متاحة لها.
في المترجمين ، يمكن تمثيل رمز الخط المستقيم (أي تسلسل العبارات بدون حلقات أو فروع شرطية) بواسطة DAG الذي يصف مدخلات ومخرجات كل من العمليات الحسابية التي يتم إجراؤها داخل الكود. هذا التمثيل يسمح للمترجم بأداء حذف التعابير الفرعية بكفاءة. في مستوى أعلى من تنظيم الكود ، ينص مبدأ التبعيات غير الدورية على أن التبعيات بين الوحدات أو مكونات نظام برمجيات كبير يجب أن تشكل رسمًا بيانيًا لا دوريًا موجهًا.
الهياكل السببية
الرسوم البيانية التي تمثل فيها الرؤوس أحداثًا تحدث في وقت محدد ، وحيث تكون الحواف دائمًا نقطة من قمة الزمن المبكر إلى قمة الوقت المتأخر للحافة ، تكون بالضرورة موجَّهة وغير دورية. يتبع عدم وجود دورة لأن الوقت المرتبط بالرأس يزداد دائمًا كلما اتبعت أي مسار في الرسم البياني حتى لا يمكنك أبدًا العودة إلى قمة على مسار. هذا يعكس حدسنا الطبيعي بأن السببية تعني أن الأحداث لا يمكن أن تؤثر إلا على المستقبل ، ولا تؤثر أبدًا على الماضي ، وبالتالي ليس لدينا حلقات سببية. مثال على هذا النوع من الرسم البياني غير الدوري الموجه هو تلك التي تمت مواجهتها في نهج المجموعة السببية للجاذبية الكمية على الرغم من أن الرسوم البيانية التي تم النظر فيها في هذه الحالة مكتملة بشكل عابر. في مثال محفوظات الإصدار ، يرتبط كل إصدار من البرنامج بوقت فريد ، وعادةً ما يكون الوقت الذي تم فيه حفظ الإصدار أو الالتزام به أو إصداره. بالنسبة إلى الرسوم البيانية للاقتباس ، يتم نشر المستندات في وقت واحد ويمكن أن تشير فقط إلى المستندات القديمة.
في بعض الأحيان لا ترتبط الأحداث بوقت مادي معين. شريطة أن يكون لأزواج الأحداث علاقة سببية بحتة ، أي أن الحواف تمثل العلاقات السببية بين الأحداث ، سيكون لدينا رسم بياني لا دوري موجه. على سبيل المثال ، تمثل شبكة بايز نظامًا للأحداث الاحتمالية كرؤوس في الرسم البياني غير الدوري الموجه ، حيث يمكن حساب احتمالية وقوع حدث من احتمالات أسلافها في DAG. في هذا السياق ، فإن الرسم البياني الأخلاقي لـ DAG هو الرسم البياني غير المباشر الذي تم إنشاؤه عن طريق إضافة حافة (غير موجهة) بين جميع الآباء من نفس الرأس (تسمى أحيانًا الزواج) ، ثم استبدال جميع الحواف الموجهة بحواف غير موجهة. هناك نوع آخر من الرسم البياني له بنية سببية مماثلة وهو مخطط التأثير ، حيث تمثل رؤوسه إما قرارات يجب اتخاذها أو معلومات غير معروفة ، وتمثل حوافها تأثيرات سببية من رأس إلى آخر. في علم الأوبئة ، على سبيل المثال ، غالبًا ما تُستخدم هذه الرسوم البيانية لتقدير القيمة المتوقعة من الخيارات المختلفة للتدخل.
والعكس صحيح أيضا. في أي تطبيق يتم تمثيله بواسطة رسم بياني لا دوري موجه ، يوجد هيكل سببي ، إما ترتيب صريح أو وقت في المثال أو ترتيب يمكن اشتقاقه من بنية الرسم البياني. يتبع هذا لأن جميع الرسوم البيانية غير الدورية الموجهة لها ترتيب طوبولوجي ، أي أن هناك طريقة واحدة على الأقل لترتيب الرؤوس بحيث تشير جميع الحواف في نفس الاتجاه على طول هذا الترتيب.
علم الأنساب وتاريخ الإصدار
يمكن النظر إلى الأشجار العائلية على أنها رسوم بيانية غير دورية موجهة ، مع رأس لكل فرد من أفراد الأسرة وحافة لكل علاقة بين الوالدين والطفل. على الرغم من الاسم ، فإن هذه الرسوم البيانية ليست بالضرورة أشجارًا بسبب إمكانية الزواج بين الأقارب (لذا فإن الطفل له سلف مشترك من جهة الأم والأب) مما يتسبب في انهيار النسب. الرسوم البيانية للنسب الأمومي (علاقات "الأم" بين النساء) والنسب الأبوي (علاقات "الأب" بين الرجال) هي أشجار ضمن هذا الرسم البياني. نظرًا لأنه لا يمكن لأحد أن يصبح أسلافه ، فإن أشجار العائلة غير دورية.
للسبب نفسه ، يحتوي تاريخ إصدار نظام التحكم في المراجعة الموزعة ، مثل Git ، بشكل عام على بنية الرسم البياني غير الدوري الموجه ، حيث يوجد رأس لكل مراجعة وحافة تربط أزواج المراجعات التي كانت مشتقة مباشرة من بعضها البعض. هذه ليست أشجارًا بشكل عام بسبب عمليات الدمج.
في العديد من الخوارزميات العشوائية في الهندسة الحسابية ، تحتفظ الخوارزمية بسجل DAG يمثل تاريخ إصدار بنية هندسية على مدار سلسلة من التغييرات في الهيكل. على سبيل المثال ، في خوارزمية تدريجية عشوائية لتثليث Delaunay ، يتغير التثليث عن طريق استبدال مثلث واحد بثلاثة مثلثات أصغر عند إضافة كل نقطة ، وعن طريق عمليات "قلب" التي تستبدل أزواج المثلثات بزوج مختلف من المثلثات. يحتوي سجل DAG لهذه الخوارزمية على رأس لكل مثلث تم إنشاؤه كجزء من الخوارزمية ، والحواف من كل مثلث إلى المثلثين أو المثلثات الثلاثة الأخرى التي تحل محله. تسمح هذه البنية بالإجابة على استعلامات موقع النقطة بكفاءة: للعثور على موقع نقطة استعلام q في تثليث Delaunay ، اتبع مسارًا في السجل DAG ، في كل خطوة ، انتقل إلى المثلث البديل الذي يحتوي على q. يجب أن يكون المثلث الأخير الذي يتم الوصول إليه في هذا المسار هو مثلث Delaunay الذي يحتوي على q.
الرسوم البيانية للاقتباس
في الرسم البياني للاقتباس ، تكون الرؤوس عبارة عن مستندات بتاريخ نشر واحد. تمثل الحواف الاقتباسات من ببليوغرافيا وثيقة ما إلى وثائق أخرى سابقة بالضرورة. يأتي المثال الكلاسيكي من الاستشهادات بين الأوراق الأكاديمية كما ورد في مقال "شبكات الأوراق العلمية" عام 1965 بقلم ديريك جيه دي سولا برايس الذي استمر في إنتاج النموذج الأول لشبكة الاستشهادات ، نموذج السعر. في هذه الحالة ، يكون عدد الاقتباسات لورقة ما هو مجرد درجة في الرأس المقابل لشبكة الاقتباس. هذا مقياس مهم في تحليل الاقتباس. تقدم أحكام المحكمة مثالاً آخر حيث يدعم القضاة استنتاجاتهم في قضية واحدة من خلال استدعاء قرارات سابقة أخرى صدرت في قضايا سابقة. يتم تقديم مثال أخير عن طريق براءات الاختراع التي يجب أن تشير إلى حالة التقنية الصناعية السابقة ، وبراءات الاختراع السابقة ذات الصلة بمطالبة البراءة الحالية. من خلال مراعاة الخصائص الخاصة للرسوم البيانية الحلقية الموجهة ، يمكن للمرء تحليل شبكات الاستشهاد بتقنيات غير متوفرة عند تحليل الرسوم البيانية العامة التي تم النظر فيها في العديد من الدراسات باستخدام تحليل الشبكة. على سبيل المثال ، يعطي الاختزال المتعدي رؤى جديدة حول توزيعات الاقتباسات الموجودة في التطبيقات المختلفة ، مع إبراز الاختلافات الواضحة في آليات إنشاء شبكات الاستشهادات في سياقات مختلفة. أسلوب آخر هو تحليل المسار الرئيسي ، والذي يتتبع روابط الاقتباس ويقترح سلاسل الاقتباس الأكثر أهمية في رسم بياني للاقتباس معين.
نموذج السعر بسيط للغاية بحيث لا يمكن أن يكون نموذجًا واقعيًا لشبكة الاستشهادات ، ولكنه بسيط بما يكفي للسماح بالحلول التحليلية لبعض خصائصها. يمكن العثور على العديد من هذه النتائج باستخدام النتائج المستمدة من النسخة غير الموجهة لنموذج السعر ، نموذج Barabási-Albert. ومع ذلك ، نظرًا لأن نموذج Price يعطي رسمًا بيانيًا لا دوريًا موجهًا ، فهو نموذج مفيد عند البحث عن الحسابات التحليلية للخصائص الفريدة للرسوم البيانية غير الدورية الموجهة. على سبيل المثال ، يتم قياس طول أطول مسار ، من العقدة رقم n المضافة إلى الشبكة إلى العقدة الأولى في الشبكة.
ضغط البيانات
يمكن أيضًا استخدام الرسوم البيانية غير الدورية الموجهة كتمثيل مضغوط لمجموعة من المتواليات. في هذا النوع من التطبيقات ، يجد المرء DAG حيث تشكل المسارات التسلسلات المحددة. عندما تشترك العديد من التسلسلات في نفس التتابعات اللاحقة ، يمكن تمثيل هذه التسلسلات اللاحقة المشتركة بجزء مشترك من DAG ، مما يسمح للتمثيل باستخدام مساحة أقل مما قد يتطلبه سرد جميع التسلسلات بشكل منفصل. على سبيل المثال ، الرسم البياني للكلمات غير الدورية الموجه عبارة عن بنية بيانات في علوم الكمبيوتر مكونة من رسم بياني لا دوري موجه بمصدر واحد ومع حواف موضحة بأحرف أو رموز ؛ تمثل المسارات من المصدر إلى الأحواض في هذا الرسم البياني مجموعة من السلاسل ، مثل الكلمات الإنجليزية. يمكن تمثيل أي مجموعة من المتتاليات كمسارات في شجرة ، من خلال تشكيل رأس شجرة لكل بادئة في التسلسل وجعل أصل إحدى هذه الرؤوس يمثل التسلسل بعنصر أقل ؛ الشجرة التي تشكلت بهذه الطريقة لمجموعة من الخيوط تسمى trie. يوفر الرسم البياني للكلمات الحلقية الموجه مساحة على مثلث من خلال السماح للمسارات بالتباعد والالتحاق مرة أخرى ، بحيث يمكن تمثيل مجموعة من الكلمات التي لها نفس اللواحق المحتملة برأس شجرة واحد.
تحدث نفس فكرة استخدام DAG لتمثيل مجموعة من المسارات في مخطط القرار الثنائي ، وهي بنية بيانات قائمة على DAG لتمثيل الوظائف الثنائية. في الرسم التخطيطي للقرار الثنائي ، تتم تسمية كل رأس غير حوضي باسم متغير ثنائي ، ويتم تسمية كل حوض وكل حافة بالرقم 0 أو 1. قيمة الوظيفة لأي تعيين حقيقة للمتغيرات هي القيمة عند تم العثور على الحوض باتباع مسار ، بدءًا من رأس المصدر الفردي ، والذي يتبع الحافة الصادرة عند كل قمة غير مغسلة للحافة الصادرة المسمى بقيمة متغير هذا الرأس. تمامًا كما يمكن عرض الرسوم البيانية للكلمات غير الدورية الموجهة باعتبارها شكلًا مضغوطًا من المحاولات ، يمكن عرض مخططات القرار الثنائي على أنها أشكال مضغوطة من أشجار القرار التي توفر مساحة من خلال السماح للمسارات بالانضمام عندما تتفق على نتائج جميع القرارات المتبقية.
خندق كوريل ، الذي يُطلق عليه أحيانًا اسم "خندق كوريل كامتشاتكا" ، عبارة عن منخفض عميق وضيق تحت سطح البحر يقع في شمال غرب المحيط الهادئ نتيجة تقارب صفيحتين تكتونيتن. : صفيحة المحيط الهادئ و صفيحة أوخوتسك . عمقها الأقصى 10542 م .
يقع غرق اندساس صفيحة المحيط الهادئ تحت صفيحة أوخوتسك في أصل خندق ويولد نشاطًا بركانيًا شديدًا عند حافة الصفيحة التي تغرق تحتها والتي تكون في أصل جزر الكوريل .
يقع الخندق غرب أرخبيل الكوريل وجنوب شبه جزيرة كامتشاتكا وشمال اليابان . خندق كوريل يمتد بين 41 ° و 56 ° شمال خط العرض و 146 درجة إلى 167 درجة شرق خط الطول . ويستمر إلى الجنوب الغربي مع خندق اليابان.
الهسلاندونة الطارئة (الاسم العلمي:†Hesslandona necopina) هي منقرض من الحيوانات تتبع الهسلاندونة من الهسلاندونات.
أكوابورين الأكوابورينات ، وتسمى أيضًا قنوات الماء، هي بروتينات من عائلة كبيرة من البروتينات الداخلية الرئيسية التي تشكل مسامًا في غشاء الخلايا الحية، مما يسهل نقل الماء بين الخلايا بشكل أساسي. تحتوي أغشية الخلايا لمجموعة متنوعة من البكتيريا والفطريات والخلايا الحيوانية والنباتية على أكوابورينات يمكن للمياه أن تتدفق من خلالها بسرعة أكبر داخل وخارج الخلية أكثر من الانتشار عبر طبقة ثنائية الفوسفوليبيد (غشاء الخلية). تحتوي الأكوابورينات على ستة مجالات حلزونية ألفا تغطي الأغشية مع كل من النهايات الكربوكسيلية والأمينية على الجانب السيتوبلازمي. تحتوي حلقتان كارهتان للماء على شكل NPA محفوظ من الأسباراجين والبرولين والألانين والذي يشكل برميلًا يحيط بمنطقة تشبه المسام المركزية التي تحتوي على كثافة بروتينية إضافية. نظرًا لأن الأكوابورينات عادةً ما تكون مفتوحة دائمًا ومنتشرة في كل نوع من الخلايا تقريبًا، فإن هذا يؤدي إلى سوء فهم مفاده أن الماء يمر بسهولة عبر غشاء الخلية تحت تدرج تركيزه. يمكن أن يمر الماء عبر غشاء الخلية من خلال الانتشار البسيط لأنه جزيء صغير، ومن خلال التناضح، في الحالات التي يكون فيها تركيز الماء خارج الخلية أكبر من تركيزه داخلها. ومع ذلك، نظرًا لأن الماء هو جزيء قطبي، فإن عملية الانتشار البسيطة هذه بطيئة نسبيًا، وتمر غالبية الماء عبر الأكوابورين.
مُنحت جائزة نوبل في الكيمياء لعام 2003 مناصفةً لكل من "بيتر أجري" لاكتشاف الأكوابورينات و"رودريك ماكينون" عن عمله على تركيب وآلية عمل قنوات البوتاسيوم.
ارتبطت العيوب الجينية التي تنطوي على جينات الأكوابورين بالعديد من الأمراض البشرية بما في ذلك مرض السكري الكاذب الكلوي والتهاب النخاع والعصب البصري.
يمكن أن ينتشر الماء بحرية من خلال طبقة ثنائية الدهون بمعدل محدود، ولكن لوحظ أن نفاذية الماء في خلايا الدم الحمراء كانت أعلى بكثير مما كان متوقعًا للانتشار التلقائي. دفعت هذه الملاحظة إلى البحث عن بروتينات متخصصة قد تكون موجودة لتسهيل تدفق المياه عبر الأغشية. تم تنقية قناة الماء المغلفة من غشاء خلايا الدم الحمراء في البداية باعتبارها نوعًا مرتبطًا بغشاء 28 كيلو دالتون، يُطلق عليه اسم بروتين متكامل مكون من 28 كيلو دالتون (CHIP28) (Denker et al. 1988). تم عرض التعبير عن CHIP28 inXenopusoocytes لاحقًا لإحداث انتشار سريع للمياه أسفل التدرجات التناضحية عبر غشاء البلازما، مما يؤدي إلى تحديد أول قناة موصلة للماء (Prestonet al. 1992). اقترح تحليل تسلسل البروتين أن CHIP28 متماثل مع البروتين الداخلي الرئيسي (MIP) من خلايا ألياف العدسة (جورين وآخرون 1984)، وبعد وقت قصير من إنشاء وظيفة مسام الماء في CHIP28، تم العثور على البروتينات المتماثلة في الثدييات والبكتيريا والنباتات تعمل كقنوات مائية، ومصطلح "أكوابورين" تم صياغته لأعضاء عائلة البروتين هذه (أجري، ساساكي وكريسبيلز 1993)، وبناءً عليه، تمت إعادة تسمية CHIP28 إلى AQP1 وأصبح MIP يُعرف الآن باسم AQP0.
جذبت آلية النقل المائي الميسر والوجود المحتمل لمسام المياه الباحثين منذ عام 1957. في معظم الخلايا، ينتقل الماء للداخل والخارج عن طريق التناضح من خلال المكون الدهني لأغشية الخلايا. نظرًا لارتفاع نفاذية الماء نسبيًا لبعض الخلايا الظهارية، كان يشتبه منذ فترة طويلة في وجود آلية إضافية لنقل المياه عبر الأغشية. قام سولومون وزملاؤه بعمل رائد في مجال نفاذية الماء عبر غشاء الخلية في أواخر الخمسينيات من القرن الماضي. في منتصف الستينيات، سعت فرضية بديلة ("نموذج التقسيم-الانتشار") إلى إثبات أن جزيئات الماء تنقسم بين طور الماء ومرحلة الدهون ثم تنتشر عبر الغشاء، وتعبرها حتى الطور البيني التالي حيث تترك وعاد الدهن إلى الطور المائي. دراسات باريسي، إيدلمان، كارفونيس وآخرون. أكد ليس فقط على أهمية وجود القنوات المائية ولكن أيضًا على إمكانية تنظيم خصائص نفاذيتها. في عام 1990، أظهرت تجارب فيركمان التعبير الوظيفي للقنوات المائية، مما يشير إلى أن قنوات المياه عبارة عن بروتينات فعالة.
أُبلغ عن أول أكوابورين، "أكوابورين -1" (المعروف أصلاً باسم CHIP 28)، بواسطة بيتر أجري، من جامعة جونز هوبكنز عام 1992. في عام 1999، مع فرق بحثية أخرى، قدم "أجري" أول صور عالية الدقة للبنية ثلاثية الأبعاد للأكوابورين، وهي أكوابورين -1. حددت دراسات أخرى باستخدام محاكاة الكمبيوتر العملاق مسار الماء أثناء تحركه عبر القناة وأظهرت كيف يمكن للمسام أن تسمح بمرور الماء دون مرور المواد المذابة الصغيرة. حصل البحث الرائد والاكتشاف اللاحق لقنوات المياه من قبل أجري وزملائه على جائزة نوبل في الكيمياء عام 2003. قال أجري إنه اكتشف الأكوابورينات "بالصدفة". كان يدرس مستضدات فصيلة الدم Rh وعزل جزيء Rh، لكن الجزيء الثاني، بحجم 28 كيلو دالتون (وبالتالي يُسمى 28K) استمر في الظهور. في البداية ظنوا أنه جزء من جزيء Rh، أو ملوث، لكن اتضح أنه نوع جديد من الجزيئات ذات وظيفة غير معروفة. كانت موجودة في هياكل مثل الأنابيب الكلوية وخلايا الدم الحمراء، وترتبط ببروتينات من أصول متنوعة، مثل دماغ ذبابة الفاكهة والبكتيريا وعدسة العين وأنسجة النبات.
ومع ذلك، فإن التقرير الأول عن نقل المياه عبر الأغشية بواسطة البروتين كان بقلم جورج بنجا وآخرون في عام 1986، قبل نشر أجري الأول حول هذا الموضوع. أدى ذلك إلى جدل مفاده أن عمل بنجا لم يتم الاعتراف به بشكل كاف سواء من قبل أجري أو من قبل لجنة جائزة نوبل.