غرافون

خذ سلسلة من${\displaystyle (G_{n})}$الرسوم البيانية العشوائية لإردوش-ريني${\displaystyle G_{n}=G(n,p)}$مع بعض المعلمات الثابتة${\displaystyle p}$بشكل بديهي، كما${\displaystyle n}$عندما يؤول العدد إلى اللانهاية، فإن نهاية هذه المتتالية من الرسوم البيانية تُحدد فقط بكثافة حواف هذه الرسوم البيانية. في فضاء الجرافونات، يتضح أن هذه المتتالية تتقارب بشكل شبه مؤكد إلى قيمة ثابتة.${\displaystyle W(x,y)\equiv p}$وهذا ما يجسد الحدس المذكور أعلاه.

خذ التسلسل${\displaystyle (H_{n})}$من الرسوم البيانية النصفية ، المعرفة بأخذ${\displaystyle H_{n}}$أن يكون الرسم البياني ثنائي الأجزاء على${\displaystyle 2n}$الرؤوس${\displaystyle u_{1},u_{2},\dots ,u_{n}}$و${\displaystyle v_{1},v_{2},\dots ,v_{n}}$بحيث${\displaystyle u_{i}}$يقع بجوار${\displaystyle v_{j}}$متى بالضبط${\displaystyle i\leq j}$إذا تم سرد الرؤوس بالترتيب الموضح، فإن مصفوفة التجاور${\displaystyle A_{H_{n}}}$تحتوي مصفوفة التجاور على ركنين من أركان مصفوفة "نصف المربع" مملوءين بالآحاد، بينما بقية العناصر تساوي صفرًا. على سبيل المثال، مصفوفة التجاور لـ${\displaystyle H_{3}}$يُعطى بواسطة

$${\displaystyle {\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.}$$

مثل${\displaystyle n}$عندما تكبر هذه الزوايا، تصبح أكثر نعومة. وتوافقًا مع هذا الحدس، فإن التسلسل${\displaystyle (H_{n})}$يتقارب إلى نصف الجرافون${\displaystyle W}$محدد بواسطة${\displaystyle W(x,y)=1}$متى${\displaystyle |x-y|\geq 1/2}$و${\displaystyle W(x,y)=0}$خلاف ذلك.

خذ التسلسل${\displaystyle (K_{n,n})}$للرسوم البيانية الثنائية الكاملة ذات الأجزاء المتساوية الحجم. إذا رتبنا الرؤوس بوضع جميع رؤوس أحد الأجزاء في البداية ووضع رؤوس الجزء الآخر في النهاية، فإن مصفوفة التجاور لـ${\displaystyle (K_{n,n})}$تبدو كمصفوفة غير قطرية كتلية، تتكون من كتلتين من الواحدات وكتلتين من الأصفار. على سبيل المثال، مصفوفة التجاور لـ${\displaystyle K_{2,2}}$يُعطى بواسطة

$${\displaystyle {\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.}$$

مثل${\displaystyle n}$كلما كبرت، يظل هذا الهيكل الكتلي لمصفوفة التجاور ثابتًا، بحيث يتقارب هذا التسلسل من الرسوم البيانية إلى رسم بياني "ثنائي الأجزاء كامل".${\displaystyle W}$ محدد بواسطة${\displaystyle W(x,y)=1}$حينما${\displaystyle \min(x,y)\leq 1/2}$و${\displaystyle \max(x,y)>1/2}$، والضبط${\displaystyle W(x,y)=0}$خلاف ذلك.

إذا قمنا بدلاً من ذلك بترتيب رؤوس${\displaystyle K_{n,n}}$من خلال التناوب بين الأجزاء، تتخذ مصفوفة التجاور بنية رقعة الشطرنج المكونة من أصفار ووحدات. على سبيل المثال، في ظل هذا الترتيب، تكون مصفوفة التجاور لـ${\displaystyle K_{2,2}}$يُعطى بواسطة

$${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.}$$

مثل${\displaystyle n}$كلما كبرت المصفوفة، أصبحت مصفوفات التجاور أدق فأدق، أشبه برقعة شطرنج. على الرغم من هذا السلوك، ما زلنا نريد الوصول إلى الحد الأقصى لـ${\displaystyle (K_{n,n})}$أن تكون فريدة وتؤدي إلى الرسم البياني من المثال 3. وهذا يعني أنه عندما نحدد رسميًا التقارب لتسلسل من الرسوم البيانية، يجب أن يكون تعريف النهاية غير متأثر بإعادة تسمية الرؤوس.

خذ سلسلة عشوائية${\displaystyle (G_{n})}$ل${\displaystyle W}$- رسم بياني عشوائي${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$بالنسبة لبعض الجرافون الثابت${\displaystyle W}$ثم كما في المثال الأول من هذا القسم، اتضح أن${\displaystyle (G_{n})}$يتقارب إلى${\displaystyle W}$بالتأكيد تقريباً.

إحدى طرق قياس المسافة بين رسمين بيانيين${\displaystyle G}$و${\displaystyle H}$يتمثل الهدف في مقارنة عدد الرسوم البيانية الفرعية النسبية لكل رسم بياني. أي، لكل رسم بياني${\displaystyle F}$يمكننا مقارنة عدد نسخ${\displaystyle F}$في${\displaystyle G}$و${\displaystyle F}$في${\displaystyle H}$إذا كانت هذه الأرقام متقاربة في كل رسم بياني${\displaystyle F}$ثم بشكل بديهي${\displaystyle G}$و${\displaystyle H}$هي رسوم بيانية متشابهة ظاهريًا. ولكن بدلًا من التعامل مباشرةً مع الرسوم البيانية الفرعية، يتضح أن التعامل مع تماثلات الرسوم البيانية أسهل. وهذا مناسب عند التعامل مع الرسوم البيانية الكبيرة والكثيفة، لأنه في هذه الحالة يتساوى عدد الرسوم البيانية الفرعية وعدد تماثلات الرسوم البيانية من رسم بياني ثابت تقريبًا.

بالنظر إلى رسمين بيانيين${\displaystyle F}$و${\displaystyle G}$كثافة التشاكل ${\displaystyle t(F,G)}$ل${\displaystyle F}$في${\displaystyle G}$يُعرَّف بأنه عدد التشاكلات البيانية من${\displaystyle F}$ل${\displaystyle G}$. بعبارة أخرى،${\displaystyle t(F,G)}$هل احتمال اختيار خريطة عشوائية من رؤوس${\displaystyle F}$إلى رؤوس${\displaystyle G}$يرسل الرؤوس المجاورة إلى${\displaystyle F}$إلى الرؤوس المجاورة في${\displaystyle G}$.

توفر الرسوم البيانية طريقة بسيطة لحساب كثافات التشاكل. في الواقع، بالنظر إلى رسم بياني${\displaystyle G}$مع الجرافون المرتبط به${\displaystyle W_{G}}$وآخر${\displaystyle F}$لدينا

$${\displaystyle t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

حيث يكون التكامل متعدد الأبعاد، ويتم حسابه على مكعب الوحدة الفائق.${\displaystyle [0,1]^{V(F)}}$وينتج هذا من تعريف الرسم البياني المرتبط، وذلك بالنظر إلى متى يكون التكامل المذكور أعلاه مساوياً لـ${\displaystyle 1}$يمكننا بعد ذلك توسيع تعريف كثافة التشاكل ليشمل الرسوم البيانية العشوائية${\displaystyle W}$باستخدام نفس التكامل وتعريف

$${\displaystyle t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

لأي رسم بياني${\displaystyle F}$.

بناءً على هذا الإعداد، نقول سلسلة من الرسوم البيانية${\displaystyle (G_{n})}$تكون متقاربة من اليسار إذا كان لكل رسم بياني ثابت${\displaystyle F}$، سلسلة كثافات التماثل${\displaystyle \left(t(F,G_{n})\right)}$يتقارب. على الرغم من أن ذلك ليس واضحًا من التعريف وحده، إذا${\displaystyle (G_{n})}$ إذا تقاربت بهذا المعنى، فإنه يوجد دائمًا رسم بياني${\displaystyle W}$بحيث يكون لكل رسم بياني${\displaystyle F}$لدينا $${\displaystyle \lim _{n\to \infty }t(F,G_{n})=t(F,W)}$$ معًا.

خذ رسمين بيانيين${\displaystyle G}$و${\displaystyle H}$على نفس مجموعة الرؤوس. ولأن هذه الرسوم البيانية تشترك في نفس الرؤوس، فإن إحدى طرق قياس المسافة بينها هي الاقتصار على مجموعات فرعية.${\displaystyle X,Y}$من مجموعة الرؤوس، ولكل زوج من هذه المجموعات الفرعية، قارن عدد الحواف${\displaystyle e_{G}(X,Y)}$من${\displaystyle X}$ل${\displaystyle Y}$في${\displaystyle G}$إلى عدد الحواف${\displaystyle e_{H}(X,Y)}$بين${\displaystyle X}$و${\displaystyle Y}$في${\displaystyle H}$إذا كانت هذه الأرقام متشابهة لكل زوج من المجموعات الجزئية (مقارنةً بالعدد الإجمالي للرؤوس)، فهذا يشير إلى${\displaystyle G}$و${\displaystyle H}$هي رسوم بيانية متشابهة.

كصياغة أولية لمفهوم المسافة هذا، لأي زوج من الرسوم البيانية${\displaystyle G}$و${\displaystyle H}$على نفس مجموعة الرؤوس${\displaystyle V}$من الحجم${\displaystyle |V|=n}$حدد مسافة القطع المحددة بين${\displaystyle G}$و${\displaystyle H}$يكون

$${\displaystyle d_{\square }(G,H)={\frac {1}{n^{2}}}\max _{X,Y\subseteq V}\left|e_{G}(X,Y)-e_{H}(X,Y)\right|.}$$

بمعنى آخر، تُشفّر مسافة القطع المُصنّفة أقصى تباين في كثافات الحواف بين${\displaystyle G}$و${\displaystyle H}$يمكننا تعميم هذا المفهوم على الجرافونات من خلال التعبير عن كثافة الحواف${\displaystyle {\tfrac {1}{n^{2}}}e_{G}(X,Y)}$من حيث الجرافون المرتبط${\displaystyle W_{G}}$مما يؤدي إلى المساواة

$${\displaystyle d_{\square }(G,H)=\max _{X,Y\subseteq V}\left|\int _{I_{X}}\int _{I_{Y}}W_{G}(x,y)-W_{H}(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$

أين${\displaystyle I_{X},I_{Y}\subseteq [0,1]}$هي اتحادات من فترات زمنية تتوافق مع الرؤوس في${\displaystyle X}$و${\displaystyle Y}$لاحظ أنه لا يزال من الممكن استخدام هذا التعريف حتى عندما لا تشترك الرسوم البيانية التي تتم مقارنتها في مجموعة رؤوس واحدة. وهذا ما يحفز التعريف الأكثر عمومية التالي.

التعريف 1. لأي دالة متناظرة وقابلة للقياس${\displaystyle f:[0,1]^{2}\to \mathbb {R} }$، عرّف معيار القطع لـ${\displaystyle f}$أن تكون الكمية

$${\displaystyle \lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$ تم الاستحواذ على جميع المجموعات الفرعية القابلة للقياس${\displaystyle S,T}$من الفترة الوحدوية. ^{[ 6 ]}

وهذا يجسد مفهومنا السابق لمسافة القطع المصنفة، حيث لدينا المساواة${\displaystyle \lVert W_{G}-W_{H}\rVert _{\square }=d_{\square }(G,H)}$.

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

التعريف 2. لأي زوج من الجرافونات${\displaystyle U}$و${\displaystyle W}$، حدد مسافة القطع الخاصة بهم لتكون

$${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}$$ أين${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$هو تكوين${\displaystyle W}$مع الخريطة${\displaystyle \varphi }$ويتم أخذ الحد الأدنى على جميع التقابلات التي تحافظ على القياس من الفترة 1 إلى نفسها. ^{[ 8 ]}

تُعرَّف مسافة القطع بين رسمين بيانيين بأنها مسافة القطع بين الرسوم البيانية المرتبطة بهما.

نقول الآن إن سلسلة من الرسوم البيانية${\displaystyle (G_{n})}$تكون المتتابعة متقاربة تحت مسافة القطع إذا كانت متتالية كوشي تحت مسافة القطع${\displaystyle \delta _{\square }}$على الرغم من أن هذا ليس نتيجة مباشرة للتعريف، فإذا كانت سلسلة من هذه الرسوم البيانية كوشي، فإنها تتقارب دائمًا إلى رسم بياني ما.${\displaystyle W}$.

وكما اتضح، بالنسبة لأي سلسلة من الرسوم البيانية${\displaystyle (G_{n})}$، التقارب من اليسار يعادل التقارب تحت مسافة القطع، وعلاوة على ذلك، فإن الرسم البياني الحدي${\displaystyle W}$الأمر سيان. يمكننا أيضًا النظر في تقارب الرسوم البيانية نفسها باستخدام التعريفات نفسها، ويبقى التكافؤ نفسه صحيحًا. في الواقع، يرتبط مفهوما التقارب ارتباطًا أقوى من خلال ما يُسمى بـ" مسلمات العد" . ^{[ 6 ]}

معضلة العد. لأي زوج من الجرافونات${\displaystyle U}$و${\displaystyle W}$لدينا

$${\displaystyle |t(F,U)-t(F,W)|\leq e(F)\delta _{\square }(U,W)}$$ لجميع الرسوم البيانية${\displaystyle F}$.

يأتي اسم "مبدأ العد" من الحدود التي يقدمها هذا المبدأ على كثافات التشاكل.${\displaystyle t(F,W)}$وهي مماثلة لعدد الرسوم البيانية الفرعية للرسوم البيانية. هذه اللمة هي تعميم للّمة عدّ الرسوم البيانية التي تظهر في مجال تقسيمات الانتظام ، وتُظهر مباشرةً أن التقارب تحت مسافة القطع يستلزم التقارب من اليسار.

معضلة العد العكسي. لكل عدد حقيقي${\displaystyle \varepsilon >0}$يوجد عدد حقيقي${\displaystyle \eta >0}$وعدد صحيح موجب${\displaystyle k}$بحيث يكون لأي زوج من الجرافونات${\displaystyle U}$و${\displaystyle W}$مع

$${\displaystyle |t(F,U)-t(F,W)|\leq \eta }$$ لجميع الرسوم البيانية${\displaystyle F}$مُرضٍ${\displaystyle v(F)\leq k}$يجب أن يكون لدينا${\displaystyle \delta _{\square }(U,W)<\varepsilon }$.

تُظهر هذه اللمة أن التقارب من اليسار يستلزم التقارب تحت مسافة القطع.