المطابقة في الرسوم البيانية الفائقة

في نظرية المخططات ، يُعرَّف التطابق في المخطط الفائق بأنه مجموعة من الحواف الفائقة ، حيث تكون كل حافتين فائقتين منفصلتين . وهو امتداد لمفهوم التطابق في المخطط . ^{[ 1 ]}^{: 466-470}^{[ 2 ]}

تعريف

تذكر أن الرسم البياني الفائق $H$ هو زوج $(V ، E)$ ، حيث $V$ هي مجموعة من الرؤوس و $E$ هي مجموعة من المجموعات الجزئية من $V$ تسمى الحواف الفائقة . قد تحتوي كل حافة فائقة على رأس واحد أو أكثر.

التطابق في $H$ هو مجموعة جزئية $M$ من $E$ ، بحيث يكون لكل حافتين فائقتين $e 1 و e 2 في M$ $تقاطع$ $فارغ$ ( لا $يوجد$ رأس $مشترك$ بينهما).

عدد التطابقات في الرسم البياني الفائق $H$ هو أكبر حجم للتطابق في $H.$ ويُرمز إليه غالبًا بـ $ν(H)$ . ^{[ 1 ]}^{: 466}^{[ 3 ]}

كمثال، لنفترض أن $V$ هي المجموعة ${1، 2، 3، 4، 5، 6، 7}.$ لنعتبر مخططًا فائقًا منتظمًا ثلاثيًا على $V$ (مخططًا فائقًا يحتوي كل ضلع فيه على 3 رؤوس بالضبط). ولنفترض أن $H$ هو مخطط فائق منتظم ثلاثيًا يحتوي على 4 أضلاع:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

ثم يقبل $H$ عدة تطابقات بحجم 2، على سبيل المثال:

{ {1,2,3}, {4,5,6} }

{ {1,4,5}, {2,3,6} }

ومع ذلك، في أي مجموعة فرعية من 3 حواف فائقة، يتقاطع اثنان منها على الأقل، لذلك لا يوجد تطابق بحجم 3. وبالتالي، فإن عدد التطابقات لـ $H$ هو 2.

رسم بياني متقاطع

يُطلق على الرسم البياني الفائق $H = (V, E) اسم$ الرسم البياني المتقاطع إذا كان لكل ضلعين فائقين في $E$ رأس مشترك. ويكون الرسم البياني الفائق $H$ متقاطعًا إذا وفقط إذا لم يكن له تطابق مع ضلعين فائقين أو أكثر، إذا وفقط إذا كان $ν(H) =$ 1. ^{[ 4 ]}

المطابقة في الرسم البياني كحالة خاصة

الرسم البياني الخالي من الحلقات الذاتية هو ببساطة رسم بياني فائق ثنائي التماثل: يمكن اعتبار كل حافة مجموعة من الرأسين اللذين تربطهما. على سبيل المثال، يمثل هذا الرسم البياني الفائق ثنائي التماثل رسمًا بيانيًا بأربعة رؤوس ${1، 2، 3، 4}$ وثلاث حواف.

{ {1,3}, {1,4}, {2,4} }

بحسب التعريف أعلاه، فإن التطابق في الرسم البياني هو مجموعة $M$ من الحواف، بحيث يكون لكل حافتين في $M$ تقاطع فارغ. وهذا يكافئ القول بأنه لا توجد حافتان في $M$ متجاورتان مع نفس الرأس؛ وهذا هو تعريف التطابق في الرسم البياني تحديدًا .

المطابقة الجزئية

المطابقة الجزئية في الرسم البياني الفائق هي دالة تُسند كسرًا في الفترة $[0,1]$ لكل حافة فائقة، بحيث يكون مجموع كسور الحواف الفائقة التي تحتوي على $v$ لكل رأس $v$ في $V$ على الأكثر 1. المطابقة هي حالة خاصة من المطابقة الجزئية حيث تكون جميع الكسور إما 0 أو 1. حجم المطابقة الجزئية هو مجموع كسور جميع الحواف الفائقة.

عدد المطابقة الجزئية للرسم البياني الفائق $H$ هو أكبر حجم للمطابقة الجزئية في $H.$ وغالبًا ما يُرمز إليه بـ $ν *(H)$ . ^{[ 3 ]}

بما أن المطابقة هي حالة خاصة من المطابقة الجزئية، فإنه لكل رسم بياني فائق $H$ :

رقم المطابقة ( $H$ ) ≤ رقم المطابقة الجزئي ( $H$ )

يُكتب هذا المبدأ رمزياً على النحو التالي:

\nu (H)\leq \nu ^{*}(H)

بشكل عام، قد يكون عدد التطابقات الجزئية أكبر من عدد التطابقات الكلي. وتقدم نظرية زولتان فوريدي ^{[ 4 ]} حدودًا عليا لنسبة عدد التطابقات الجزئية ( $H$ ) إلى عدد التطابقات الكلي ( $H$ ):

إذا كان كل ضلع فائق في $H$ يحتوي على $r$ رأس على الأكثر، فإن

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$

على وجه الخصوص، في رسم بياني بسيط: ^{[ 5 ]}

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$

المتباينة دقيقة: ليكن H $ r$ $$ المستوى الإسقاطي المحدود المنتظم من الرتبة r . عندئذٍ، $ν (H$ $r) = 1 لأن كل ضلعين فائقين يتقاطعان، وν*(Hr) = r - 1 + 1$ $/$ $r$ وفقًا $للمطابقة الجزئية التي تُسند وزنًا مقداره 1$ $/$ $r$ $لكل$ $ضلع$ $فائق$ ( $وهي$ $مطابقة$ $لأن$ $كل$ رأس مُحتوى في $r$ ضلعًا فائقًا، وحجمه $r$ $- 1 +$ $1$ $/$ $r$ لوجود $r$ $2$ $-$ $r$ $+$ $1 ضلعًا فائقًا$ $) . لذلك$ $،$ فإن النسبة هي بالضبط $r$ $- 1 +$ $1$ $/$ $r$ $.$
إذا كانت قيمة $r$ بحيث لا يوجد مستوى إسقاطي محدود منتظم من الدرجة $r (على سبيل المثال،$ $r$ $= 7$ )، فإن متباينة أقوى تتحقق:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

إذا كانت $H مقسمة إلى$ $r$ أجزاء (حيث يتم تقسيم الرؤوس إلى $r$ أجزاء ويحتوي كل ضلع فائق على رأس من كل جزء)، فإن:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

على وجه الخصوص، في الرسم البياني ثنائي الأجزاء، $ν *(H) = ν (H)$ . وقد أثبت ذلك أندراس غيارفاس . ^{[ 4 ]}

المتباينة حادة: ليكن $H r-$ هو المستوى الإسقاطي المقتطع من الرتبة $r - 1.$ عندئذٍ $ν (H r -) = 1$ لأن كل حافتين فائقتين تتقاطعان، و $ν *(H r -$ $)$ $=$ $r$ $- 1 من خلال المطابقة الجزئية$ $التي$ تُسند وزنًا قدره $1$ $/$ $r$ لكل حافة فائقة (يوجد $r$ $2$ $-$ $r$ حافة فائقة).

تطابق مثالي

يُطلق على التطابق $M اسم$ التطابق التام إذا كان كل رأس $v$ في $V$ موجودًا في حافة فائقة واحدة فقط من $M.$ وهذا هو الامتداد الطبيعي لمفهوم التطابق التام في الرسم البياني.

يُطلق على التطابق الجزئي $M اسم$ التطابق الكامل إذا كان مجموع كسور الحواف الفائقة في $M$ التي تحتوي على $v$ يساوي 1 بالضبط لكل رأس $v$ في $V.$

لنفترض وجود مخطط فائق $H$ يحتوي كل ضلع فائق فيه على $n$ رأسًا على الأكثر. إذا كان $H$ يقبل مطابقة جزئية مثالية، فإن عدد المطابقة الجزئية فيه يكون على الأقل $| V | / n$ . إذا كان كل ضلع فائق في $H$ يحتوي على $n$ رأسًا بالضبط، فإن عدد المطابقة الجزئية فيه يكون بالضبط $|$ $V$ $|$ $/$ $n$ . ^[⁶^]^:^{القسم 2.} هذا تعميم لحقيقة أن حجم المطابقة المثالية في المخطط هو $|$ $V$ $|$ $/$ $2$ .

بالنظر إلى مجموعة $V$ من الرؤوس، فإن مجموعة $E$ من المجموعات الفرعية لـ $V$ تسمى متوازنة إذا كان الرسم البياني الفائق $(V ، E)$ يقبل مطابقة كسرية مثالية.

على سبيل المثال، إذا كانت $V = {1,2,3,a,b,c}$ و $E = { {1,a}, {2,a}, {1,b}, {2,b}, {3,c} }،$ فإن $E$ متوازنة، مع المطابقة الكسرية المثالية ${ 1/2, 1/2, 1/2, 1/2, 1 }.$

توجد شروط كافية متعددة لوجود تطابق تام في الرسم البياني الفائق:

نظريات من نوع هول للرسوم البيانية الفائقة - تقدم شروطًا كافية مماثلة لنظرية هول للزواج ، استنادًا إلى مجموعات من الجيران.
المطابقة المثالية في الرسوم البيانية الفائقة ذات الدرجة العالية - تقدم شروطًا كافية مماثلة لنظرية ديراك حول الدورات الهاميلتونية ، بناءً على درجة الرؤوس.
قام كل من كيفاش ومايكروفت بتطوير نظرية هندسية لمطابقة الرسوم البيانية الفائقة. ^{[ 7 ]}

مجموعة متوازنة - عائلة

تُسمى عائلة المجموعات $E$ فوق مجموعة أساسية $V$ متوازنة (بالنسبة إلى $V$ ) إذا كان الرسم البياني الفائق $H = (V, E)$ يقبل مطابقة كسرية مثالية. ^{[ 6 ]}^{: القسم 2}

على سبيل المثال، لنفترض مجموعة الرؤوس $V = {1,2,3,a,b,c}$ ومجموعة الحواف $E = {1-a, 2-a, 1-b, 2-b, 3-c}. تُعتبر$ $E$ متوازنة، حيث يوجد تطابق كسري مثالي بأوزان ${1/2, 1/2, 1/2, 1/2, 1}.$

حساب المطابقة القصوى

مشكلة إيجاد تطابق ذي عدد عناصر أقصى في الرسم البياني الفائق، وبالتالي حساب $\nu (H)$ تُعدّ هذه المسألة صعبة الحل من نوع NP حتى بالنسبة للرسوم البيانية الفائقة ثلاثية التماثل (انظر المطابقة ثلاثية الأبعاد ). وهذا على عكس حالة الرسوم البيانية البسيطة (ثنائية التماثل) حيث يمكن حساب مطابقة ذات عدد عناصر أقصى في وقت متعدد الحدود.

المطابقة والتغطية

غطاء الرؤوس في الرسم البياني الفائق $H = (V, E)$ هو مجموعة جزئية $T$ من $V$ ، بحيث يحتوي كل ضلع فائق في $E$ على رأس واحد على الأقل من $T$ (يُسمى أيضًا مجموعة مستعرضة أو مجموعة ضاربة ، وهو مكافئ لغطاء المجموعة ). وهو تعميم لمفهوم غطاء الرؤوس في الرسم البياني.

عدد تغطية الرؤوس للرسم البياني الفائق $H$ هو أصغر حجم لتغطية الرؤوس في $H.$ وغالبًا ما يُرمز إليه بـ $τ (H)$ ، ^{[ 1 ]}^{: 466} للعرض.

الغطاء الرأسي الجزئي هو دالة تُسند وزنًا لكل رأس في $V$ ، بحيث يكون مجموع كسور الرؤوس في كل حافة فائقة $e$ في $E$ أكبر $من$ أو يساوي 1. الغطاء الرأسي هو حالة خاصة من الغطاء الرأسي الجزئي حيث تكون جميع الأوزان إما 0 أو 1. حجم الغطاء الرأسي الجزئي هو مجموع كسور جميع الرؤوس.

يُعرف عدد تغطية الرؤوس الجزئية للرسم البياني الفائق $H$ بأنه أصغر حجم لتغطية الرؤوس الجزئية في $H.$ وغالبًا ما يُرمز إليه بـ $τ *(H)$ .

بما أن غطاء الرؤوس هو حالة خاصة من غطاء الرؤوس الجزئي، فإنه لكل رسم بياني فائق $H$ :

رقم تغطية الرؤوس الجزئي ( $H$ ) ≤ رقم تغطية الرؤوس ( $H$ ).

تُشير ثنائية البرمجة الخطية إلى أنه، لكل رسم بياني فائق $H$ :

عدد المطابقة الجزئي ( $H$ ) = عدد تغطية الرأس الجزئي ( $H$ ).

وبالتالي، لكل رسم بياني فائق $H$ : ^{[ 4 ]}

\nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H)\leq \tau (H)

إذا كان حجم كل حافة فائقة في $H$ لا يتجاوز $r،$ فإن اتحاد جميع الحواف الفائقة في المطابقة القصوى يمثل غطاءً للرؤوس (لو كانت هناك حافة فائقة غير مغطاة، لكان بإمكاننا إضافتها إلى المطابقة). لذلك:

\tau (H)\leq r\cdot \nu (H).

هذا التباين محكم: المساواة تتحقق، على سبيل المثال، عندما تحتوي $V على$ $r \cdot ν (H) + r - 1$ رؤوس وتحتوي $E$ على جميع المجموعات الفرعية من $r$ رؤوس.

ومع ذلك، بشكل عام $τ *(H) < r \cdot ν (H)$ ، لأن $ν *(H) < r \cdot ν (H)$ ؛ انظر المطابقة الجزئية أعلاه.

تقول فرضية رايزر أنه في كل $رسم بياني فائق موحد من النوع$ $r$ -partite:

\tau (H)\leq (r-1)\nu (H).

تم إثبات بعض الحالات الخاصة من التخمين؛ انظر تخمين رايزر .

ممتلكات كونيغ

تتمتع الرسوم البيانية الفائقة بخاصية كونيغ إذا كان أكبر عدد من التطابقات يساوي أصغر عدد من تغطية الرؤوس، أي إذا كان $ν (H) = τ (H)$ . تُبين نظرية كونيغ-إغرفاري أن كل رسم بياني ثنائي الأجزاء يتمتع بخاصية كونيغ. لتوسيع هذه النظرية لتشمل الرسوم البيانية الفائقة، نحتاج إلى توسيع مفهوم ثنائية الأجزاء ليشمل الرسوم البيانية الفائقة. ^{[ 1 ]}^{: 468}

يُمكن تعميم ذلك بشكل طبيعي كما يلي: يُطلق على الرسم البياني الفائق اسم "قابل للتلوين الثنائي" إذا أمكن تلوين رؤوسه بلونين بحيث يحتوي كل ضلع فائق (بحجم 2 على الأقل) على رأس واحد على الأقل من كل لون. يُعرف هذا المصطلح أيضًا باسم " الخاصية ب" . الرسم البياني البسيط ثنائي الأجزاء إذا وفقط إذا كان قابلاً للتلوين الثنائي. مع ذلك، توجد رسوم بيانية فائقة قابلة للتلوين الثنائي دون تطبيق خاصية كونيغ. على سبيل المثال، لنفترض الرسم البياني الفائق $V = {1,2,3,4}$ حيث جميع الثلاثيات $E = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }.$ هذا الرسم البياني قابل للتلوين الثنائي، فعلى سبيل المثال، يُمكننا تلوين ${1,2}$ باللون الأزرق و ${3,4}$ باللون الأبيض. مع ذلك، فإن عدد التطابقات فيه هو 1 وعدد تغطية الرؤوس هو 2.

يُمكن تعميم ذلك على النحو التالي: إذا كان لدينا مخطط فائق $H = (V, E) ومجموعة جزئية V' من V، فإن تقييد H$ $على V' هو المخطط الفائق$ الذي $رؤوسه$ V $،$ ولكل حافة فائقة e $في$ E $تتقاطع$ مع $V$ ' $،$ فإنه $يحتوي$ على حافة فائقة $e'$ تمثل تقاطع $e$ و $V'$ . يُسمى المخطط الفائق متوازنًا إذا كانت جميع قيوده قابلة للتلوين بلونين بشكل أساسي ، أي أننا نتجاهل الحواف الفائقة المفردة في التقييد. ^[⁸^] يكون المخطط البسيط ثنائي الأجزاء إذا وفقط إذا كان متوازنًا.

يكون الرسم البياني البسيط ثنائي الأجزاء إذا وفقط إذا لم يحتوي على دورات فردية الطول. وبالمثل، يكون الرسم البياني الفائق متوازنًا إذا وفقط إذا لم يحتوي على دوائر فردية الطول $.$ $الدائرة$ $ذات$ $الطول k في الرسم البياني الفائق هي متتالية متناوبة (v₁, e₁, v₂, e₂, \dots, vₖ, eₖ, vₖ₊₁$ = v₁ $)$ ، $حيث تمثل vᵢ رؤوسًا مختلفة ، وتمثل eᵢ حوافًا فائقة مختلفة ، وتحتوي كل حافة فائقة على الرأس الموجود على$ يسارها $والرأس$ الموجود $على$ $يمينها$ $.$ تُسمى الدائرة $غير$ متوازنة إذا لم تحتوي أي حافة فائقة $على$ رؤوس أخرى في الدائرة. أثبت كلود بيرج أن الرسم البياني الفائق يكون متوازنًا إذا وفقط إذا لم يحتوي على دائرة غير متوازنة فردية الطول. يتمتع كل رسم بياني فائق متوازن بخاصية كونيغ. ^[⁹^]^[¹^]^:^468-470

ما يلي متكافئ: ^{[ 1 ]}^{: 470-471}

كل رسم بياني فائق جزئي من $H$ (أي رسم بياني فائق مشتق من $H$ عن طريق حذف بعض الحواف الفائقة) له خاصية كونيغ.
كل رسم بياني جزئي فائق من $H$ له خاصية أن درجته القصوى تساوي عدد تلوين حوافه الأدنى .
تتمتع $H$ بخاصية Helly ، ومخطط التقاطع لـ $H$ (المخطط البسيط الذي تكون فيه الرؤوس $E$ وعنصران من $E$ مرتبطان إذا وفقط إذا تقاطعا) هو مخطط مثالي .

المطابقة والتعبئة

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

التعبئة الرأسية في الرسم البياني (البسيط) هي مجموعة جزئية $P$ من رؤوسه، بحيث لا يكون أي رأسين في $P$ متجاورين.

تُكافئ مشكلة إيجاد أقصى تعبئة للرؤوس في رسم بياني مشكلة إيجاد أقصى تطابق في رسم بياني فائق: ^{[ 1 ]}^{: 467}

بفرض وجود مخطط فائق $H = (V, E)$ ، يُعرَّف مخطط تقاطعه $Int(H)$ بأنه المخطط البسيط الذي رؤوسه $E$ وحوافه أزواج $(e1, e2)$ بحيث يشترك $e1$ $و$ $e2 في رأس$ $واحد .$ $عندئذٍ$ ، كل تطابق في $H$ هو تجميع رؤوس في $Int($ $H$ $)،$ $والعكس$ صحيح.
بفرض وجود رسم بياني $G = (V', E')$ ، نُعرّف الرسم البياني الفائق النجمي $St(G)$ بأنه الرسم البياني الفائق الذي رؤوسه هي $E'$ وحوافه الفائقة هي نجوم رؤوس $G$ (أي، لكل رأس $v'$ في $V'$ ، توجد حافة فائقة في $St(G)$ تحتوي على جميع الحواف في $E'$ المجاورة لـ $v'$ ). عندئذٍ، كل عملية تعبئة رؤوس في $G$ هي مطابقة في $St(G)،$ والعكس صحيح.
$بدلاً من$ ذلك، إذا كان لدينا رسم بياني $G = (V', E')$ ، نُعرّف الرسم البياني الفائق للزمر $Cl(G)$ بأنه الرسم البياني الفائق الذي رؤوسه هي زمر G ، ولكل رأس $v'$ في $V'$ ، يوجد ضلع فائق في $Cl($ $G$ $)$ يحتوي على جميع الزمر في $G$ التي تحتوي على $v'$ . وبالتالي، فإن كل عملية تعبئة رؤوس في $G$ تُطابق $Cl($ $G$ $)$ والعكس صحيح. تجدر الإشارة إلى أنه لا يمكن إنشاء $Cl($ $G$ $) من$ $G$ في وقت متعدد الحدود ، لذا لا يمكن استخدامه كاختزال لإثبات صعوبة NP. لكن له بعض الاستخدامات النظرية.

انظر أيضاً

المطابقة ثلاثية الأبعاد - حالة خاصة من مطابقة الرسوم البيانية الفائقة مع الرسوم البيانية الفائقة الموحدة ثلاثية الأبعاد.
غطاء الرؤوس في الرسوم البيانية الفائقة
الرسم البياني الفائق ثنائي الأجزاء
مطابقة قوس قزح في الرسوم البيانية الفائقة
الرسم البياني الفائق ذو الفاصل الزمني D - رسم بياني فائق لانهائي توجد فيه علاقة ما بين رقم المطابقة ورقم التغطية.
نظرية إردوش-كو-رادو حول الحواف غير المنفصلة ثنائياً في المخططات الفائقة

مراجع

1 2 3 4 5 6 7 لوفاسز, لازلو ; بلامر ، دكتوراه في الطب (1986)، نظرية المطابقة ، حوليات الرياضيات المنفصلة، المجلد. 29، شمال هولندا، ISBN 0-444-87916-1، MR 0859549
↑ بيرج، كلود (1973). الرسوم البيانية والرسوم البيانية الفائقة . أمستردام: نورث هولاند.
1 2 أهاروني، رون؛ كيسلر، أوفرا (15-10-1990). "حول إمكانية توسيع نظرية هول لتشمل المخططات الفائقة ثنائية الأجزاء" . الرياضيات المتقطعة . 84 (3): 309-313 . doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
1 2 3 4 فوريدي، زولتان (1981-06-01). "الدرجة القصوى والمطابقات الكسرية في المخططات الفائقة المنتظمة". كومبيناتوريكا . 1 (2): 155-162 . doi : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .
↑ لوفاس، ل. (1974). "نظريات المينيماكس للرسوم البيانية الفائقة". في: بيرج، كلود؛ راي-تشودري، ديجين (محرران). ندوة الرسوم البيانية الفائقة . سلسلة محاضرات في الرياضيات. المجلد 411. برلين، هايدلبرغ: سبرينغر. الصفحات 111-126 . doi : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7.
1 2 نيمان، كاثرين؛ سو، فرانسيس إدوارد؛ زربيب، شيرا (2020-01-02). "القسمة العادلة مع قطع متعددة" . الرياضيات التطبيقية المنفصلة . 283 : 115-122 . arXiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
↑ كيفاش، بيتر؛ مايكروفت، ريتشارد (1 يناير 2015). نظرية هندسية لمطابقة المخططات الفائقة . مذكرات الجمعية الرياضية الأمريكية. المجلد 233. الجمعية الرياضية الأمريكية. ISBN 978-1-4704-0965-4.
↑ بيرج، كلود (1973-01-01)، سريفاستافا، جاغديش ن. (محرر)، "الفصل 2 - الرسوم البيانية الفائقة المتوازنة وبعض التطبيقات في نظرية الرسوم البيانية" ، مسح لنظرية التوافقية ، نورث هولاند، ص 15-23 ، ISBN 978-0-7204-2262-7تم الاطلاع عليه بتاريخ 19 يونيو 2020{{citation}}: CS1 maint: work parameter with ISBN ( link )
↑ بيرج، كلود؛ فيرغناس، ميشيل لاس (1970). "حول نظرية من النوع الملكي للرسوم البيانية الفائقة". حوليات أكاديمية نيويورك للعلوم . 175 (1): 32-40 . رمز Bibcode : 1970NYASA.175...32B . doi : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .

[lp-1] 1 2 3 4 5 6 7 لوفاسز, لازلو ; بلامر ، دكتوراه في الطب (1986)، نظرية المطابقة ، حوليات الرياضيات المنفصلة، المجلد. 29، شمال هولندا، ISBN 0-444-87916-1، MR 0859549

[2] بيرج، كلود (1973). الرسوم البيانية والرسوم البيانية الفائقة . أمستردام: نورث هولاند.

[:1-3] 1 2 أهاروني، رون؛ كيسلر، أوفرا (15-10-1990). "حول إمكانية توسيع نظرية هول لتشمل المخططات الفائقة ثنائية الأجزاء" . الرياضيات المتقطعة . 84 (3): 309-313 . doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .

[:2-4] 1 2 3 4 فوريدي، زولتان (1981-06-01). "الدرجة القصوى والمطابقات الكسرية في المخططات الفائقة المنتظمة". كومبيناتوريكا . 1 (2): 155-162 . doi : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .

[5] لوفاس، ل. (1974). "نظريات المينيماكس للرسوم البيانية الفائقة". في: بيرج، كلود؛ راي-تشودري، ديجين (محرران). ندوة الرسوم البيانية الفائقة . سلسلة محاضرات في الرياضيات. المجلد 411. برلين، هايدلبرغ: سبرينغر. الصفحات 111-126 . doi : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7.

[:0-6] 1 2 نيمان، كاثرين؛ سو، فرانسيس إدوارد؛ زربيب، شيرا (2020-01-02). "القسمة العادلة مع قطع متعددة" . الرياضيات التطبيقية المنفصلة . 283 : 115-122 . arXiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .

[7] كيفاش، بيتر؛ مايكروفت، ريتشارد (1 يناير 2015). نظرية هندسية لمطابقة المخططات الفائقة . مذكرات الجمعية الرياضية الأمريكية. المجلد 233. الجمعية الرياضية الأمريكية. ISBN 978-1-4704-0965-4.

[8] بيرج، كلود (1973-01-01)، سريفاستافا، جاغديش ن. (محرر)، "الفصل 2 - الرسوم البيانية الفائقة المتوازنة وبعض التطبيقات في نظرية الرسوم البيانية" ، مسح لنظرية التوافقية ، نورث هولاند، ص 15-23 ، ISBN 978-0-7204-2262-7تم الاطلاع عليه بتاريخ 19 يونيو 2020{{citation}}: CS1 maint: work parameter with ISBN ( link )

[9] بيرج، كلود؛ فيرغناس، ميشيل لاس (1970). "حول نظرية من النوع الملكي للرسوم البيانية الفائقة". حوليات أكاديمية نيويورك للعلوم . 175 (1): 32-40 . رمز Bibcode : 1970NYASA.175...32B . doi : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .

[ 1 ]

[ 2 ]

[ 5 ]

[ 7 ]

[

[