مخطط مستو: الفرق بين النسختين
[نسخة منشورة] | [نسخة منشورة] |
لا ملخص تعديل |
ط بوت:إضافة مصدر من ويكي الإنجليزية أو الفرنسية (تجريبي) |
||
سطر 1: | سطر 1: | ||
{{مصدر|تاريخ=مارس 2016}} |
|||
[[File:K4 planar.svg|thumb|رسم يوضح المخطط المستوي المكون من أربع حلقات.]] |
[[File:K4 planar.svg|thumb|رسم يوضح المخطط المستوي المكون من أربع حلقات.]] |
||
في [[نظرية المخططات|المخططات]]، '''المخطّط المستوي''' هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط.<ref>{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=64|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|accessdate=8 August 2012|quote=Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.}}</ref><ref>{{cite journal | last1 = Bonichon | first1 = N. | last2 = Gavoille | first2 = C. | last3 = Hanusse | first3 = N. | last4 = Poulalhon | first4 = D. | last5 = Schaeffer | first5 = G. | year = 2006 | title = Planar Graphs, via Well-Orderly Maps and Trees | url = | journal = Graphs and Combinatorics | volume = 22 | issue = | pages = 185–202 | doi=10.1007/s00373-006-0647-2| citeseerx = 10.1.1.106.7456 }}</ref><ref>{{cite journal | last1 = Giménez | first1 = Omer | last2 = Noy | first2 = Marc | year = 2009 | title = Asymptotic enumeration and limit laws of planar graphs | url = | journal = Journal of the American Mathematical Society | volume = 22 | issue = | pages = 309–329 | doi=10.1090/s0894-0347-08-00624-3| arxiv = math/0501269 }}</ref> |
|||
في [[نظرية المخططات|المخططات]]، '''المخطّط المستوي''' هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط. |
|||
== معايير المخطّط المستوي == |
== معايير المخطّط المستوي == |
||
حسب [[كوراتوفسكي]], يكون [[مخططات|المخطط]] مستويا إذا لم يتضمن زمرة من الرتبة الخامسة، أو [[مخطط ثنائي|مخططا ثنائيا]] كاملا من الرتبة الثالثة. |
حسب [[كوراتوفسكي]], يكون [[مخططات|المخطط]] مستويا إذا لم يتضمن زمرة من الرتبة الخامسة، أو [[مخطط ثنائي|مخططا ثنائيا]] كاملا من الرتبة الثالثة. |
||
سطر 38: | سطر 37: | ||
:يكون المخطّط مستويا إذا وفقط إذا لم يتضمّن مخطّطا جزئيّا عبارة عن ''تمديد'' ل ''K''<sub>5</sub> ([[نظرية المخططات#مخطط كامل|زمرة]] ب 5 قمم) أو ''K''<sub>3,3</sub> (المخطّط ثنائي كامل ب3+3 رؤوس). |
:يكون المخطّط مستويا إذا وفقط إذا لم يتضمّن مخطّطا جزئيّا عبارة عن ''تمديد'' ل ''K''<sub>5</sub> ([[نظرية المخططات#مخطط كامل|زمرة]] ب 5 قمم) أو ''K''<sub>3,3</sub> (المخطّط ثنائي كامل ب3+3 رؤوس). |
||
'''التمديد'' بالنّسبة لمخطّط هو نتيجة إضافة قـمّة أو أكثر لحرف أو عدّة حروف (مثلا, تحويل الحرف•——• إلى •—•—•). |
'''التمديد'' بالنّسبة لمخطّط هو نتيجة إضافة قـمّة أو أكثر لحرف أو عدّة حروف (مثلا, تحويل الحرف•——• إلى •—•—•). |
||
== مراجع == |
|||
{{مراجع}} |
|||
== وصلات خارجية == |
== وصلات خارجية == |
نسخة 10:49، 24 ديسمبر 2017
في المخططات، المخطّط المستوي هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط.[1][2][3]
معايير المخطّط المستوي
حسب كوراتوفسكي, يكون المخطط مستويا إذا لم يتضمن زمرة من الرتبة الخامسة، أو مخططا ثنائيا كاملا من الرتبة الثالثة.
وجوه مخطط مستوي
ليكن G مخططا مستويا، الوجه F هو أكبر منطقة من المستوى محدّدة بمجموعة حروف G ولا تتضمن أيا منها.
ليكن G مخطّطا مستويا، و a عدد حروف G. إذن :
صيغة أويلر
تعاريف
- المسار ذو الطول r هو سلسلة من القمم المرتبطة مع أصل السبيل و طرفه.
- يكون المخطّط متّصلا إذا وُجد مسار بين كل قمتين من G.
- المسار المغلق هو حالة .
- الشجرة هي مخطط متّصل بدون أي مسار مغلق.
تمهيدة
كل مخطّط متّصل يمكن الحصول عليه بإضافة عدّة قمم لشجرة (لها نفس عدد القمم).
صيغة أويلر للمخطّطات المستوية المتّصلة
ليكن G مخطّط مستوي متّصل. ليكن n عدد قمم a, G عدد حروفه و f عدد وجوهه. إذن: n − a + f = 2
المعايير
تحديد المعايير التي تمكّن من معرفة ان كان مخطّط ما مستويا. ليكن G مخطّط مستوي متّصل. ليكن n عدد قمم a, G عدد حروفه:
- في حالة وجود مثلّثات.
- في حالة عدم وجود مثلّثات.
مميّزة كوراتوفسكي
الرياضي البولوني كوراتوفسكي وضع الميّزة التالية للمخطّطات المستوية :
- يكون المخطّط مستويا إذا وفقط إذا لم يتضمّن مخطّطا جزئيّا عبارة عن تمديد ل K5 (زمرة ب 5 قمم) أو K3,3 (المخطّط ثنائي كامل ب3+3 رؤوس).
'التمديد بالنّسبة لمخطّط هو نتيجة إضافة قـمّة أو أكثر لحرف أو عدّة حروف (مثلا, تحويل الحرف•——• إلى •—•—•).
مراجع
- ^ Trudeau، Richard J. (1993). Introduction to Graph Theory (ط. Corrected, enlarged republication.). New York: Dover Pub. ص. 64. ISBN:978-0-486-67870-2. اطلع عليه بتاريخ 2012-08-08.
Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.
- ^ Bonichon، N.؛ Gavoille، C.؛ Hanusse، N.؛ Poulalhon، D.؛ Schaeffer، G. (2006). "Planar Graphs, via Well-Orderly Maps and Trees". Graphs and Combinatorics. ج. 22: 185–202. CiteSeerX:10.1.1.106.7456. DOI:10.1007/s00373-006-0647-2.
- ^ Giménez، Omer؛ Noy، Marc (2009). "Asymptotic enumeration and limit laws of planar graphs". Journal of the American Mathematical Society. ج. 22: 309–329. arXiv:math/0501269. DOI:10.1090/s0894-0347-08-00624-3.
وصلات خارجية
- Edge Addition Planarity Algorithm Source Code — Free C source code for reference implementation of Boyer-Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator.
- Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
- 3 Utilities Puzzle and Planar Graphs
- Planarity — A puzzle game created by John Tantalo.
- Mindgames nTangle Freeware nTangle puzzle program with 20,000 puzzles
في كومنز صور وملفات عن: مخطط مستو |