عمليات الرسم البياني

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

العمليات الأحادية

تُنشئ العمليات الأحادية رسمًا بيانيًا جديدًا من رسم بياني أولي واحد.

العمليات الأولية

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

العمليات المتقدمة

تُنشئ العمليات المتقدمة رسمًا بيانيًا جديدًا من رسم بياني أولي عن طريق تغيير معقد، مثل:

العمليات الثنائية

تُنشئ العمليات الثنائية رسمًا بيانيًا جديدًا من رسمين بيانيين أوليين G ₁ = ( V ₁ , E ₁ ) و G ₂ = ( V ₂ , E ₂ ) ، مثل:

اتحاد الرسم البياني: G1 ∪ G2 _. يوجد تعريفان. في التعريف الأكثر شيوعًا، وهو الاتحاد المنفصل للرسوم البيانية _، يُفترض أن الاتحاد منفصل. أما التعريف الأقل شيوعًا (وإن كان أكثر اتساقًا مع التعريف العام للاتحاد _في الرياضيات ) _، فيُعرّف اتحاد رسمين بيانيين على أنه الرسم البياني ( V1 ∪ V2 , _E1 ∪ E2 ₎ .
تقاطع الرسم البياني: G ₁ ∩ G ₂ = ( V ₁ ∩ V ₂ , E ₁ ∩ E ₂ ) ; ^{[ 1 ]}
ربط الرسم البياني : $G_{1}\نابلا G_{2}$ . رسم بياني يحتوي على جميع الحواف التي تربط رؤوس الرسم البياني الأول برؤوس الرسم البياني الثاني. وهي عملية تبديلية (للرسوم البيانية غير المصنفة)؛ ^{[ 2 ]}
منتجات الرسوم البيانية القائمة على الضرب الديكارتي لمجموعات الرؤوس:
- ضرب الرسم البياني الديكارتي : إنها عملية تبديلية وتجميعية (للرسوم البيانية غير المصنفة)، ^{[ 2 ]}
- منتج الرسم البياني المعجمي (أو تركيب الرسم البياني): إنها عملية ترابطية (للرسوم البيانية غير المصنفة) وغير تبادلية، ^{[ 2 ]}
- الضرب البياني القوي : هو عملية تبديلية وتجميعية (للرسوم البيانية غير المصنفة)،
- ضرب الموتر في الرسم البياني (أو ضرب الرسم البياني المباشر، ضرب الرسم البياني الفئوي، ضرب الرسم البياني الأساسي، ضرب الرسم البياني لكرونكر): إنها عملية تبادلية وتجميعية (للرسوم البيانية غير المصنفة)،
- منتج بديل ،
- حاصل ضرب الرسم البياني المتعرج ؛ ^{[ 3 ]}
منتج الرسم البياني مبني على منتجات أخرى:
- ضرب الرسم البياني الجذري : هي عملية تجميعية (للرسوم البيانية غير المصنفة ولكن الجذرية)،
- ناتج الرسم البياني التاجي : إنها عملية غير تبادلية؛ ^{[ 4 ]}
تركيب الرسوم البيانية المتسلسلة والمتوازية :
- تركيب الرسوم البيانية المتوازية: هي عملية تبديلية (للرسوم البيانية غير المصنفة)،
- تركيب الرسوم البيانية المتسلسلة: هي عملية غير تبادلية،
- تركيب الرسم البياني المصدر: إنها عملية تبادلية (للرسوم البيانية غير المصنفة)؛
شركة هاجوس للإنشاءات .

ملحوظات

↑ بوندي، جيه إيه؛ مورتي، يو إس آر (2008). نظرية الرسم البياني . نصوص الدراسات العليا في الرياضيات. سبرينغر. ص 29. ISBN 978-1-84628-969-9.
1 2 3 هاراري، ف . نظرية الرسم البياني . ريدينغ، ماساتشوستس: أديسون-ويسلي، 1994.
↑ رينغولد، أ.؛ فادان، س.؛ ويغدرسون، أ. (2002). "موجات الإنتروبيا، وحاصل ضرب الرسم البياني المتعرج، وموسعات جديدة ذات درجة ثابتة". حوليات الرياضيات . 155 (1): 157-187 . arXiv : math/0406038 . doi : 10.2307/3062153 . JSTOR 3062153. MR 1888797 .
^ فروشت، روبرت ؛ هراري ، فرانك (1970). “على هالة اثنين من الرسوم البيانية”. المعادلات الرياضية . 4 : 322-324 . دوى : 10.1007 / bf01844162 . اتش دي ال : 2027.42/44326 .

[bondy_murty-1] بوندي، جيه إيه؛ مورتي، يو إس آر (2008). نظرية الرسم البياني . نصوص الدراسات العليا في الرياضيات. سبرينغر. ص 29. ISBN 978-1-84628-969-9.

[harary-2] 1 2 3 هاراري، ف . نظرية الرسم البياني . ريدينغ، ماساتشوستس: أديسون-ويسلي، 1994.

[3] رينغولد، أ.؛ فادان، س.؛ ويغدرسون، أ. (2002). "موجات الإنتروبيا، وحاصل ضرب الرسم البياني المتعرج، وموسعات جديدة ذات درجة ثابتة". حوليات الرياضيات . 155 (1): 157-187 . arXiv : math/0406038 . doi : 10.2307/3062153 . JSTOR 3062153. MR 1888797 .

[4] فروشت، روبرت ؛ هراري ، فرانك (1970). “على هالة اثنين من الرسوم البيانية”. المعادلات الرياضية . 4 : 322-324 . دوى : 10.1007 / bf01844162 . اتش دي ال : 2027.42/44326 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

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