الرسم البياني الخطي

في فرع الرياضيات $المعروف$ بنظرية المخططات ، يُعد المخطط الخطي للمخطط غير الموجه $G$ مخططًا آخر $L(G)$ يمثل العلاقات المجاورة بين حواف G. ويتم إنشاء $L($ $G$ $)$ بالطريقة التالية: لكل حافة في $G$ ، يتم إنشاء رأس في $L($ $G$ $)$ ؛ ولكل حافتين في $G$ تشتركان في رأس واحد، يتم إنشاء حافة بين رأسيهما المتناظرين في $L($ $G$ $)$ .

يُشتق اسم " الرسم البياني الخطي" من ورقة بحثية لهاري ونورمان (1960)، مع أن ويتني (1932) وكراوز (1943) استخدما هذا التركيب قبل ذلك. ^{[ 1 ]} تشمل المصطلحات الأخرى المستخدمة للإشارة إلى الرسم البياني الخطي: الرسم البياني المُغطي ، والمشتق ، والثنائي من الحافة إلى الرأس ، والمرافق ، والرسم البياني التمثيلي ، و θ-أوبرازوم ، ^{[ 1 ]} بالإضافة إلى الرسم البياني للحافة ، ورسم التبادل ، والرسم البياني المرافق ، والرسم البياني المشتق . ^{[ 2 ]}

أثبت هاسلر ويتني ( 1932 ) أنه باستثناء حالة واحدة ، يمكن استعادة بنية الرسم البياني المتصل $G بالكامل من رسمه البياني الخطي.$ ^[³^] وتنتج العديد من خصائص الرسوم البيانية الخطية الأخرى عن ترجمة خصائص الرسم البياني الأساسي من الرؤوس إلى الحواف، وبحسب نظرية ويتني، يمكن إجراء الترجمة نفسها في الاتجاه المعاكس. الرسوم البيانية الخطية خالية من المخالب ، والرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء مثالية . تتميز الرسوم البيانية الخطية بتسعة رسوم بيانية فرعية ممنوعة ، ويمكن التعرف عليها في وقت خطي .

تمت دراسة العديد من التوسعات لمفهوم الرسم البياني الخطي، بما في ذلك الرسوم البيانية الخطية للرسوم البيانية الخطية، والرسوم البيانية الخطية للرسوم البيانية المتعددة، والرسوم البيانية الخطية للرسوم البيانية الفائقة ، والرسوم البيانية الخطية للرسوم البيانية الموزونة.

التعريف الرسمي

إذا كان لدينا رسم بياني $G$ ، فإن الرسم البياني الخطي $L (G)$ الخاص به هو رسم بياني بحيث

يمثل كل رأس من رؤوس $L (G)$ ضلعًا من أضلاع $G$ ؛ و
يكون رأسان من $L (G)$ متجاورين إذا وفقط إذا كانت حوافهم المتناظرة تشترك في نقطة نهاية مشتركة ("متجاورين") في $G.$

أي أنه رسم بياني لتقاطع حواف $G$ ، حيث يمثل كل حافة بمجموعة نقطتي نهايتها. ^{[ 2 ]}

مثال

تُظهر الأشكال التالية رسمًا بيانيًا (يسارًا، برؤوس زرقاء) ورسمه الخطي (يمينًا، برؤوس خضراء). يُشار إلى كل رأس من رؤوس الرسم الخطي بزوج من نقاط نهاية الحافة المقابلة له في الرسم البياني الأصلي. على سبيل المثال، الرأس الأخضر على اليمين المُشار إليه بـ 1،3 يُقابل الحافة على اليسار بين الرأسين الأزرقين 1 و3. الرأس الأخضر 1،3 مجاور لثلاثة رؤوس خضراء أخرى: 1،4 و1،2 (المقابلة لحواف تشترك في نقطة النهاية 1 في الرسم البياني الأزرق) و4،3 (المقابلة لحافة تشترك في نقطة النهاية 3 في الرسم البياني الأزرق).

الرسم البياني G
الرؤوس في L( G ) المُنشأة من الحواف في G
الحواف المضافة في L( G )
الرسم البياني الخطي L( G )

ملكيات

الخصائص المترجمة للرسم البياني الأساسي

يمكن ترجمة خصائص الرسم البياني $G التي تعتمد فقط على التجاور بين الحواف إلى خصائص مكافئة في$ $L (G)$ تعتمد على التجاور بين الرؤوس. على سبيل المثال، التطابق في $G$ هو مجموعة من الحواف التي لا يوجد حافتان متجاورتان فيها، ويقابله مجموعة من الرؤوس في $L (G)$ التي لا يوجد رأسان متجاوران فيها، أي مجموعة مستقلة . ^{[ 4 ]}

هكذا،

الرسم البياني الخطي للرسم البياني المتصل هو رسم بياني متصل. إذا كان $G$ متصلاً، فإنه يحتوي على مسار يربط أي حافتين من حوافه، وهو ما يُترجم إلى مسار في $L (G)$ يحتوي على أي رأسين من رؤوس $L (G)$ . ومع ذلك، قد يكون للرسم البياني $G$ الذي يحتوي على بعض الرؤوس المعزولة، وبالتالي يكون غير متصل، رسم بياني خطي متصل. ^{[ 5 ]}
يحتوي الرسم البياني الخطي على نقطة مفصلية إذا وفقط إذا كان الرسم البياني الأساسي يحتوي على جسر لا تكون درجة أي من طرفيه واحدة. ^{[ 2 ]}
بالنسبة للرسم البياني $G$ الذي يحتوي على $n$ رأسًا و $m$ حافة، فإن عدد رؤوس الرسم البياني الخطي $L (G)$ هو $m$ ، وعدد حواف $L (G)$ هو نصف مجموع مربعات درجات الرؤوس في $G$ ، مطروحًا منه $m$ . ^{[ 6 ]}
تُقابل المجموعة المستقلة في $L (G)$ تطابقًا في $G.$ وعلى وجه الخصوص، تُقابل المجموعة المستقلة القصوى في $L (G)$ تطابقًا أقصى في $G.$ وبما أنه يمكن إيجاد التطابقات القصوى في وقت متعدد الحدود، فإنه يمكن أيضًا إيجاد المجموعات المستقلة القصوى للرسوم البيانية الخطية، على الرغم من صعوبة مسألة المجموعة المستقلة القصوى بالنسبة لعائلات أعم من الرسوم البيانية. ^{[ 4 ]} وبالمثل، تُقابل المجموعة المستقلة قوس قزح في $L (G)$ تطابق قوس قزح في $G.$
العدد اللوني للحافة في الرسم البياني $G$ يساوي العدد اللوني للرأس في الرسم البياني الخطي $L (G)$ . ^{[ 7 ]}
الرسم البياني الخطي للرسم البياني المتعدي الحواف هو رسم بياني متعدٍ الرؤوس . يمكن استخدام هذه الخاصية لتوليد عائلات من الرسوم البيانية التي (مثل رسم بيترسن البياني ) تكون متعدية الرؤوس ولكنها ليست رسوم كايلي البيانية : إذا كان $G$ رسمًا بيانيًا متعديًا الحواف يحتوي على خمسة رؤوس على الأقل، وليس ثنائي الأجزاء، وله درجات رؤوس فردية، فإن $L (G)$ هو رسم بياني متعدٍ الرؤوس وغير كايلي. ^{[ 8 ]}
إذا احتوى الرسم البياني $G$ على دورة أويلر ، أي إذا كان $G$ متصلاً وله عدد زوجي من الحواف عند كل رأس، فإن الرسم البياني الخطي لـ $G$ يكون هاميلتونيًا . مع ذلك، لا تنشأ جميع الدورات الهاميلتونية في الرسوم البيانية الخطية من دورات أويلر بهذه الطريقة؛ على سبيل المثال، يكون الرسم البياني الخطي للرسم البياني الهاميلتوني $G$ نفسه هاميلتونيًا، بغض النظر عما إذا كان $G$ أيضًا أويلريًا. ^{[ 9 ]}
إذا كان رسمان بيانيان بسيطان متماثلين ، فإن رسومهما البيانية الخطية تكون متماثلة أيضًا. وتُقدّم نظرية ويتني لتماثل الرسوم البيانية عكس هذه النظرية لجميع أزواج الرسوم البيانية المتصلة باستثناء زوج واحد.
في سياق نظرية الشبكات المعقدة ، يحافظ الرسم البياني الخطي لشبكة عشوائية على العديد من خصائص الشبكة، مثل خاصية العالم الصغير (وجود مسارات قصيرة بين جميع أزواج الرؤوس) وشكل توزيع درجاتها . ^{[ 10 ]} لاحظ إيفانز ولامبيوت (2009) أنه يمكن تطبيق أي طريقة لإيجاد تجمعات الرؤوس في شبكة معقدة على الرسم البياني الخطي واستخدامها لتجميع حوافها بدلاً من ذلك.

نظرية ويتني للتماثل

إذا كانت الرسوم البيانية الخطية لرسمين بيانيين متصلين متماثلة، فإن الرسوم البيانية الأساسية تكون متماثلة، باستثناء حالة الرسم البياني المثلثي $K 3$ والرسم البياني المخلبي $K 1,3$ ، حيث أن لهما رسومًا بيانية خطية متماثلة ولكنهما ليسا متماثلين في حد ذاتهما. ^{[ 3 ]}

إلى جانب $K3$ و $K1,3 ، توجد بعض الرسوم البيانية الصغيرة الاستثنائية$ $الأخرى$ التي تتميز بأن رسمها الخطي يتمتع بدرجة تناظر أعلى من الرسم البياني نفسه. على سبيل المثال، يحتوي الرسم البياني المعيني $K1,1,2$ (مثلثان يشتركان في ضلع) على أربعة تماثلات بيانية، $بينما$ يحتوي رسمه الخطي $K1,2,2 على$ ثمانية. في الرسم التوضيحي للرسم البياني المعيني الموضح، لا يُعد تدوير الرسم البياني بزاوية 90 درجة تناظرًا للرسم البياني نفسه، بل هو تناظر لرسمه الخطي. مع ذلك، تحتوي جميع هذه الحالات الاستثنائية على أربعة رؤوس على الأكثر. تنص نسخة مُحسّنة من نظرية ويتني للتماثل على أنه بالنسبة للرسوم البيانية المتصلة التي تحتوي على أكثر من أربعة رؤوس، يوجد تطابق تام بين تماثلات الرسوم البيانية وتماثلات رسومها الخطية. ^{[ 11 ]}

تم إثبات نظائر نظرية ويتني للتماثل بالنسبة للرسوم البيانية الخطية للرسوم البيانية المتعددة ، ولكنها أكثر تعقيدًا في هذه الحالة. ^{[ 12 ]}

رسوم بيانية خطية منتظمة ومثالية للغاية

يُعرف الرسم البياني الخطي للرسم البياني الكامل $K n$ أيضًا بالرسم البياني المثلثي ، أو رسم جونسون البياني $J (n, 2)$ ، أو مكمل رسم كنيسر البياني KG $ n,2$ . تتميز الرسوم البيانية المثلثية بأطيافها ، باستثناء $n = 8.$ [ ^{13 ] ويمكن} وصفها أيضًا (باستثناء $K 8$ ) بأنها رسوم بيانية منتظمة بقوة ذات معاملات $srg(n (n -1)/2, 2(n -2), n -2, 4)$ . ^{[ 14 ]} الرسوم البيانية الثلاثة المنتظمة بقوة التي لها نفس المعاملات والطيف مثل $L (K 8)$ هي رسوم تشانغ البيانية ، والتي يمكن الحصول عليها عن طريق تبديل الرسم البياني من $L (K 8)$ .

الرسم البياني الخطي للرسم البياني ثنائي الأجزاء مثالي (انظر نظرية كونيغ )، ولكنه ليس بالضرورة ثنائي الأجزاء كما يُبين مثال الرسم البياني للمخلب. تُشكل الرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء إحدى اللبنات الأساسية للرسوم البيانية المثالية، المستخدمة في برهان نظرية الرسم البياني المثالي القوي . ^[¹⁵^] تُعد رسوم الرخ البيانية ، وهي رسوم بيانية خطية للرسوم البيانية ثنائية الأجزاء الكاملة ، حالة خاصة من هذه الرسوم البيانية . ومثل الرسوم البيانية الخطية للرسوم البيانية الكاملة، يمكن تمييزها $،$ باستثناء واحد، بعدد رؤوسها، وعدد حوافها، وعدد الجيران المشتركين للنقاط المتجاورة وغير المتجاورة. الحالة الاستثنائية الوحيدة هي $L$ $($ $K4,4$ $)$ ، التي تشترك في معاييرها مع رسم شريكاندي البياني . عندما يكون لكلا جانبي التقسيم الثنائي نفس عدد الرؤوس، تكون هذه الرسوم البيانية منتظمة بقوة. ^[¹⁶^] لقد ثبت أنه باستثناء $C3$ $و$ $C4$ و $C5$ ، يمكن تحويل جميع الرسوم البيانية المتصلة والمنتظمة بقوة إلى رسوم بيانية غير منتظمة بقوة ضمن تحويلين للرسم البياني الخطي. $[$ 17 $]$ ^يتطلب^التوسع^ليشمل الرسوم البيانية غير المتصلة ألا يكون الرسم البياني اتحادًا منفصلاً $لـ$ $C3$ .

بشكل عام، يُقال إن الرسم البياني $G هو$ رسم بياني خطي مثالي إذا كان $L (G)$ رسمًا بيانيًا مثاليًا . الرسوم البيانية الخطية المثالية هي تحديدًا تلك التي لا تحتوي على دورة بسيطة ذات طول فردي أكبر من ثلاثة. ^{[ 18 ]} وبالمثل، يكون الرسم البياني خطيًا مثاليًا إذا وفقط إذا كان كل مكون من مكوناته ثنائية الاتصال إما ثنائي الأجزاء أو على شكل $K⁴$ (الهرم الرباعي) أو $K⁻¹$ $, ⁻¹, ⁿ$ (كتاب من مثلث واحد أو أكثر تشترك جميعها في ضلع مشترك). ^{[ 19 ]} كل رسم بياني خطي مثالي هو نفسه مثالي. ^{[ 20 ]}

عائلات الرسوم البيانية الأخرى ذات الصلة

جميع الرسوم البيانية الخطية هي رسوم بيانية خالية من المخالب ، أي رسوم بيانية لا تحتوي على رسم بياني فرعي مستحث على شكل شجرة ثلاثية الأوراق. ^{[ 21 ]} وكما هو الحال مع الرسوم البيانية الخالية من المخالب بشكل عام، فإن كل رسم بياني خطي متصل $L (G)$ يحتوي على عدد زوجي من الحواف له تطابق تام ؛ ^{[ 22 ]} وهذا يعني، بشكل مكافئ، أنه إذا كان الرسم البياني الأساسي $G$ يحتوي على عدد زوجي من الحواف، فيمكن تقسيم حوافه إلى مسارات ثنائية الحواف.

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

جميع القيم الذاتية لمصفوفة التجاور $A$ للرسم البياني الخطي لا تقل عن -2. والسبب في ذلك هو أنه يمكن كتابة $A على النحو التالي:$ $A=J^{\mathsf {T}}J-2I$ حيث $J$ هي مصفوفة الوقوع غير الموقّعة للرسم البياني قبل الخط، و $I$ هي مصفوفة الوحدة. على وجه الخصوص، $A + 2I هي$ مصفوفة غراميان لنظام من المتجهات: تُسمى جميع الرسوم البيانية التي تتمتع بهذه الخاصية بالرسوم البيانية الخطية المعممة. ^{[ 25 ]}

التوصيف والتعرف

قسم كليك

بالنسبة لأي رسم بياني $G$ ، وأي رأس $v$ في $G$ ، فإن مجموعة الحواف المتصلة بـ $v$ تُقابل زمرة في الرسم البياني الخطي $L (G)$ . تُقسّم الزمر المُشكّلة بهذه الطريقة حواف $L (G)$ . ينتمي كل رأس من $L (G)$ إلى اثنتين منها فقط (الزمرتان اللتان تُقابلان طرفي الحافة المقابلة في $G$ ).

يمكن استخدام وجود هذا التقسيم إلى زمر لتوصيف الرسوم البيانية الخطية: يكون الرسم البياني $L$ رسمًا بيانيًا خطيًا لرسم بياني آخر أو رسم بياني متعدد إذا وفقط إذا كان من الممكن إيجاد مجموعة من الزمر في $L$ (مع السماح لبعض الزمر بأن تكون رؤوسًا منفردة) تقسم حواف $L$ ، بحيث ينتمي كل رأس من $L$ إلى زمرتين فقط. ^{[ 21 ]} ويكون الرسم البياني خطيًا لرسم بياني آخر (وليس رسمًا بيانيًا متعددًا) إذا حققت هذه المجموعة من الزمر الشرط الإضافي المتمثل في عدم وجود رأسين من $L$ في نفس الزمرتين. وبوجود هذه المجموعة من الزمر، يمكن استعادة الرسم البياني الأساسي $G$ الذي يكون $L$ رسمه البياني الخطي عن طريق إنشاء رأس واحد في G $لكل$ زمرة، وحافة في $G$ لكل رأس في $L$ بحيث تكون نهايتاها هما الزمرتين اللتين تحتويان على الرأس في $L.$ بحسب الصيغة القوية لنظرية ويتني للتماثل، إذا كان الرسم البياني الأساسي $G$ يحتوي على أكثر من أربعة رؤوس، فلا يمكن أن يكون هناك سوى تقسيم واحد من هذا النوع.

على سبيل المثال، يمكن استخدام هذا التوصيف لإظهار أن الرسم البياني التالي ليس رسمًا بيانيًا خطيًا:

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

الرسوم البيانية الفرعية المحظورة

تم إثبات توصيف آخر للرسوم البيانية الخطية في دراسة بينيك (1970) (وقد نُشر سابقًا دون برهان من قِبل بينيك (1968) ). بيّن بينيك وجود تسعة رسوم بيانية دنيا ليست رسومًا بيانية خطية، بحيث يكون لأي رسم بياني ليس خطيًا أحد هذه الرسوم البيانية التسعة كرسم بياني فرعي مُستحث . أي أن الرسم البياني يكون خطيًا إذا وفقط إذا لم تُستحث أي مجموعة فرعية من رؤوسه أحد هذه الرسوم البيانية التسعة. في المثال أعلاه، تُستحث الرؤوس الأربعة العلوية شكلًا يشبه المخلب (أي رسمًا بيانيًا ثنائي الأجزاء كاملًا $K 1,3$ )، كما هو موضح في أعلى يسار الرسم التوضيحي للرسوم البيانية الفرعية المحظورة. لذلك، وفقًا لتوصيف بينيك، لا يمكن أن يكون هذا المثال رسمًا بيانيًا خطيًا. بالنسبة للرسوم البيانية ذات الدرجة الدنيا 5 على الأقل، فإن الرسوم البيانية الفرعية الستة الموجودة في العمودين الأيمن والأيسر من الشكل هي فقط ما يلزم في التوصيف. ^{[ 26 ]}

الخوارزميات

وصف روسوبولوس (1973) وليهوت (1974) خوارزميات خطية للتعرف على الرسوم البيانية الخطية وإعادة بناء رسومها البيانية الأصلية. وعمّم سيسلو (1982) هذه الأساليب لتشمل الرسوم البيانية الموجهة . ووصف ديجورجي وسيمون (1995) بنية بيانات فعالة للحفاظ على رسم بياني ديناميكي، يخضع لإضافة وحذف الرؤوس، والحفاظ على تمثيل للمدخلات كرسم بياني خطي (إن وجد) في وقت يتناسب مع عدد الحواف المتغيرة في كل خطوة.

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

قم بإنشاء الرسم البياني المدخل $L$ بإضافة الرؤوس واحدًا تلو الآخر، مع اختيار رأس في كل خطوة مجاور لرأس واحد على الأقل تمت إضافته سابقًا. أثناء إضافة الرؤوس إلى $L$ ، حافظ على رسم بياني $G$ بحيث يكون $L = L (G)$ ؛ إذا فشلت الخوارزمية في إيجاد رسم بياني مناسب $G$ ، فإن المدخل ليس رسمًا بيانيًا خطيًا وتتوقف الخوارزمية.
عند إضافة رأس $v$ إلى رسم بياني $L (G)$ يحتوي على أربعة $رؤوس$ أو أقل، قد لا يكون تمثيل الرسم البياني الخطي فريدًا. ولكن في هذه الحالة، يكون الرسم البياني المُضاف صغيرًا بما يكفي لإيجاد تمثيل له كرسم بياني خطي باستخدام البحث الشامل في وقت ثابت.
عند إضافة رأس $v$ إلى رسم بياني أكبر $L$ يُمثل الرسم البياني الخطي لرسم بياني آخر $G$ ، ليكن $S$ الرسم البياني الجزئي من $G$ المُكوَّن من الحواف التي تُقابل جيران $v$ في $L.$ تحقق مما إذا كان $S$ يحتوي على غطاء رأسي يتكون من رأس واحد أو رأسين غير متجاورين. إذا كان هناك رأسان في الغطاء، فقم بتوسيع $G$ بإضافة حافة (تُقابل $v$ ) تربط هذين الرأسين. إذا كان هناك رأس واحد فقط في الغطاء، فأضف رأسًا جديدًا إلى $G$ ، مُجاورًا لهذا الرأس.

تستغرق كل خطوة إما وقتًا ثابتًا، أو تتضمن إيجاد غطاء رأس ذي حجم ثابت داخل رسم بياني $S$ يتناسب حجمه مع عدد جيران الرأس $v$ . وبالتالي، فإن إجمالي وقت الخوارزمية بأكملها يتناسب مع مجموع أعداد جيران جميع الرؤوس، والذي (بحسب نظرية المصافحة ) يتناسب مع عدد حواف الإدخال.

تكرار عامل الرسم البياني الخطي

يأخذ فان رويج وويلف (1965) في الاعتبار تسلسل الرسوم البيانية

G,L(G),L(L(G)),L(L(L(G))),\dots .\

تُظهر هذه النتائج أنه عندما يكون $G عبارة عن$ رسم بياني متصل محدود ، فإن أربعة سلوكيات فقط ممكنة لهذا التسلسل:

إذا كان $G$ مخططًا دوريًا، ^فإن L $(G) وكل$ مخطط لاحق في هذه السلسلة متماثل مع $G$ نفسه. وهذه هي المخططات المتصلة الوحيدة التي يكون فيها $L (G)$ متماثلًا مع $G.$ [ ^{27 ]}
إذا كان $G$ عبارة عن مخلب $K 1,3$ ، فإن $L (G)$ وجميع الرسوم البيانية اللاحقة في التسلسل هي مثلثات.
إذا كان $G$ عبارة عن رسم بياني للمسار ، فإن كل رسم بياني لاحق في التسلسل يكون مسارًا أقصر حتى ينتهي التسلسل في النهاية برسم بياني فارغ .
في جميع الحالات المتبقية، تتزايد أحجام الرسوم البيانية في هذا التسلسل في النهاية بلا حدود.

إذا لم تكن $G$ متصلة، فإن هذا التصنيف ينطبق بشكل منفصل على كل مكون من مكونات $G.$

بالنسبة للرسوم البيانية المتصلة التي ليست مسارات، فإن جميع أعداد التكرار العالية بما فيه الكفاية لعملية الرسم البياني الخطي تنتج رسومًا بيانية هاميلتونية. ^{[ 28 ]}

التعميمات

الرسوم البيانية المتوسطة والمجسمات المحدبة

عندما يكون للرسم البياني المستوي $G$ درجة رأس قصوى تبلغ ثلاثة، يكون رسمه الخطي مستويًا، ويمكن تمديد أي تضمين مستوي لـ $G إلى تضمين لـ$ $L (G)$ . مع ذلك، توجد رسوم بيانية مستوية ذات درجة أعلى تكون رسومها الخطية غير مستوية. تشمل هذه الرسوم، على سبيل المثال، الرسم البياني ذو الخمس نجوم $K1,5 ،$ ورسم بياني الجوهرة المتكون من إضافة قطرين غير متقاطعين داخل خماسي منتظم، وجميع المجسمات المحدبة التي لها رأس من الدرجة أربعة أو أكثر. ^{[ 29 ]}

يُعدّ الرسم البياني الوسيط بنيةً بديلةً تتطابق مع الرسم البياني الخطي للرسوم البيانية المستوية ذات الدرجة القصوى ثلاثة، ولكنه يكون مستويًا دائمًا. يحتوي على نفس رؤوس الرسم البياني الخطي، ولكن قد يحتوي على عدد أقل من الحواف: يكون رأسان في الرسم البياني الوسيط متجاورين إذا وفقط إذا كانت الحافتان المقابلتان لهما متتاليتين على أحد أوجه التمثيل المستوي. الرسم البياني الوسيط للرسم البياني الثنائي لرسم بياني مستوي هو نفسه الرسم البياني الوسيط للرسم البياني المستوي الأصلي. ^{[ 30 ]}

بالنسبة للمجسمات المنتظمة أو البسيطة، يمكن تمثيل عملية الرسم البياني المتوسط هندسيًا بعملية قطع كل رأس من رؤوس المجسم بمستوى يمر بمنتصفات جميع حوافه المتصلة به. ^{[ 31 ]} تُعرف هذه العملية بأسماء مختلفة، منها القطع الثاني، [ ^{32 ] والقطع} المنحط، ^{[ 33 ]} والتصحيح . ^{[ 34 ]}

إجمالي الرسوم البيانية

الرسم البياني الكلي $T (G)$ للرسم البياني $G$ له رؤوس تمثل عناصر (رؤوس أو حواف) الرسم البياني $G$ ، وتكون هناك حافة بين عنصرين عندما يكونان متجاورين أو متجاورين. ويمكن أيضًا الحصول على الرسم البياني الكلي بتقسيم كل حافة من حواف $G$ ثم حساب مربع الرسم البياني المقسم. ^{[ 35 ]}

الرسوم البيانية المتعددة

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

مع ذلك، بالنسبة للرسوم البيانية المتعددة، يوجد عدد أكبر من أزواج الرسوم البيانية غير المتماثلة التي لها نفس الرسوم البيانية الخطية. على سبيل المثال، الرسم البياني الثنائي الكامل $K 1, n$ له نفس الرسم البياني الخطي للرسم البياني ثنائي القطب والرسم البياني المتعدد لشانون بنفس عدد الحواف. ومع ذلك، لا يزال من الممكن اشتقاق نظائر لنظرية ويتني للتماثل في هذه الحالة. ^{[ 12 ]}

الرسوم البيانية الخطية

إنشاء مخططات دي بروين كرسوم بيانية خطية متكررة

من الممكن أيضًا تعميم الرسوم البيانية الخطية لتشمل الرسوم البيانية الموجهة. ^{[ 37 ]} إذا كان $G$ رسمًا بيانيًا موجهًا، فإن الرسم البياني الخطي الموجه له يحتوي على رأس واحد لكل حافة من حواف $G.$ يرتبط رأسان يمثلان حوافًا موجهة من $u$ إلى $v$ ومن $w$ إلى $x$ في $G$ بحافة من $uv$ إلى $wx$ في الرسم البياني الخطي الموجه عندما $v$ $=$ $w$ . أي أن كل حافة في الرسم البياني الخطي الموجه لـ $G$ تمثل مسارًا موجهًا بطول اثنين في $G. يمكن تكوين$ رسوم دي بروين البيانية بتكرار عملية تكوين الرسوم البيانية الخطية الموجهة هذه، بدءًا من رسم بياني موجه كامل . ^[³⁸^]

الرسوم البيانية الخطية الموزونة

في الرسم البياني الخطي $L (G)$ ، يُنشئ كل رأس من الدرجة $k$ في الرسم البياني الأصلي $G$ $عدد k (k -1)/2$ من الحواف في الرسم البياني الخطي. بالنسبة للعديد من أنواع التحليل، يعني هذا أن العقد ذات الدرجة العالية في $G$ ممثلة تمثيلاً زائداً في الرسم البياني الخطي $L (G)$ . على سبيل المثال، لنفترض مساراً عشوائياً على رؤوس الرسم البياني الأصلي $G.$ سيمر هذا المسار بحافة $e$ بتردد $f$ . من ناحية أخرى، تُربط هذه الحافة $e$ برأس فريد، ولنقل $v$ ، في الرسم البياني الخطي $L (G) . إذا أجرينا$ $الآن$ نفس نوع المسار العشوائي على رؤوس الرسم البياني الخطي، فقد يختلف تردد زيارة $v تماماً عن$ f . إذا كانت الحافة $e$ في $G$ متصلة بعقد من الدرجة $O (k)$ ، فسيتم اجتيازها بتردد $O (k²)$ أكثر في الرسم البياني الخطي $L (G)$ . بمعنى آخر، تضمن نظرية تماثل الرسوم البيانية لويتني أن الرسم البياني الخطي يُشفّر دائمًا تقريبًا بنية الرسم البياني الأصلي $G$ بدقة، لكنها لا تضمن وجود علاقة بسيطة بين ديناميكيات هذين الرسمين البيانيين. أحد الحلول هو إنشاء رسم بياني خطي مُثقّل، أي رسم بياني خطي بحواف مُثقّلة . هناك عدة طرق طبيعية للقيام بذلك. ^{[ 39 ]} على سبيل المثال، إذا كانت الحافتان $d$ و $e$ في الرسم البياني $G$ متصلتين برأس $v$ من الدرجة $k$ ، فإنه في الرسم البياني الخطي $L (G)$ يمكن إعطاء وزن $1/($ $k$ $- 1)$ للحافة التي تربط الرأسين $d$ و $e$ . بهذه الطريقة، ستكون قوة كل حافة في $G$ (بشرط ألا يكون أي من طرفيها متصلًا برأس من الدرجة 1) تساوي 2 في الرسم البياني الخطي $L$ $($ $G$ $)،$ وهو ما يتوافق مع الطرفين اللذين ترتبط بهما الحافة في $G.$ من السهل توسيع هذا التعريف للرسم البياني الخطي المُثقّل ليشمل الحالات التي يكون فيها الرسم البياني الأصلي $G$ ^[ 40 ^] المبدأ في جميع الحالات هو ضمان أن يعكس الرسم البياني الخطي L ⁽ $G) ديناميكيات وطوبولوجيا$ الرسم البياني الأصلي $G.$

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

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

رسم بياني للانفصال

يُنشأ مخطط الانفصال للمخطط $G$ ، ويُرمز له بـ $D (G)$ ، بالطريقة التالية: لكل ضلع في $G$ ، يُنشأ رأس في $D (G)$ ؛ ولكل ضلعين في $G$ لا يشتركان في رأس، يُنشأ ضلع بين رأسيهما المتناظرين في $D (G)$ . ^{[ 41 ]} بعبارة أخرى، $D (G)$ هو المخطط المُكمِّل لـ $L (G)$ . الزمرة في $D (G)$ تُقابل مجموعة مستقلة في $L (G)$ ، والعكس صحيح.

ملحوظات

1 2 هيمينجر وبينيك (1978) ، ص. 273.
1 2 3 هاراري (1972) ، ص 71.
1 2 ويتني (1932) ؛ كراوز (1943) ؛ هاراري (1972) ، النظرية 8.3، ص 72. يقدم هاراري برهانًا مبسطًا لهذه النظرية بواسطة يونغ (1966) .
1 2 باشوس، فانجيليس ث. (2010)، التحسين التوافقي وعلوم الحاسوب النظرية: واجهات ووجهات نظر ، جون وايلي وأولاده، ص 394، ISBN 978-0-470-39367-3من الواضح أن هناك تطابقًا واحدًا لواحد بين تطابقات الرسم البياني والمجموعات المستقلة للرسم البياني الخطي الخاص به.
↑ تم الإشارة إلى ضرورة مراعاة الرؤوس المعزولة عند النظر في اتصال الرسوم البيانية الخطية بواسطة Cvetković و Rowlinson و Simić (2004) ، ص 32 .
^ هراري (1972) ، النظرية 8.1، ص. 72.
↑ ديستل، راينهارد (2006)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد 173، سبرينغر، ص 112، ISBN 978-3-540-26183-4. متوفر أيضاً في النسخة الإلكترونية المجانية ، الفصل 5 ("التلوين")، صفحة 118.
↑ لوري، جوزيف؛ سكابيلاتو، رافاييل (2003)، موضوعات في التشكلات الذاتية للرسوم البيانية وإعادة بنائها ، نصوص طلابية من جمعية لندن الرياضية، المجلد 54، كامبريدج: مطبعة جامعة كامبريدج، ص 44، ISBN 0-521-82151-7، MR 1971819 . يعزو لوري وسكابيلاتو هذا الإنجاز إلى مارك واتكينز.
^ هراري (1972) ، النظرية 8.8، ص. 80.
^ رمضانبور، كريم بور ومشاغي (2003) .
^ يونج (1966) ؛ ديجيورجي وسيمون (1995) .
1 2 زفيروفيتش (1997)
↑ فان دام، إدوين ر.؛ هايمرز، ويليم هـ. (2003)، "أي الرسوم البيانية يتم تحديدها بواسطة طيفها؟" ، الجبر الخطي وتطبيقاته ، 373 : 241-272 ، doi : 10.1016/S0024-3795(03)00483-X ، MR 2022290 ، S2CID 32070167 انظر على وجه الخصوص الاقتراح 8، صفحة 262.
↑ هاراري (1972) ، النظرية 8.6، ص 79. ينسب هاراري هذه النتيجة إلى أوراق بحثية مستقلة لـ LC Chang (1959) و AJ Hoffman (1960).
↑ تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2006)، "نظرية الرسم البياني الكامل القوي" ، حوليات الرياضيات ، 164 (1): 51-229 ، arXiv : math/0212070 ، doi : 10.4007/annals.2006.164.51 ، S2CID 119151552 انظر أيضًا: Roussel, F.; Rusu, I.; Thuillier, H. (2009)، "تخمين الرسم البياني المثالي القوي: 40 عامًا من المحاولات، وحلها"، الرياضيات المتقطعة ، 309 (20): 6092-6113 ، doi : 10.1016/j.disc.2009.05.024 ، MR 2552645 ، S2CID 16049392 .
↑ هاراري (1972) ، النظرية 8.7، ص 79. يُنسب هاراري هذا التوصيف للرسوم البيانية الخطية للرسوم البيانية الثنائية الكاملة إلى مون وهوفمان. وقد سبق أن أثبت شريكاندي حالة تساوي عدد الرؤوس على كلا الجانبين.
↑ يانغ، فان؛ هوانغ، شينغيو (2024). "رؤى نظرية حول تحويل الرسم البياني الخطي في تعلم الرسم البياني". arXiv : 2410.16138 [ cs.LG ].
^ تروتر (1977) ؛ دي ويرا (1978) .
↑ مافري (1992) .
↑ تروتر (1977) .
1 2 Harary (1972) ، النظرية 8.4 ، ص. 74 ، يقدم ثلاثة توصيفات مكافئة للرسوم البيانية الخطية: تقسيم الحواف إلى زمر، وخاصية كونها خالية من المخالب وخالية من المعين الفردي ، والرسوم البيانية التسعة المحظورة لـ Beineke.
↑ سومنر، ديفيد ب. (1974)، "الرسوم البيانية ذات العوامل من الدرجة 1"، وقائع الجمعية الرياضية الأمريكية ، 42 (1)، الجمعية الرياضية الأمريكية: 8-12 ، doi : 10.2307/2039666 ، JSTOR 2039666 ، MR 0323648 . Las Vergnas, M. (1975)، “A note on matchings in graphs”، دفاتر مركز دراسات البحث التشغيلي ، 17 (2–3–4): 257–260 ، MR 0412042 .
↑ هاراري (1972) ، النظرية 8.5، ص 78. ينسب هاراري النتيجة إلى غاري شارتراند .
↑ إردوش، بول ؛ ساكس، مايكل ؛ سوس، فيرا ت. (1986)، "الأشجار المستحثة القصوى في الرسوم البيانية"، مجلة نظرية التوافيق، السلسلة ب ، 41 (1): 61-79 ، doi : 10.1016/0095-8956(86)90028-6 .
^ تسفيتكوفيتش ورولينسون وسيميتش (2004) .
↑ ميتلسكي وتيشكيفيتش (1997)
↑ هذه النتيجة هي أيضًا النظرية 8.2 لهاري (1972) .
↑ هاراري (1972) ، النظرية 8.11، ص 81. ينسب هاراري هذه النتيجة إلى غاري شارتراند .
^ سيدلاتشيك (1964) ؛ جرينويل وهمينجر (1972) .
↑ أرتشيديكون، دان (1992)، "الرسم البياني الوسيط وازدواجية الجهد والتيار"، الرياضيات المتقطعة ، 104 (2): 111-141 ، doi : 10.1016/0012-365X(92)90328-D ، MR 1172842 .
↑ ماكي، ت. أ. (1989)، "نموذج نظرية الرسم البياني للازدواجية الجغرافية"، الرياضيات التوافقية: وقائع المؤتمر الدولي الثالث (نيويورك، 1985) ، حوليات أكاديمية نيويورك للعلوم، المجلد 555، نيويورك: أكاديمية نيويورك للعلوم، الصفحات 310-315 ، رمز Bibcode : 1989NYASA.555..310M ، doi : 10.1111/j.1749-6632.1989.tb22465.x ، MR 1018637 ، S2CID 86300941 .
↑ بو، أنتوني (1976)، متعددات السطوح: مدخل بصري ، مطبعة جامعة كاليفورنيا، رقم ISBN 978-0-520-03056-5.
↑ لوب، آرثر لي (1991)، هياكل الفضاء - تناغمها وتناغمها ( الطبعة الخامسة)، بيركهاوزر، ISBN 978-3-7643-3588-5.
↑ وايسشتاين، إريك دبليو. "التصحيح" . عالم الرياضيات .
↑ هاراري (1972) ، ص 82.
^ ريياتشيك وفرانا (2011) .
↑ هاراري ونورمان (1960) .
^ تشانغ ولين (1987) .
↑ إيفانز ولامبيوت (2009) .
↑ إيفانز ولامبيوت (2010) .
↑ ميشولام، روي (1 يناير 2001). "مركب الزمرة ومطابقة الرسم البياني الفائق". كومبيناتوريكا . 21 (1): 89-94 . doi : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

مراجع

Beineke، LW (1968)، “الرسوم البيانية المشتقة من digraphs”، في Sachs، H .؛ فوس، H.-J.؛ والتر، H.-J. (محرران)، Beiträge zur Graphentheorie ، لايبزيغ: تيوبنر، الصفحات من 17 إلى 33 .
بينيك، إل دبليو (1970)، "خصائص الرسوم البيانية المشتقة"، مجلة نظرية التوافيق ، 9 (2): 129-135 ، doi : 10.1016/S0021-9800(70)80019-9 ، MR 0262097 .
سفيتكوفيتش، دراغوش؛ رولينسون، بيتر؛ سيميتش، سلوبودان (2004)، تعميمات طيفية للرسوم البيانية الخطية ، سلسلة محاضرات جمعية لندن الرياضية، المجلد 314، كامبريدج: مطبعة جامعة كامبريدج، doi : 10.1017/CBO9780511751752 ، ISBN 0-521-83663-8MR 2120511 .
دي جورجي، دانييلي جورجيو؛ سيمون، كلاوس (1995)، "خوارزمية ديناميكية للتعرف على الرسوم البيانية الخطية"، مفاهيم نظرية الرسوم البيانية في علوم الحاسوب (آخن، 1995) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1017، برلين: سبرينغر، الصفحات 37-48 ، doi : 10.1007/3-540-60618-1_64 ، ISBN 978-3-540-60618-5MR 1400011 .
إيفانز، تي إس؛ لامبيوت، آر. (2009)، "الرسوم البيانية الخطية، وتقسيمات الروابط، والمجتمعات المتداخلة"، مجلة Physical Review E ، 80 (1) 016105، arXiv : 0903.2181 ، Bibcode : 2009PhRvE..80a6105E ، doi : 10.1103/PhysRevE.80.016105 ، PMID 19658772 .
إيفانز، تي إس؛ لامبيوت، آر. (2010)، "الرسوم البيانية الخطية للشبكات الموزونة للمجتمعات المتداخلة"، المجلة الأوروبية للفيزياء ب ، 77 (2): 265-272 ، arXiv : 0912.4389 ، Bibcode : 2010EPJB...77..265E ، doi : 10.1140/epjb/e2010-00261-8 ، S2CID 119504507 .
غرينويل، دي إل؛ هيمينجر، روبرت إل (1972)، "الرسوم البيانية الفرعية المحظورة للرسوم البيانية ذات الرسوم البيانية الخطية المستوية"، الرياضيات المتقطعة ، 2 : 31-34 ، doi : 10.1016/0012-365X(72)90058-1 ، MR 0297604 .
هراري، ف . نورمان، ر.ز (1960)، “بعض خصائص الرسوم البيانية الخطية”، Rendiconti del Circolo Matematico di Palermo ، 9 (2): 161–169 ، دوى : 10.1007/BF02854581 ، hdl : 10338.dmlcz/128114 ، S2CID 122473974 .
هاراري، ف. (1972)، "8. الرسوم البيانية الخطية"، نظرية الرسوم البيانية (ملف PDF) ، ماساتشوستس: أديسون-ويسلي، ص 71-83 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 2017-02-07 ، تم استرجاعه بتاريخ 2013-11-08 .
هيمينجر، آر إل؛ بينيك، إل دبليو (1978)، "الرسوم البيانية الخطية والرسوم البيانية الخطية الموجهة"، في بينيك، إل دبليو؛ ويلسون، آر جيه (محرران)، مواضيع مختارة في نظرية الرسم البياني ، دار النشر الأكاديمية، الصفحات 271-305 .
Jung، HA (1966)، “Zu einem Isomorphiesatz von H. Whitney für Graphen”، Mathematische Annalen (في الألمانية)، 164 (3): 270–271 ، دوى : 10.1007 / BF01360250 ، MR 0197353 ، S2CID 119898359 .
Krausz، J. (1943)، “Démonstration nouvelle d’un théorème de Whitney sur les réseaux”، مات. فيز. لابوك ، 50 : 75 – 85، م.ر 0018403 .
ليهوت، فيليب جي إتش (1974)، "خوارزمية مثلى لاكتشاف الرسم البياني الخطي وإخراج الرسم البياني الجذري الخاص به"، مجلة ACM ، 21 (4): 569-575 ، doi : 10.1145/321850.321853 ، MR 0347690 ، S2CID 15036484 .
مافري، فريدريك (1992)، "النوى في الرسوم البيانية الخطية المثالية"، مجلة نظرية التوافيق ، السلسلة ب، 55 (1): 1-8 ، doi : 10.1016/0095-8956(92)90028-V ، MR 1159851 .
ميتلسكي، يوري؛ تيشكيفيتش، ريجينا (1997)، "حول الرسوم البيانية الخطية للرسوم البيانية الفائقة الخطية المنتظمة من الدرجة 3"، مجلة نظرية الرسوم البيانية ، 25 (4): 243-251 ، doi : 10.1002/(SICI)1097-0118(199708)25:4 < 243::AID-JGT1 > 3.0.CO ; 2-K.
رامزانبور، أ.؛ كريميبور، ف.؛ مشاغي، أ. (2003)، "توليد شبكات مترابطة من شبكات غير مترابطة" ، مجلة فيزيكال ريفيو إي ، 67 (4) 046107، arXiv : cond-mat/0212469 ، Bibcode : 2003PhRvE..67d6107R ، doi : 10.1103/physreve.67.046107 ، PMID 12786436 ، S2CID 33054818 .
فان رويج، إيه سي إم؛ Wilf, HS (1965)، “The Interchange graph of a finite graph”، Acta Mathematica Hungarica ، 16 ( 3– 4): 263–269 ، دوى : 10.1007/BF01904834 ، hdl : 10338.dmlcz/140421 ، S2CID 122866512 .
روسوبولوس، ن.د. (1973)، "خوارزمية max { m , n } لتحديد الرسم البياني H من الرسم البياني الخطي G الخاص به "، رسائل معالجة المعلومات ، 2 (4): 108-112 ، doi : 10.1016/0020-0190(73)90029-X ، MR 0424435 .
ريياتشيك، زدينيك؛ فرانا ، بيتر (2011)، “الرسوم البيانية الخطية للرسوم البيانية المتعددة وترابط هاميلتون للرسوم البيانية الخالية من المخالب”، مجلة نظرية الرسم البياني ، 66 (2): 152–173 ، دوى : 10.1002 / jgt.20498 ، MR 2778727 ، S2CID 8880045 .
سيدلاسيك، ج. (1964)، "بعض خصائص الرسوم البيانية التبادلية"، نظرية الرسوم البيانية وتطبيقاتها (وقائع ندوة سمولينيتسه، 1963) ، دار نشر الأكاديمية التشيكوسلوفاكية للعلوم، براغ، ص 145-150 ، MR 0173255 .
سيسلو، ماتشي م. (1982)، "خوارزمية تصنيف للتعرف على الرسم البياني الخطي الموجه وإخراج الرسم البياني الجذري الخاص به"، رسائل معالجة المعلومات ، 15 (1): 28-30 ، doi : 10.1016/0020-0190(82)90080-1 ، MR 0678028 .
تروتر، إل إي جونيور (1977)، "الرسوم البيانية الخطية المثالية"، البرمجة الرياضية ، 12 (2): 255-259 ، doi : 10.1007/BF01593791 ، MR 0457293 ، S2CID 38906333 .
دي ويرا، د. (1978)، "حول الرسوم البيانية المثالية المتصلة" ، البرمجة الرياضية ، 15 (2): 236-238 ، doi : 10.1007/BF01609025 ، MR 0509968 ، S2CID 37062237 .
ويتني، هـ. (1932)، "الرسوم البيانية المتطابقة وترابط الرسوم البيانية"، المجلة الأمريكية للرياضيات ، 54 (1): 150-168 ، doi : 10.2307/2371086 ، hdl : 10338.dmlcz/101067 ، JSTOR 2371086 .
تشانغ، فو جي؛ لين، قوه نينغ (1987)، “على الرسوم البيانية دي بروين – جيدة”، اكتا الرياضيات. سينيكا ، 30 (2): 195-205 ، السيد 0891925 .
زيروفيتش، I. ه. (1997)، نظريات تناظرية للرسومات المتعددة والرسومات المتعددة, Diskretnaya Matematika (بالروسية)، 9 (2): 98–105 ، دوى : 10.4213/dm478 ، MR 1468075 تُرجمت إلى الإنجليزية بعنوان: زفيروفيتش، إ. إي. (1997)، "نظير لنظرية ويتني لرسوم بيانية الحواف للرسوم البيانية المتعددة، ورسوم بيانية الحواف المتعددة"، الرياضيات المتقطعة وتطبيقاتها ، 7 (3): 287-294 ، doi : 10.1515/dma.1997.7.3.287 ، S2CID 120525090 .

روابط خارجية

[FOOTNOTEHemmingerBeineke1978273-1] 1 2 هيمينجر وبينيك (1978) ، ص. 273.

[h72-71-2] 1 2 3 هاراري (1972) ، ص 71.

[whitney-3] 1 2 ويتني (1932) ؛ كراوز (1943) ؛ هاراري (1972) ، النظرية 8.3، ص 72. يقدم هاراري برهانًا مبسطًا لهذه النظرية بواسطة يونغ (1966) .

[paschos-4] 1 2 باشوس، فانجيليس ث. (2010)، التحسين التوافقي وعلوم الحاسوب النظرية: واجهات ووجهات نظر ، جون وايلي وأولاده، ص 394، ISBN 978-0-470-39367-3من الواضح أن هناك تطابقًا واحدًا لواحد بين تطابقات الرسم البياني والمجموعات المستقلة للرسم البياني الخطي الخاص به.

[5] تم الإشارة إلى ضرورة مراعاة الرؤوس المعزولة عند النظر في اتصال الرسوم البيانية الخطية بواسطة Cvetković و Rowlinson و Simić (2004) ، ص 32 .

[6] هراري (1972) ، النظرية 8.1، ص. 72.

[7] ديستل، راينهارد (2006)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد 173، سبرينغر، ص 112، ISBN 978-3-540-26183-4. متوفر أيضاً في النسخة الإلكترونية المجانية ، الفصل 5 ("التلوين")، صفحة 118.

[8] لوري، جوزيف؛ سكابيلاتو، رافاييل (2003)، موضوعات في التشكلات الذاتية للرسوم البيانية وإعادة بنائها ، نصوص طلابية من جمعية لندن الرياضية، المجلد 54، كامبريدج: مطبعة جامعة كامبريدج، ص 44، ISBN 0-521-82151-7، MR 1971819 . يعزو لوري وسكابيلاتو هذا الإنجاز إلى مارك واتكينز.

[9] هراري (1972) ، النظرية 8.8، ص. 80.

[FOOTNOTERamezanpourKarimipourMashaghi2003-10] رمضانبور، كريم بور ومشاغي (2003) .

[11] يونج (1966) ؛ ديجيورجي وسيمون (1995) .

[z97-12] 1 2 زفيروفيتش (1997)

[13] فان دام، إدوين ر.؛ هايمرز، ويليم هـ. (2003)، "أي الرسوم البيانية يتم تحديدها بواسطة طيفها؟" ، الجبر الخطي وتطبيقاته ، 373 : 241-272 ، doi : 10.1016/S0024-3795(03)00483-X ، MR 2022290 ، S2CID 32070167 انظر على وجه الخصوص الاقتراح 8، صفحة 262.

[14] هاراري (1972) ، النظرية 8.6، ص 79. ينسب هاراري هذه النتيجة إلى أوراق بحثية مستقلة لـ LC Chang (1959) و AJ Hoffman (1960).

[15] تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2006)، "نظرية الرسم البياني الكامل القوي" ، حوليات الرياضيات ، 164 (1): 51-229 ، arXiv : math/0212070 ، doi : 10.4007/annals.2006.164.51 ، S2CID 119151552 انظر أيضًا: Roussel, F.; Rusu, I.; Thuillier, H. (2009)، "تخمين الرسم البياني المثالي القوي: 40 عامًا من المحاولات، وحلها"، الرياضيات المتقطعة ، 309 (20): 6092-6113 ، doi : 10.1016/j.disc.2009.05.024 ، MR 2552645 ، S2CID 16049392 .

[16] هاراري (1972) ، النظرية 8.7، ص 79. يُنسب هاراري هذا التوصيف للرسوم البيانية الخطية للرسوم البيانية الثنائية الكاملة إلى مون وهوفمان. وقد سبق أن أثبت شريكاندي حالة تساوي عدد الرؤوس على كلا الجانبين.

[17] يانغ، فان؛ هوانغ، شينغيو (2024). "رؤى نظرية حول تحويل الرسم البياني الخطي في تعلم الرسم البياني". arXiv : 2410.16138 [ cs.LG ].

[18] تروتر (1977) ؛ دي ويرا (1978) .

[FOOTNOTEMaffray1992-19] مافري (1992) .

[FOOTNOTETrotter1977-20] تروتر (1977) .

[h72-8.4-21] 1 2 Harary (1972) ، النظرية 8.4 ، ص. 74 ، يقدم ثلاثة توصيفات مكافئة للرسوم البيانية الخطية: تقسيم الحواف إلى زمر، وخاصية كونها خالية من المخالب وخالية من المعين الفردي ، والرسوم البيانية التسعة المحظورة لـ Beineke.

[22] سومنر، ديفيد ب. (1974)، "الرسوم البيانية ذات العوامل من الدرجة 1"، وقائع الجمعية الرياضية الأمريكية ، 42 (1)، الجمعية الرياضية الأمريكية: 8-12 ، doi : 10.2307/2039666 ، JSTOR 2039666 ، MR 0323648 . Las Vergnas, M. (1975)، “A note on matchings in graphs”، دفاتر مركز دراسات البحث التشغيلي ، 17 (2–3–4): 257–260 ، MR 0412042 .

[23] هاراري (1972) ، النظرية 8.5، ص 78. ينسب هاراري النتيجة إلى غاري شارتراند .

[24] إردوش، بول ؛ ساكس، مايكل ؛ سوس، فيرا ت. (1986)، "الأشجار المستحثة القصوى في الرسوم البيانية"، مجلة نظرية التوافيق، السلسلة ب ، 41 (1): 61-79 ، doi : 10.1016/0095-8956(86)90028-6 .

[FOOTNOTECvetkovićRowlinsonSimić2004-25] تسفيتكوفيتش ورولينسون وسيميتش (2004) .

[mt97-26] ميتلسكي وتيشكيفيتش (1997)

[27] هذه النتيجة هي أيضًا النظرية 8.2 لهاري (1972) .

[28] هاراري (1972) ، النظرية 8.11، ص 81. ينسب هاراري هذه النتيجة إلى غاري شارتراند .

[29] سيدلاتشيك (1964) ؛ جرينويل وهمينجر (1972) .

[30] أرتشيديكون، دان (1992)، "الرسم البياني الوسيط وازدواجية الجهد والتيار"، الرياضيات المتقطعة ، 104 (2): 111-141 ، doi : 10.1016/0012-365X(92)90328-D ، MR 1172842 .

[31] ماكي، ت. أ. (1989)، "نموذج نظرية الرسم البياني للازدواجية الجغرافية"، الرياضيات التوافقية: وقائع المؤتمر الدولي الثالث (نيويورك، 1985) ، حوليات أكاديمية نيويورك للعلوم، المجلد 555، نيويورك: أكاديمية نيويورك للعلوم، الصفحات 310-315 ، رمز Bibcode : 1989NYASA.555..310M ، doi : 10.1111/j.1749-6632.1989.tb22465.x ، MR 1018637 ، S2CID 86300941 .

[32] بو، أنتوني (1976)، متعددات السطوح: مدخل بصري ، مطبعة جامعة كاليفورنيا، رقم ISBN 978-0-520-03056-5.

[33] لوب، آرثر لي (1991)، هياكل الفضاء - تناغمها وتناغمها ( الطبعة الخامسة)، بيركهاوزر، ISBN 978-3-7643-3588-5.

[34] وايسشتاين، إريك دبليو. "التصحيح" . عالم الرياضيات .

[35] هاراري (1972) ، ص 82.

[FOOTNOTERyjáčekVrána2011-36] ريياتشيك وفرانا (2011) .

[FOOTNOTEHararyNorman1960-37] هاراري ونورمان (1960) .

[FOOTNOTEZhangLin1987-38] تشانغ ولين (1987) .

[FOOTNOTEEvansLambiotte2009-39] إيفانز ولامبيوت (2009) .

[FOOTNOTEEvansLambiotte2010-40] إيفانز ولامبيوت (2010) .

[41] ميشولام، روي (1 يناير 2001). "مركب الزمرة ومطابقة الرسم البياني الفائق". كومبيناتوريكا . 21 (1): 89-94 . doi : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

13 ] ويمكن

[ 14 ]

[

[

يتطلب

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

فإن

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

32 ] والقطع

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[

[ 39 ]

[

[ 41 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗