شبكة (ترتيب)

العلاقات الثنائية المتعدية 
متماثلمضاد للتناظرمتصلمؤسس بشكل جيدلديه روابطلديه لقاءاتانعكاسيغير انعكاسيغير متماثل
توتال، سيميكونكسمضاد للانعكاس
علاقة التكافؤعلامة صح خضراءYعلامة صح خضراءY
طلب مسبق (طلب شبه رسمي)علامة صح خضراءY
طلب جزئيعلامة صح خضراءYعلامة صح خضراءY
إجمالي الطلبات المسبقةعلامة صح خضراءYعلامة صح خضراءY
إجمالي الطلبعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
الطلب المسبقعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
ترتيب شبه جيدعلامة صح خضراءYعلامة صح خضراءY
ترتيب جيدعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
شعريةعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
الانضمام إلى شبه الشبكةعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
شبكة اللقاءاتعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
ترتيب جزئي صارمعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
ترتيب ضعيف صارمعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
إجمالي الطلب الصارمعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءYعلامة صح خضراءY
متماثلمضاد للتناظرمتصلمؤسس بشكل جيدلديه روابطلديه لقاءاتانعكاسيغير انعكاسيغير متماثل
التعريفات، للجميعأ،ب{\displaystyle a,b}وS:{\displaystyle S\neq \varnothing :} أRببRأ{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}أRب و بRأأ=ب{\displaystyle {\begin{aligned}aRb{\text{ و }}&bRa\\\Rightarrow a={}&b\end{aligned}}}أبأRب أو بRأ{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}مينSموجود{\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}أبموجود{\displaystyle {\begin{aligned}a\vee b\\{\text{يوجد}}\end{aligned}}}أبموجود{\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}أRأ{\displaystyle aRa}لا أRأ{\displaystyle {\text{not }}aRa}أRبلا بRأ{\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}
علامة صح خضراءيشير الرمز Y إلى أن خاصية العمود صحيحة دائمًا بالنسبة لعنصر الصف (في أقصى اليسار)، بينما يشير الرمز ✗ إلى أن الخاصية غير مضمونة بشكل عام (قد تكون صحيحة أو خاطئة). على سبيل المثال، يُشار إلى أن كل علاقة تكافؤ متناظرة، ولكن ليس بالضرورة مضادة للتناظر، بالرمز Y في عمود "متناظر" والرمز في عمود "مضاد للتناظر". علامة صح خضراء

تتطلب جميع التعريفات ضمنيًا العلاقة المتجانسةR{\displaystyle R}يكون متعدياً : للجميعأ،ب،ج،{\displaystyle a,b,c,}لوأRب{\displaystyle aRb}وبRج{\displaystyle bRc}ثمأRج.{\displaystyle aRc.} قد يتطلب تعريف المصطلح خصائص إضافية غير مدرجة في هذا الجدول.

الشبكة هي بنية مجردة تُدرس في فرعي نظرية الترتيب والجبر المجرد في الرياضيات . تتكون من مجموعة مرتبة جزئيًا، حيث يمتلك كل زوج من العناصر حدًا أعلى فريدًا (يُسمى أيضًا الحد الأعلى الأدنى أو التقاطع ) وحدًا أدنى فريدًا (يُسمى أيضًا الحد الأدنى الأعلى أو التقاطع ). مثال على ذلك مجموعة القوى لمجموعة مرتبة جزئيًا حسب الاحتواء ، حيث يكون الحد الأعلى هو الاتحاد والحد الأدنى هو التقاطع . مثال آخر هو الأعداد الطبيعية ، مرتبة جزئيًا حسب قابلية القسمة ، حيث يكون الحد الأعلى هو المضاعف المشترك الأصغر والحد الأدنى هو القاسم المشترك الأكبر .

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

يُطلق على المجال الفرعي الذي يدرس الشبكات اسم نظرية الشبكات .

تعريف

يمكن تعريف الشبكة إما من الناحية النظرية كمجموعة مرتبة جزئياً، أو كبنية جبرية.

مجموعة مرتبة جزئيا

مجموعة مرتبة جزئياً (مجموعة جزئية)(ل،){\displaystyle (L,\leq )}تُسمى الشبكة شبكة إذا كانت شبكة شبه متصلة وشبكة شبه متصلة في آن واحد ، أي كل مجموعة فرعية مكونة من عنصرين{أ،ب}ل{\displaystyle \{a,b\}\subseteq L}يحتوي على وصلة (أي الحد الأعلى الأدنى، المشار إليه بـأب{\displaystyle a\vee b}) ومقابل ذلك ، يمثل الحد الأدنى الأكبر (أي الحد الأدنى الأكبر، ويرمز إليه بـأب{\displaystyle a\wedge b}). هذا التعريف يجعل{\displaystyle \,\wedge \,}و{\displaystyle \,\vee \,}العمليات الثنائية . كلا العمليتين رتيبتان بالنسبة للترتيب المعطى:أ1أ2{\displaystyle a_{1}\leq a_{2}}وب1ب2{\displaystyle b_{1}\leq b_{2}}يشير ذلك إلى أنأ1ب1أ2ب2{\displaystyle a_{1}\vee b_{1}\leq a_{2}\vee b_{2}}وأ1ب1أ2ب2.{\displaystyle a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}.}

يستنتج من ذلك، بالاستقراء ، أن لكل مجموعة جزئية منتهية غير فارغة في شبكة حدًا أعلى أدنى وحدًا أدنى أعلى. وبفرضيات إضافية، يمكن التوصل إلى استنتاجات أخرى؛ انظر مقال "الاكتمال (نظرية الترتيب)" لمزيد من التفاصيل حول هذا الموضوع. يتناول هذا المقال أيضًا كيفية إعادة صياغة التعريف السابق بدلالة وجود روابط غالوا مناسبة بين مجموعات مرتبة جزئيًا ذات صلة - وهو نهج ذو أهمية خاصة في دراسة الشبكات من منظور نظرية الفئات ، وفي تحليل المفاهيم الرسمية .

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

كبنية جبرية

الشبكة هي بنية جبرية(ل،،){\displaystyle (L,\vee ,\wedge )}، تتكون من مجموعةل{\displaystyle L}وعمليتان ثنائيتان، تبادليتان وتجميعيتان{\displaystyle \vee }و{\displaystyle \wedge }علىل{\displaystyle L}تحقيق الهويات البديهية التالية (والتي تسمى أحيانًا قوانين الامتصاص ) لجميع العناصرأ،بل{\displaystyle a,b\in L} : أ(أب)=أ{\displaystyle a\vee (a\wedge b)=a}أ(أب)=أ{\displaystyle a\wedge (a\vee b)=a}

تُعتبر المتطابقتان التاليتان عادةً من البديهيات، على الرغم من أنهما ناتجتان عن قانوني الامتصاص معًا. [ 2 ] وتُسمى هذه القوانين بقوانين التماثل . أأ=أ{\displaystyle a\vee a=a}أأ=أ{\displaystyle a\wedge a=a}

تؤكد هذه البديهيات أن كلا(ل،){\displaystyle (L,\vee )}و(ل،){\displaystyle (L,\wedge )}هي أنصاف شبكات . قوانين الامتصاص، وهي البديهيات الوحيدة المذكورة أعلاه التي تظهر فيها كل من "الالتقاء" و"الالتحام"، تميز الشبكة عن أي زوج من هياكل أنصاف الشبكات، وتضمن تفاعل نصفي الشبكتين بشكل مناسب. على وجه الخصوص، كل نصف شبكة هو ثنائي للأخرى. يمكن اعتبار قوانين الامتصاص شرطًا بأن نصفي الشبكتين "الالتقاء" و"الالتحام" يحددان نفس الترتيب الجزئي .

العلاقة بين التعريفين

تُنتج الشبكة القائمة على نظرية الترتيب العمليتين الثنائيتين{\displaystyle \vee }و.{\displaystyle \wedge .}بما أنه يمكن التحقق بسهولة من قوانين التبديل والتجميع والامتصاص لهذه العمليات، فإنها تجعل(ل،،){\displaystyle (L,\vee ,\wedge )}إلى شبكة بالمعنى الجبري.

والعكس صحيح أيضاً. بالنظر إلى شبكة معرفة جبرياً(ل،،)،{\displaystyle (L,\vee ,\wedge ),}يمكن تعريف ترتيب جزئي{\displaystyle \leq }علىل{\displaystyle L}عن طريق الضبط أب لو أ=أب، أو {\displaystyle a\leq b{\text{ if }}a=a\wedge b,{\text{ or }}}أب لو ب=أب،{\displaystyle a\leq b{\text{ if }}b=a\vee b,} لجميع العناصرأ،بل.{\displaystyle a,b\in L.}تضمن قوانين الامتصاص أن يكون كلا التعريفين متكافئين: أ=أب يشير إلى ب=ب(بأ)=(أب)ب=أب{\displaystyle a=a\wedge b{\text{ implies }}b=b\vee (b\wedge a)=(a\wedge b)\vee b=a\vee b} وينطبق الأمر نفسه على الاتجاه الآخر.

يمكن الآن التحقق من العلاقة{\displaystyle \leq }يُعرّف هذا الأسلوب ترتيبًا جزئيًا يتم فيه إجراء عمليات الالتقاء والربط الثنائية من خلال العمليات الأصلية.{\displaystyle \vee }و.{\displaystyle \wedge .}

بما أن التعريفين للشبكة متكافئان، فيمكن للمرء أن يستدعي بحرية جوانب أي من التعريفين بأي طريقة تناسب الغرض المطروح.

شبكة محدودة

الشبكة المحدودة هي شبكة تحتوي بالإضافة إلى ذلك على عنصر أعظم (يسمى أيضًا العنصر الأقصى أو العنصر الأعلى ، ويرمز له بـ1{\displaystyle 1}أو{\displaystyle \top }) وأصغر عنصر (يسمى أيضًا الحد الأدنى أو القاع ، ويرمز له بـ0{\displaystyle 0}أو{\displaystyle \bot }، والتي تحقق 0x1 لكل xل.{\displaystyle 0\leq x\leq 1\;{\text{ for every }}x\in L.}

يمكن تعريف الشبكة المحدودة أيضًا على أنها بنية جبرية من الشكل التالي:(ل،،،0،1){\displaystyle (L,\vee ,\wedge ,0,1)}بحيث(ل،،){\displaystyle (L,\vee ,\wedge )}هي شبكة،0{\displaystyle 0}(الجزء السفلي من الشبكة) هو عنصر الهوية لعملية الربط،{\displaystyle \vee ,}و1{\displaystyle 1}(قمة الشبكة) هي العنصر المحايد لعملية الالتقاء.{\displaystyle \wedge .}أ0=أ{\displaystyle a\vee 0=a}أ1=أ{\displaystyle a\wedge 1=a}

يمكن إثبات أن المجموعة المرتبة جزئيًا هي شبكة محدودة إذا وفقط إذا كان لكل مجموعة منتهية من العناصر (بما في ذلك المجموعة الفارغة) وصلة وتقاطع.

يمكن تضمين أي شبكة في شبكة محدودة بإضافة عنصر أكبر وعنصر أصغر. علاوة على ذلك، فإن كل شبكة منتهية غير فارغة تكون محدودة، وذلك بأخذ وصل (أو تقاطع) جميع العناصر، ويرمز له بـ1=ل=أ1أن{\textstyle 1=\bigvee L=a_{1}\lor \cdots \lor a_{n}}(على التوالى0=ل=أ1أن{\textstyle 0=\bigwedge L=a_{1}\land \cdots \land a_{n}}) أينل={أ1،...،أن}{\displaystyle L=\left\{a_{1},\ldots ,a_{n}\right\}}هي مجموعة جميع العناصر.

الاتصال بالبنى الجبرية الأخرى

ترتبط الشبكات ببعض البنى الجبرية الشبيهة بالمجموعات . ولأنّ خاصيتي الالتقاء والوصل تتبادلان وتترافقان، يمكن اعتبار الشبكة مكونة من مجموعتين شبهيتين تبادليتين لهما نفس المجال. بالنسبة للشبكة المحدودة، تكون هاتان المجموعتان شبهيتين في الواقع أحاديات تبادلية . قانون الامتصاص هو المتطابقة الوحيدة المميزة لنظرية الشبكات. كما يمكن اعتبار الشبكة المحدودة هيكلاً تبادلياً بدون بديهية التوزيع.

بفضل خصائص التبديل والتجميع والتكرار، يمكن اعتبار عمليتي الربط والالتقاء عمليتين على مجموعات منتهية غير فارغة، بدلاً من كونهما عمليتين على أزواج من العناصر. في شبكة محدودة، يمكن تعريف عمليتي الربط والالتقاء للمجموعة الفارغة أيضاً (على النحو التالي:0{\displaystyle 0}و1،{\displaystyle 1,}على التوالي). وهذا يجعل الشبكات المحدودة أكثر طبيعية إلى حد ما من الشبكات العامة، ويشترط العديد من المؤلفين أن تكون جميع الشبكات محدودة.

يلعب التفسير الجبري للشبكات دورًا أساسيًا في الجبر الشامل .

أمثلة

  • لأي مجموعةأ،{\displaystyle A,}مجموعة جميع المجموعات الفرعية منأ{\displaystyle A}(تسمى مجموعة القوى لـأ{\displaystyle A}يمكن ترتيبها عبر تضمين المجموعات الجزئية للحصول على شبكة محدودة بـأ{\displaystyle A}نفسها والمجموعة الفارغة. في هذه الشبكة، يتم توفير الحد الأعلى عن طريق اتحاد المجموعات ويتم توفير الحد الأدنى عن طريق تقاطع المجموعات (انظر الشكل  1).
  • لأي مجموعةأ،{\displaystyle A,}مجموعة جميع المجموعات الجزئية المنتهية منأ،{\displaystyle A,}مرتبة حسب الاحتواء، هي أيضًا شبكة، وستكون محدودة إذا وفقط إذاأ{\displaystyle A}محدود.
  • لأي مجموعةأ،{\displaystyle A,}مجموعة جميع أقسامأ،{\displaystyle A,}مرتبة حسب التحسين ، هي شبكة (انظر الشكل  3).
  • تشكل الأعداد الصحيحة الموجبة بترتيبها المعتاد شبكة غير محدودة، تحت عمليتي "min" و "max". 1 هو الأدنى؛ لا يوجد أعلى (انظر الشكل  4).
  • المربع الديكارتي للأعداد الطبيعية، مرتبة بحيث(أ،ب)(ج،د){\displaystyle (a,b)\leq (c,d)}لوأج و بد.{\displaystyle a\leq c{\text{ and }}b\leq d.}الزوجان(0،0){\displaystyle (0,0)}هو العنصر السفلي؛ لا يوجد عنصر علوي (انظر الصورة  5).
  • تشكل الأعداد الطبيعية أيضًا شبكة تحت عمليات أخذ القاسم المشترك الأكبر والمضاعف المشترك الأصغر ، مع قابلية القسمة كعلاقة ترتيب:أب{\displaystyle a\leq b}لوأ{\displaystyle a}يقسمب.{\displaystyle b.}1{\displaystyle 1}هو الأسفل؛0{\displaystyle 0}هذا هو الأعلى. الصورة  2 تُظهر شبكة فرعية محدودة.
  • كل شبكة كاملة (انظر أدناه أيضًا ) هي شبكة محدودة (محددة نوعًا ما). وتنتج عن هذه الفئة مجموعة واسعة من الأمثلة العملية .
  • مجموعة العناصر المدمجة في شبكة حسابية كاملة هي شبكة ذات عنصر أصغر، حيث تُحدد عمليات الشبكة بتقييد العمليات المقابلة في الشبكة الحسابية. هذه هي الخاصية المميزة التي تُفرق الشبكات الحسابية عن الشبكات الجبرية ، التي لا تُشكل عناصرها المدمجة سوى شبه شبكة متصلة . تُدرس هاتان الفئتان من الشبكات الكاملة في نظرية المجالات .

تُقدم أمثلة إضافية للشبكات لكل خاصية من الخصائص الإضافية التي نناقشها أدناه.

أمثلة على غير الشبكات

الصورة  8: مجموعة مرتبة غير شبكية:أ{\displaystyle a}وب{\displaystyle b}لها حدود دنيا مشتركة0،د،ز،ح،{\displaystyle 0,d,g,h,}وأنا،{\displaystyle i,}لكن لا يوجد بينها حد أدنى أقصى .
الصورة  7: مجموعة ترتيبية غير شبكية:ب{\displaystyle b}وج{\displaystyle c}لها حدود عليا مشتركةد،هـ،{\displaystyle d,e,}وو،{\displaystyle f,}لكن لا يوجد بينها الحد الأعلى الأدنى .
الصورة  6: مجموعة مرتبة غير شبكية:ج{\displaystyle c}ود{\displaystyle d}ليس لها حد أعلى مشترك.

معظم المجموعات المرتبة جزئياً ليست شبكات، بما في ذلك ما يلي.

  • مجموعة جزئية منفصلة، ​​أي مجموعة جزئية بحيثxy{\displaystyle x\leq y}يشير إلىx=y،{\displaystyle x=y,}تُعتبر المجموعة شبكةً إذا وفقط إذا احتوت على عنصر واحد على الأكثر. وعلى وجه الخصوص، فإن المجموعة الجزئية المرتبة المنفصلة المكونة من عنصرين ليست شبكة.
  • على الرغم من أن المجموعة{1،2،3،6}{\displaystyle \{1,2,3,6\}}الترتيب الجزئي حسب قابلية القسمة هو شبكة، المجموعة{1،2،3}{\displaystyle \{1,2,3\}}الترتيب المرتب ليس شبكة لأن الزوج 2، 3 يفتقر إلى وصلة؛ وبالمثل، يفتقر الزوج 2، 3 إلى نقطة التقاء في{2،3،6}.{\displaystyle \{2,3,6\}.}
  • المجموعة{1،2،3،12،18،36}{\displaystyle \{1,2,3,12,18,36\}}الترتيب الجزئي حسب قابلية القسمة ليس شبكة. لكل زوج من العناصر حد أعلى وحد أدنى، لكن الزوج 2، 3 له ثلاثة حدود عليا، وهي 12 و18 و36، ولا يوجد بينها أصغر هذه الحدود الثلاثة في حالة قابلية القسمة (12 و18 لا يقسمان بعضهما). وبالمثل، للزوج 12، 18 ثلاثة حدود دنيا، وهي 1 و2 و3، ولا يوجد بينها أكبر هذه الحدود الثلاثة في حالة قابلية القسمة (2 و3 لا يقسمان بعضهما).

مورفولوجيات الشبكات

الشكل  9: خريطة رتيبةو{\displaystyle f}بين الشبكات التي لا تحافظ على الوصلات ولا على التقاءات، لأنو(u)و(v)=uu=u{\displaystyle f(u)\vee f(v)=u^{\prime }\vee u^{\prime }=u^{\prime }}{\displaystyle \neq }1=و(1)=و(uv){\displaystyle 1^{\prime }=f(1)=f(u\vee v)}وو(u)و(v)=uu=u{\displaystyle f(u)\wedge f(v)=u^{\prime }\wedge u^{\prime }=u^{\prime }}{\displaystyle \neq }0=و(0)=و(uv).{\displaystyle 0^{\prime }=f(0)=f(u\wedge v).}

ينبثق المفهوم المناسب للتشاكل بين شبكتين بسهولة من التعريف الجبري المذكور أعلاه . بالنظر إلى شبكتين(ل،ل،ل){\displaystyle \left(L,\vee _{L},\wedge _{L}\right)}و(م،م،م)،{\displaystyle \left(M,\vee _{M},\wedge _{M}\right),}التشاكل الشبكي من L إلى M هو دالةو:لم{\displaystyle f:L\to M}بحيث يكون ذلك لجميعأ،بل:{\displaystyle a,b\in L:}و(ألب)=و(أ)مو(ب)، و {\displaystyle f\left(a\vee _{L}b\right)=f(a)\vee _{M}f(b),{\text{ and }}}و(ألب)=و(أ)مو(ب).{\displaystyle f\left(a\wedge _{L}b\right)=f(a)\wedge _{M}f(b).}

هكذاو{\displaystyle f}هو تماثل بين نصفي الشبكتين الأساسيتين . عند النظر في الشبكات ذات البنية الأكثر تعقيدًا، يجب أن "تحترم" التماثلات البنية الإضافية أيضًا. على وجه الخصوص، تماثل الشبكة المحدودة (يُسمى عادةً "تماثل الشبكة").و{\displaystyle f}بين شبكتين محدودتينل{\displaystyle L}وم{\displaystyle M}ينبغي أن يتمتع أيضاً بالخاصية التالية: و(0ل)=0م، و {\displaystyle f\left(0_{L}\right)=0_{M},{\text{ and }}}و(1ل)=1م.{\displaystyle f\left(1_{L}\right)=1_{M}.}

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

أي تشاكل بين الشبكات يكون بالضرورة رتيبًا بالنسبة لعلاقة الترتيب المرتبطة به؛ انظر: دالة الحفاظ على النهايات. والعكس غير صحيح: فالرتابة لا تعني بالضرورة الحفاظ على التقاطعات والوصلات (انظر الشكل  9)، مع أن التقابل الحافظ للترتيب يكون تشاكلًا إذا كان معكوسه حافظًا للترتيب أيضًا.

بالنظر إلى التعريف القياسي للتشاكلات باعتبارها تماثلات قابلة للعكس، فإن تشاكل الشبكة هو ببساطة تشاكل شبكي تقابلي . وبالمثل، فإن تشاكل الشبكة الداخلي هو تشاكل شبكي من شبكة إلى نفسها، وتشاكل الشبكة الذاتي هو تشاكل شبكي داخلي تقابلي. تشكل الشبكات وتشاكلاتها فئةً .

يتركل{\displaystyle \mathbb {L} }ول{\displaystyle \mathbb {L} '}ليكن لدينا شبكتان تحتويان على 0 و 1 . تشاكل منل{\displaystyle \mathbb {L} }لل{\displaystyle \mathbb {L} '}يُطلق عليه اسم 0 ، 1 - يفصل إذا وفقط إذاو-1{و(0)}={0}{\displaystyle f^{-1}\{f(0)\}=\{0\}}(و{\displaystyle f}يفصل 0 ) وو-1{و(1)}={1}{\displaystyle f^{-1}\{f(1)\}=\{1\}}(و{\displaystyle f}يفصل 1).

الشبكات الفرعية

شبكة فرعية من شبكةل{\displaystyle L}هي مجموعة فرعية منل{\displaystyle L}هذا عبارة عن شبكة لها نفس عمليات الالتقاء والربط مثلل.{\displaystyle L.} أي إذال{\displaystyle L}هي شبكة وم{\displaystyle M}هي مجموعة فرعية منل{\displaystyle L}بحيث يكون لكل زوج من العناصرأ،بم{\displaystyle a,b\in M}كلاهماأب{\displaystyle a\wedge b}وأب{\displaystyle a\vee b}فيم،{\displaystyle M,}ثمم{\displaystyle M}هي شبكة فرعية منل.{\displaystyle L.}[ 3 ]

شبكة فرعيةم{\displaystyle M}من شبكةل{\displaystyle L}هي شبكة فرعية محدبة منل،{\displaystyle L,}لوxzy{\displaystyle x\leq z\leq y}وx،yم{\displaystyle x,y\in M}يشير ذلك إلى أنz{\displaystyle z}ينتمي إلىم،{\displaystyle M,}لجميع العناصرx،y،zل.{\displaystyle x,y,z\in L.}

خصائص الشبكات

نقدم الآن عدداً من الخصائص المهمة التي تؤدي إلى فئات خاصة مثيرة للاهتمام من الشبكات. وقد سبق مناقشة إحدى هذه الخصائص، وهي خاصية التقييد.

اكتمال

تُسمى المجموعة المرتبة جزئيًا شبكة كاملة إذا كانت جميع مجموعاتها الجزئية تحتوي على وصلة وتقاطع. وعلى وجه الخصوص، كل شبكة كاملة هي شبكة محدودة. في حين أن تشاكلات الشبكات المحدودة تحافظ عمومًا على وصلات وتقاطعات محدودة فقط، فإن تشاكلات الشبكات الكاملة تتطلب الحفاظ على وصلات وتقاطعات عشوائية.

كل مجموعة مرتبة جزئياً تشكل شبه شبكة كاملة هي أيضاً شبكة كاملة. ويرتبط بهذه النتيجة ظاهرة مثيرة للاهتمام، وهي وجود مفاهيم متنافسة متعددة للتشاكل لهذه الفئة من المجموعات المرتبة جزئياً، وذلك تبعاً لما إذا كانت تُعتبر شبكات كاملة، أو أنصاف شبكات كاملة متصلة، أو أنصاف شبكات كاملة متقاطعة، أو شبكات متصلة كاملة أو شبكات متقاطعة كاملة.

إن "الشبكة الجزئية" ليست عكس "الشبكة الكاملة" - بل إن "الشبكة الجزئية" و"الشبكة" و"الشبكة الكاملة" هي تعريفات مقيدة بشكل متزايد.

اكتمال مشروط

الشبكة المشروطة الكاملة هي شبكة يكون فيها لكل مجموعة جزئية غير فارغة ذات حد أعلى حد أدنى (أي حد أعلى أصغر). تُعدّ هذه الشبكات التعميم الأكثر مباشرة لبديهية اكتمال الأعداد الحقيقية . الشبكة المشروطة الكاملة إما أن تكون شبكة كاملة، أو شبكة كاملة بدون عنصرها الأقصى.1،{\displaystyle 1,}عنصرها الأدنى0،{\displaystyle 0,}أو كلاهما. [ 4 ] [ 5 ]

التوزيعية

الشكل  11: أصغر شبكة غير نمطية (وبالتالي غير توزيعية) N 5 .بج{\displaystyle b\leq c}، لكنب(أج)=ب{\displaystyle b\vee (a\wedge c)=b}و(بأ)ج=ج{\displaystyle (b\vee a)\wedge c=c}وبالتالي، فإن قانون التوزيع المعياري يُنتهك. كما أن العناصر المُصنّفة تُخالف معادلة التوزيع.ج(أب)=(جأ)(جب)،{\displaystyle c\wedge (a\vee b)=(c\wedge a)\vee (c\wedge b),}لكن إرضاء ازدواجيتهاج(أب)=(جأ)(جب).{\displaystyle c\vee (a\wedge b)=(c\vee a)\wedge (c\vee b).}
الشكل  10: أصغر شبكة غير توزيعية (ولكنها نمطية) M 3 .

بما أن الشبكات تأتي مع عمليتين ثنائيتين، فمن الطبيعي أن نتساءل عما إذا كانت إحداهما توزع على الأخرى، أي ما إذا كان أحد القانونين الثنائيين التاليين ينطبق على كل ثلاثة عناصرأ،ب،جل،{\displaystyle a,b,c\in L,}:

توزيعية{\displaystyle \vee }زيادة{\displaystyle \wedge }

أ(بج)=(أب)(أج).{\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c).}

توزيعية{\displaystyle \wedge }زيادة{\displaystyle \vee }

أ(بج)=(أب)(أج).{\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c).}

تُسمى الشبكة التي تُحقق البديهية الأولى، أو ما يُكافئها (كما اتضح) البديهية الثانية، شبكةً توزيعية . [ 6 ] الشبكات غير التوزيعية الوحيدة التي تحتوي على أقل من 6 عناصر تُسمى M3 و N5 ؛ [ 7 ] وهما موضحتان في الشكلين 10 و11 على التوالي. تكون الشبكة توزيعية إذا وفقط إذا لم يكن لها شبكة فرعية متماثلة مع M3 أو N5 . [ 8 ] كل شبكة توزيعية متماثلة مع شبكة من المجموعات (حيث الاتحاد والتقاطع هما الربط والالتقاء على التوالي). [ 9 ]

للحصول على نظرة عامة على المفاهيم الأقوى للتوزيعية المناسبة للشبكات الكاملة والتي تستخدم لتعريف فئات أكثر خصوصية من الشبكات مثل الإطارات والشبكات التوزيعية الكاملة ، انظر التوزيعية في نظرية الترتيب .

نمطية التصميم

في بعض التطبيقات، يكون شرط التوزيع قويًا جدًا، وغالبًا ما تكون الخاصية الأضعف التالية مفيدة. شبكة(ل،،){\displaystyle (L,\vee ,\wedge )}تكون الوحدة نمطية إذا، بالنسبة لجميع العناصرأ،ب،جل،{\displaystyle a,b,c\in L,}التطابق التالي صحيح: (أج)(بج)=((أج)ب)ج.{\displaystyle (a\wedge c)\vee (b\wedge c)=((a\wedge c)\vee b)\wedge c.}( الهوية المعيارية ) هذا الشرط يعادل البديهية التالية: أج{\displaystyle a\leq c}يشير إلىأ(بج)=(أب)ج.{\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge c.}( قانون الوحدات النمطية ) في الواقع، المتباينةأ(بج)(أب)ج{\displaystyle a\vee (b\wedge c)\leq (a\vee b)\wedge c}ينطبق في أي شبكة عندماأج{\displaystyle a\leq c}[ 10 ] تكون الشبكة نمطية إذا وفقط إذا لم يكن لها شبكة فرعية متماثلة مع N5 ( كما هو موضح في الشكل 11  ). [ 8 ] بالإضافة إلى الشبكات التوزيعية، تشمل أمثلة الشبكات النمطية شبكة الوحدات الفرعية لوحدة نمطية (ومن هنا جاءت تسميتها نمطية )، وشبكة المثاليّات ثنائية الجانب لحلقة ، وشبكة الزمر الجزئية الطبيعية لزمرة . تُعدّ مجموعة الحدود من الرتبة الأولى التي يكون ترتيبها "أكثر تحديدًا من" شبكة غير نمطية تُستخدم في الاستدلال الآلي .

شبه نمطية

تكون الشبكة المحدودة نمطية إذا وفقط إذا كانت شبه نمطية علوية وسفلية . بالنسبة لشبكة ذات طول محدود، فإن شبه النمطية (العلوية) تُكافئ شرط أن تكون الشبكة متدرجة ودالة رتبتها.ر{\displaystyle r}يستوفي الشرط التالي: [ 11 ]

ر(x)+ر(y)ر(xy)+ر(xy).{\displaystyle r(x)+r(y)\geq r(x\wedge y)+r(x\vee y).}

شرط آخر مكافئ (للشبكات المتدرجة) هو شرط بيركوف :

لكلx{\displaystyle x}وy{\displaystyle y}فيل،{\displaystyle L,}لوx{\displaystyle x}وy{\displaystyle y}كلاهما يغطيxy،{\displaystyle x\wedge y,}ثمxy{\displaystyle x\vee y}يغطي كلا الجانبينx{\displaystyle x}وy.{\displaystyle y.}

تُسمى الشبكة شبه معيارية سفلية إذا كانت شبكتها الثنائية شبه معيارية. بالنسبة للشبكات المحدودة، يعني هذا أن الشروط السابقة تتحقق مع{\displaystyle \vee }و{\displaystyle \wedge }[ 12 ] تم استبدال "يغطي" بـ "يغطيه"، وتم عكس المتباينات.

الاستمرارية والجبرية

في نظرية المجال ، من الطبيعي السعي لتقريب العناصر في ترتيب جزئي بعناصر "أبسط بكثير". يؤدي هذا إلى فئة المجموعات الجزئية المرتبة المتصلة ، والتي تتكون من مجموعات جزئية مرتبة حيث يمكن الحصول على كل عنصر كقيمة عليا لمجموعة موجهة من العناصر التي تقع أسفل ذلك العنصر بكثير. إذا أمكن تقييد هذه المجموعات الموجهة بالعناصر المدمجة في مجموعة جزئية مرتبة للحصول على هذه المجموعات، فإن المجموعة الجزئية المرتبة تصبح جبرية . يمكن تطبيق كلا المفهومين على الشبكات كما يلي:

  • الشبكة المتصلة هي شبكة كاملة متصلة كمجموعة مرتبة جزئياً.
  • الشبكة الجبرية هي شبكة كاملة تكون جبرية كمجموعة مرتبة جزئياً.

تتمتع كلتا الفئتين بخصائص مثيرة للاهتمام. على سبيل المثال، يمكن وصف الشبكات المتصلة بأنها هياكل جبرية (ذات عمليات لا نهائية) تحقق متطابقات معينة. في حين أن هذا الوصف غير معروف للشبكات الجبرية، إلا أنه يمكن وصفها "نحويًا" باستخدام أنظمة معلومات سكوت .

المكملات والمكملات الزائفة

يتركل{\displaystyle L}لتكن شبكة محدودة ذات عنصر أكبر يساوي 1 وعنصر أصغر يساوي 0. عنصرانx{\displaystyle x}وy{\displaystyle y}لل{\displaystyle L}تكون هذه العناصر مكملة لبعضها البعض إذا وفقط إذا: xy=1 و xy=0.{\displaystyle x\vee y=1\quad {\text{ and }}\quad x\wedge y=0.}

بشكل عام، قد لا يكون لبعض عناصر الشبكة المحدودة مكمل، وقد يكون لبعضها الآخر أكثر من مكمل واحد. على سبيل المثال، المجموعة{0،1/2،1}{\displaystyle \{0,1/2,1\}}بترتيبها المعتاد، تُشكل شبكة محدودة، و12{\displaystyle {\tfrac {1}{2}}}ليس له مكمل. في الشبكة المحدودة N 5 ، العنصرأ{\displaystyle a}له مكملان، وهما:ب{\displaystyle b}وج{\displaystyle c}(انظر الشكل  11). تسمى الشبكة المحدودة التي يكون لكل عنصر فيها مكمل شبكة مكملة .

الشبكة المكملة التي تكون أيضًا توزيعية هي جبر بولياني . بالنسبة للشبكة التوزيعية، فإن مكمل الشبكة المكملة هو مكمل الشبكة التوزيعية.x،{\displaystyle x,}عندما يكون موجوداً، يكون فريداً.

في حالة كون المتمم فريدًا، نكتب¬x=y{\textstyle \lnot x=y}وبالمثل،¬y=x.{\textstyle \lnot y=x.}العملية الأحادية المقابلة علىل،{\displaystyle L,}يُطلق عليه اسم التكامل، وهو يُدخل نظيرًا للنفي المنطقي في نظرية الشبكة.

تُعدّ جبريات هيتينغ مثالاً على الشبكات التوزيعية حيث قد تفتقر بعض العناصر إلى العناصر المكملة. كل عنصرz{\displaystyle z}من ناحية أخرى، يمتلك جبر هيتينغ مكملًا زائفًا ، يُشار إليه أيضًا بـ¬x.{\textstyle \lnot x.}المكمل الزائف هو العنصر الأكبرy{\displaystyle y}بحيثxy=0.{\displaystyle x\wedge y=0.}إذا كان المكمل الزائف لكل عنصر من عناصر جبر هيتينغ هو في الواقع مكمل، فإن جبر هيتينغ هو في الواقع جبر بولياني.

حالة سلسلة جوردان-ديديكيند

سلسلة منx0{\displaystyle x_{0}}لxن{\displaystyle x_{n}}هي مجموعة{x0،x1،...،xن}،{\displaystyle \left\{x_{0},x_{1},\ldots ,x_{n}\right\},}أينx0<x1<x2<...<xن.{\displaystyle x_{0}<x_{1}<x_{2}<\ldots <x_{n}.} طول هذه السلسلة هو n ، أي أقل بواحد من عدد عناصرها. وتكون السلسلة قصوى إذاxأنا{\displaystyle x_{i}}أغطيةxأنا-1{\displaystyle x_{i-1}}للجميع1أنان.{\displaystyle 1\leq i\leq n.}

إذا كان ذلك لأي زوج،x{\displaystyle x}وy،{\displaystyle y,}أينx<y،{\displaystyle x<y,}جميع السلاسل القصوى منx{\displaystyle x}لy{\displaystyle y}إذا كان لها نفس الطول، فإن الشبكة يقال إنها تحقق شرط سلسلة جوردان-ديديكيند .

مصنف/مرتب

شبكة(ل،){\displaystyle (L,\leq )}يُطلق عليه اسم المجموعة المتدرجة ، وأحيانًا المرتبة (لكن انظر المجموعة المرتبة جزئيًا لمعنى بديل)، إذا كان من الممكن تزويده بدالة ترتيب.ر:لشمال{\displaystyle r:L\to \mathbb {N} }أحيانًا إلىZ{\displaystyle \mathbb {Z} }متوافق مع الترتيب (لذار(x)<ر(y){\displaystyle r(x)<r(y)}حينماx<y{\displaystyle x<y}) بحيث كلماy{\displaystyle y}أغطيةx،{\displaystyle x,}ثمر(y)=ر(x)+1.{\displaystyle r(y)=r(x)+1.} تُسمى قيمة دالة الرتبة لعنصر الشبكة رتبته .

عنصر شبكيy{\displaystyle y}ويقال إنه يغطي عنصرًا آخرx،{\displaystyle x,}لوy>x،{\displaystyle y>x,}لكن لا يوجدz{\displaystyle z}بحيثy>z>x.{\displaystyle y>z>x.} هنا،y>x{\displaystyle y>x}وسائلxy{\displaystyle x\leq y}وxy.{\displaystyle x\neq y.}

الشبكات الحرة

أي مجموعةX{\displaystyle X}يمكن استخدامها لتوليد الشبكة شبه الحرةFX.{\displaystyle FX.}تُعرَّف الشبكة شبه الحرة بأنها تتكون من جميع المجموعات الجزئية المنتهية منX،{\displaystyle X,}مع عملية شبه الشبكة المعطاة باتحاد المجموعات العادي . تتمتع شبه الشبكة الحرة بالخاصية الشاملة . بالنسبة للشبكة الحرة على مجموعةX،{\displaystyle X,}قدم ويتمان بناءً قائماً على كثيرات الحدود علىX{\displaystyle X}أعضائها . [ 13 ] [ 14 ]

الشبكات المسطحة

أي مجموعة (عادةً متعددة العناصر)X{\displaystyle X}يمكن أيضًا استخدامها لتعريف شبكة مسطحة ، وهي أصغر شبكة تكون فيها عناصر المجموعة غير قابلة للمقارنة، أو بشكل مكافئ، شبكة الرتبة 3 حيثX{\displaystyle X}هي بالضبط مجموعة العناصر ذات الرتبة المتوسطة. [ 15 ]

مفاهيم مهمة في نظرية الشبكة

سنعرّف الآن بعض المفاهيم النظرية المتعلقة بالترتيب ذات الأهمية لنظرية الشبكة. فيما يلي، لنفترضx{\displaystyle x}أن يكون عنصرًا من عناصر شبكة مال.{\displaystyle L.}x{\displaystyle x}يُطلق عليه اسم:

  • انضم إلى غير قابل للاختزال إذاx=أب{\displaystyle x=a\vee b}يشير إلىx=أ أو x=ب.{\displaystyle x=a{\text{ or }}x=b.}للجميعأ،بل.{\displaystyle a,b\in L.}لول{\displaystyle L}يحتوي على عنصر سفلي0،{\displaystyle 0,}بعض المؤلفين يشترطونx0{\displaystyle x\neq 0}[ 16 ] عند تعميم الشرط الأول ليشمل عمليات الربط العشوائيةأناأناأأنا،{\displaystyle \bigvee _{i\in I}a_{i},}x{\displaystyle x}يُطلق عليه اسم الربط غير القابل للاختزال تمامًا (أو{\displaystyle \vee }(غير قابل للاختزال). المفهوم المزدوج هو عدم قابلية الاختزال ({\displaystyle \wedge }(غير قابلة للاختزال). على سبيل المثال، في الشكل  2، العناصر 2 و3 و4 و5 غير قابلة للاختزال بالضم، بينما العناصر 12 و15 و20 و30 غير قابلة للاختزال بالتقاطع. وبحسب التعريف، قد يُعتبر العنصر السفلي 1 غير قابل للاختزال بالضم، والعنصر العلوي 60 غير قابل للاختزال بالتقاطع. في شبكة الأعداد الحقيقية ذات الترتيب المعتاد، كل عنصر غير قابل للاختزال بالضم، ولكن لا يوجد عنصر غير قابل للاختزال بالضم بشكل كامل.
  • انضم إلى برايم إذاxأب{\displaystyle x\leq a\vee b}يشير إلىxأ أو xب.{\displaystyle x\leq a{\text{ or }}x\leq b.}مرة أخرى، بعض المؤلفين يطلبونx0{\displaystyle x\neq 0}على الرغم من أن هذا غير معتاد. [ 17 ] يمكن تعميم هذا أيضًا للحصول على مفهوم العنصر الأولي المشترك تمامًا . المفهوم المقابل هو العنصر الأولي المتقاطع . كل عنصر مشترك أولي هو أيضًا عنصر غير قابل للاختزال المشترك، وكل عنصر متقاطع أولي هو أيضًا عنصر غير قابل للاختزال المتقاطع. ويتحقق العكس إذال{\displaystyle L}توزيعي.

يتركل{\displaystyle L}يحتوي على عنصر سفلي 0. ​​عنصرx{\displaystyle x}لل{\displaystyle L}هي ذرة إذا0<x{\displaystyle 0<x}ولا يوجد عنصرyل{\displaystyle y\in L}بحيث0<y<x.{\displaystyle 0<y<x.}ثمل{\displaystyle L}يُطلق عليه اسم:

  • ذري إذا كان لكل عنصر غير صفريx{\displaystyle x}لل،{\displaystyle L,}توجد ذرةأ{\displaystyle a}لل{\displaystyle L}بحيثأx؛{\displaystyle a\leq x;}[ 18 ]
  • ذري إذا كان كل عنصر منل{\displaystyle L}هو أعلى مستوى للذرات. [ 19 ]

ومع ذلك، تستخدم العديد من المصادر والمجتمعات الرياضية مصطلح "ذري" بمعنى "ذري" كما هو محدد أعلاه.

يشير مفهوما المُثُل ومفهوم المرشحات إلى أنواع محددة من المجموعات الجزئية لمجموعة مرتبة جزئيًا، ولذا فهما مهمان لنظرية الشبكات. يمكن الاطلاع على التفاصيل في المداخل ذات الصلة.

انظر أيضاً

التطبيقات التي تستخدم نظرية الشبكة

لاحظ أنه في العديد من التطبيقات، تكون المجموعات عبارة عن شبكات جزئية فقط: ليس كل زوج من العناصر له نقطة التقاء أو ربط.

ملحوظات

  1. غراتزر 2003 ، ص 52 . 
  2. بيركوف 1948 ، ص 18. "منذ أ=أ(أ(أأ))=أأ{\displaystyle a=a\vee (a\wedge (a\vee a))=a\vee a}و"بشكل مزدوج". ينسب بيركوف هذا إلى ديديكيند 1897 ، ص 8 
  3. بوريس، ستانلي ن.، وسانكابانافار، إتش بي، 1981. دورة في الجبر الشامل . سبرينغر-فيرلاغ. ISBN 3-540-90578-2.
  4. بيكر، كيربي (2010). "الشبكات الكاملة" (ملف PDF) . قسم الرياضيات بجامعة كاليفورنيا في لوس أنجلوس . تم الاطلاع عليه بتاريخ 8 يونيو 2022 .
  5. كابلانسكي، إيرفينغ (1972). نظرية المجموعات والفضاءات المترية ( الطبعة الثانية). مدينة نيويورك: دار نشر تشيلسي التابعة لجمعية الرياضيات الأمريكية . ص 14. ISBN   9780821826942.
  6. بيركوف، غاريت (1967). نظرية الشبكة . الجمعية الرياضية الأمريكية . ص 32. 
  7. Davey & Priestley (2002) harvtxt error: multiple targets (2×): CITEREFDaveyPriestley2002 ( help ) , Exercise 4.1, p.  104 .
  8. 1 2 Davey & Priestley (2002) harvtxt error: multiple targets (2×): CITEREFDaveyPriestley2002 ( help ) , Theorem 4.10, p.  89 .
  9. Davey & Priestley (2002) خطأ harvtxt: أهداف متعددة (2×): CITEREFDaveyPriestley2002 ( مساعدة ) ، النظرية 10.21 ، ص  238-239 .
  10. ديفي، بكالوريوس؛ بريستلي، هيلاري (2002). مقدمة في الشبكات والترتيب ( الطبعة الثانية). كامبريدج: مطبعة جامعة كامبريدج. اللمة 4.1. ISBN  978-0-511-80908-8.
  11. بيركوف، غاريت (1967). نظرية الشبكات ( الطبعة الثالثة). بروفيدنس: الجمعية الرياضية الأمريكية. النتيجة 1 في القسم الرابع.1 والنظريتان 14 و15 في القسم الثاني.8. ISBN  9780821810255.
  12. ستانلي، ريتشارد ب. (1997)، التوافقية العددية (المجلد 1) ، مطبعة جامعة كامبريدج، الصفحات 103-104 ، رقم ISBN  0-521-66351-2
  13. فيليب ويتمان (1941). "الشبكات الحرة 1". حوليات الرياضيات . 42 (1): 325-329 . doi : 10.2307/1969001 . JSTOR 1969001 . 
  14. فيليب ويتمان (1942). "الشبكات الحرة II". حوليات الرياضيات . 43 (1): 104-115 . doi : 10.2307/1968883 . JSTOR 1968883 . 
  15. ^ برينك ، كريس. كال، ولفرام. شميت ، غونتر (23 أبريل 1997). الأساليب العلائقية في علوم الكمبيوتر . فيينا، النمسا: سبرينغر فيينا. ص. 127. ردمك  978-3-211-82971-4.
  16. ديفي وبريستلي 2002 ، ص 53. خطأ في رقم المرجع: أهداف متعددة (2×): CITEREFDaveyPriestley2002 ( مساعدة )
  17. هوفمان، رودولف-إي. (1981). المجموعات المرتبة جزئيًا المتصلة، والأطياف الأولية للشبكات الكاملة التوزيعية تمامًا، وتكثيفات هاوسدورف . الشبكات المتصلة. المجلد 871. الصفحات 159-208 . doi : 10.1007/BFb0089907 .  
  18. غراتزر 2003 ، ص 246، التمرين 3.
  19. غراتزر 2003 ، ص 234، بعد التعريف 1.

مراجع

تتوفر الدراسات المتخصصة مجاناً عبر الإنترنت:

  • بوريس، ستانلي ن.، وسانكابانافار، إتش بي، 1981. دورة في الجبر الشامل. سبرينغر-فيرلاغ. ISBN 3-540-90578-2.
  • جيبسن، بيتر، وهنري روز، أنواع الشبكات ، سلسلة محاضرات في الرياضيات 1533، دار نشر سبرينغر، 1992. ISBN 0-387-56314-8.

نصوص تمهيدية موصى بها لمن لديهم مستوى محدود من النضج الرياضي :

  • دونيلان، توماس، 1968. نظرية الشبكة . بيرغامون.
  • غراتزر، جورج ، 1971. نظرية الشبكة: المفاهيم الأولى والشبكات التوزيعية . دبليو إتش فريمان.

النص التمهيدي المعاصر القياسي، وهو أصعب قليلاً من النص المذكور أعلاه:

دراسات متقدمة:

على الشبكات الحرة:

حول تاريخ نظرية الشبكة:

حول تطبيقات نظرية الشبكة:

  • غاريت بيركوف (1967). جيمس سي. أبوت (محرر). ما الذي يمكن أن تقدمه لك الشبكات؟ فان نوستراند.جدول المحتويات