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

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

وصف سيمور بنزر ( 1959 ) مفهومًا مشابهًا لمخططات السلاسل عند تطبيقه على البنى الجينية. وفي هذا السياق، طرح أيضًا الحالة الخاصة بتقاطع الفترات على خط، وهي عائلة مخططات الفترات الكلاسيكية . ^{[ 1 ]} لاحقًا، حدد سيندن (1966) الفكرة نفسها للشبكات الكهربائية والدوائر المطبوعة. ^{[ 2 ]} بدأت الدراسة الرياضية لمخططات السلاسل بورقة بحثية لإيرليخ وإيفن وتارجان (1976) ، ومن خلال تعاون بين سيندن ورونالد غراهام ، حيث طُرح توصيف مخططات السلاسل في النهاية كسؤال مفتوح في الندوة المجرية الخامسة حول التوافقية عام 1976. ^{[ 3 ]} ومع ذلك، فقد ثبت في النهاية أن التعرف على مخططات السلاسل مسألة NP-كاملة ، مما يعني أنه من غير المرجح وجود توصيف بسيط لها. ^{[ 4 ]} 

كل رسم بياني مستوٍ هو رسم بياني سلسلة: ^{[ 5 ]} يمكن تكوين تمثيل رسم بياني سلسلة لأي رسم بياني مضمن في مستوى عن طريق رسم سلسلة لكل رأس تدور حول الرأس وحول نقطة منتصف كل حافة مجاورة، كما هو موضح في الشكل. لأي حافة${\displaystyle uv}$من الرسم البياني، السلاسل لـ${\displaystyle u}$و${\displaystyle v}$يتقاطعان مرتين بالقرب من منتصف${\displaystyle uv}$ولا توجد تقاطعات أخرى، لذا فإن أزواج السلاسل المتقاطعة تمثل بالضبط أزواج الرؤوس المتجاورة في الرسم البياني المستوي الأصلي. وبدلاً من ذلك، وفقًا لنظرية تعبئة الدوائر ، يمكن تمثيل أي رسم بياني مستوي كمجموعة من الدوائر، حيث تتقاطع أي دائرتين إذا وفقط إذا كانت الرؤوس المقابلة لهما متجاورة؛ توفر هذه الدوائر (مع اختيار نقطة بداية ونهاية لتحويلها إلى منحنيات مفتوحة) تمثيلًا بيانيًا للسلاسل للرسم البياني المستوي المعطى. أثبت تشالوبين، وغونسالفيس، وأوشيم (2007) أن لكل رسم بياني مستوي تمثيلًا بيانيًا للسلاسل حيث يحتوي كل زوج من السلاسل على نقطة تقاطع واحدة على الأكثر، على عكس التمثيلات الموصوفة أعلاه. إن حدسية شاينرمان ، التي تم إثباتها الآن، هي بيان أقوى مفاده أنه يمكن تمثيل كل رسم بياني مستوي بواسطة رسم بياني لتقاطع القطع المستقيمة، وهي حالة خاصة جدًا من السلاسل.

إذا كان كل ضلع من أضلاع الرسم البياني المعطى${\displaystyle G}$إذا تم تقسيم الرسم البياني الناتج، فسيكون رسمًا بيانيًا للسلاسل إذا وفقط إذا${\displaystyle G}$مستوي. على وجه الخصوص، تقسيم الرسم البياني الكامل${\displaystyle K_{5}}$الرسم التوضيحي ليس رسمًا بيانيًا للسلاسل النصية، لأن${\displaystyle K_{5}}$ليس مستوياً. ^{[ 5 ]}

كل رسم بياني دائري ، باعتباره رسمًا بيانيًا لتقاطع القطع المستقيمة (أوتار الدائرة)، هو أيضًا رسم بياني نصي. يمكن تمثيل كل رسم بياني وتري كرسم بياني نصي: الرسوم البيانية الوترية هي رسوم بيانية لتقاطع الأشجار الفرعية، ويمكن تكوين تمثيل نصي لرسم بياني وتري عن طريق تكوين تضمين مستوٍ للشجرة المقابلة واستبدال كل شجرة فرعية بسلسلة تتبع حواف الشجرة الفرعية. ^{[ 6 ]}

الرسم البياني المكمل لكل رسم بياني للمقارنة (المعروف أيضًا باسم الرسم البياني للمقارنة المشتركة ) هو أيضًا رسم بياني للسلاسل النصية. ^{[ 7 ]}

أظهر كراتوشفيل (1991ب) أن التعرف على الرسوم البيانية للسلاسل النصية يُصنف ضمن فئة NP-hard ، لكنه لم يتمكن من إثبات إمكانية حله ضمن فئة NP . ^{[ 8 ]} يتمثل أحد عوائق حل هذه المشكلة ضمن فئة NP في أن جميع أنظمة المنحنيات التي تُمثل الرسم البياني لبعض السلاسل النصية تحتوي على عدد أُسّي من التقاطعات، لذا لا يُمكن استخدام تمثيل صريح كدليل ذي حجم متعدد الحدود على أن الرسم البياني هو رسم بياني للسلاسل النصية. ^{[ 9 ]} بدلاً من ذلك، ركزت الأبحاث اللاحقة في هذا المجال على وصف مُختصر للتمثيلات من حيث تسلسلات التقاطعات على كل سلسلة نصية، والموصوفة باستخدام نظرية اللغات الرسمية . بعد نتائج وسيطة لشايفر وستيفانكوفيتش (2001) وباش وتوث (2002) ، أكمل شايفر وسيدجويك وستيفانكوفيتش (2003) إثبات أن المشكلة تقع ضمن فئة NP، وبالتالي فهي مسألة كاملة من فئة NP . ^{[ 4 ]}

أظهر إيرليخ وإيفن وتارجان (1976) أن اختبار ما إذا كان الرسم البياني للسلسلة${\displaystyle k}$تُعتبر مسألة التلوين -colorable مسألة NP-كاملة، لكل${\displaystyle k\geq 3}$وحتى عند اقتصارها على الرسوم البيانية ذات التمثيل النصي المحدد المكون من قطع مستقيمة. ^{[ 10 ]} يمكن إيجاد التلوين الثلاثي للرسوم البيانية النصية، إن وُجد، في الحد الزمني شبه الأسي.${\displaystyle 2^{O(n^{2/3}\log n)}}$لكن من غير المرجح تحقيق وقت مماثل لعدد أكبر من الألوان، وفقًا للافتراضات القياسية لنظرية التعقيد: خوارزمية للتلوين بأربعة ألوان في وقت${\displaystyle 2^{o(n)}}$^{[ 11 ]} من شأنه أن يتعارض مع فرضية الزمن الأسي .

أصغر رسم بياني ليس رسمًا بيانيًا للسلاسل النصية يحتوي على 12 رأسًا. ^{[ 12 ]}

لاحظ كراتوشفيل (1991أ) أن المحددات المستحثة للرسوم البيانية الخيطية هي أيضًا رسوم بيانية خيطية. تُستخلص المحددات المستحثة من رسم بياني مُعطى عن طريق تقليص الحواف وحذف الرؤوس؛ وعلى عكس الشكل الأكثر عمومية للمحددات البيانية، فإنها لا تسمح بحذف الحواف. بالنسبة للمحددات البيانية، تنص نظرية روبرتسون-سيمور على أن أي خاصية رسم بياني مغلقة تحت المحددات لها عدد محدود من المحددات الصغرى الممنوعة . ومع ذلك، لا ينطبق هذا على المحددات المستحثة، وقد وجد كراتوشفيل عائلة لانهائية من المحددات الصغرى الممنوعة المستحثة للرسوم البيانية الخيطية. ^{[ 13 ]}

على غرار نظرية الفاصل المستوي ، كل${\displaystyle m}$يمكن تقسيم الرسم البياني للسلسلة ذي الحواف إلى مجموعتين فرعيتين، كل منهما تمثل جزءًا ثابتًا من حجم الرسم البياني بأكمله، عن طريق إزالة${\displaystyle O(m^{3/4}\log ^{1/2}m)}$الرؤوس. ويترتب على ذلك أن الرسوم البيانية للسلاسل الخالية من الثنائيات ، هي رسوم بيانية للسلاسل لا تحتوي على رؤوس.${\displaystyle K_{t,t}}$رسم بياني فرعي لبعض الثوابت${\displaystyle t}$، يملك${\displaystyle O(n)}$الحواف ولها توسع متعدد الحدود بشكل أقوى . ^{[ 14 ]}

• بنزر، س. (1959)، "حول طوبولوجيا البنية الجينية الدقيقة"، وقائع الأكاديمية الوطنية للعلوم في الولايات المتحدة الأمريكية ، 45 (11): 1607-1620 ، Bibcode : 1959PNAS...45.1607B ، doi : 10.1073/pnas.45.11.1607 ، PMC 222769 ، PMID 16590553  .
• بونيه، إدوارد؛ رزافسكي، باويل (2019)، "برنامج الأمثلية في الرسوم البيانية القطاعية والسلسلة"، Algorithmica ، 81 (7): 3047-3073 ، doi : 10.1007/s00453-019-00568-7 ، MR 3948280 .
• شالوبين، ج.؛ غونسالفيس، د.؛ أوشيم، ب. ( 2007)، "الرسوم البيانية المستوية موجودة في 1-STRING"، وقائع الندوة السنوية الثامنة عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​ACM وSIAM، ص 609-617 .
• دفوراك، زدينيك ؛ نورين، سيرجي (2016)، "الفواصل شبه الخطية القوية والتوسع متعدد الحدود"، مجلة SIAM للرياضيات المتقطعة ، 30 (2): 1095-1101 ، arXiv : 1504.04821 ، doi : 10.1137/15M1017569.
• إيرليخ، ج.؛ إيفن، س.؛ تارجان، ر. إي. (1976)، "مخططات تقاطع المنحنيات في المستوى"، مجلة نظرية التوافيق ، 21 (1): 8-20 ، doi : 10.1016/0095-8956(76)90022-8.
• فوكس، جاكوب ؛ باتش، يانوس (2010)، "نظرية فاصلة لرسوم بيانية السلاسل وتطبيقاتها" ، التوافقية، الاحتمالات والحوسبة ، 19 (3): 371، doi : 10.1017/s0963548309990459 ، S2CID 5705145 .
• فوكس، جاكوب ؛ باتش، يانوس (2012)، "مخططات السلاسل ومخططات عدم المقارنة"، التقدم في الرياضيات ، 230 (3): 1381-1401 ، doi : 10.1016/j.aim.2012.03.011 ، hdl : 1721.1/98834 ، MR 2921183 .
• جولومبيك، إم سي ؛ روتيم، دي؛ أوروتيا، جيه (1983)، "مخططات المقارنة ومخططات التقاطع"، الرياضيات المتقطعة ، 43 (1): 37-46 ، doi : 10.1016/0012-365X(83)90019-5.
• غراهام، آر إل (1976)، "المسألة 1"، مسائل مفتوحة في الندوة المجرية الخامسة حول التوافقية.
• كراتوشفيل، يان (1991أ)، "مخططات السلاسل. الجزء الأول: عدد المخططات الحرجة غير السلاسلية لانهائي"، مجلة نظرية التوافيق، السلسلة ب ، 52 (1): 53-66 ، doi : 10.1016/0095-8956(91)90090-7.
• كراتوشفيل، يان (1991ب)، "مخططات السلاسل. الجزء الثاني: التعرف على مخططات السلاسل مسألة صعبة من نوع NP"، مجلة نظرية التوافيق، السلسلة ب ، 52 (1): 67-78 ، doi : 10.1016/0095-8956(91)90091-W.
• الأماكن القريبة : جولجان، ميروسلاف؛ كوتشيرا، بيتر (1986)، “الرسوم البيانية المتسلسلة”، Rozpravy Československé Akad. فيد شادا مات. بريرود. فيد ، 96 (3): 96، م.ر 0865778 .
• الأماكن القريبة : ماتوسيك، جيري (1991)، “الرسوم البيانية المتسلسلة التي تتطلب تمثيلات أسية”، مجلة النظرية التوافقية، السلسلة ب ، 53 (1): 1– 4، دوى : 10.1016 / 0095-8956 (91)90050-T ، MR 1122293 .
• لوفاس، ل. (1983)، "الرسوم البيانية المثالية"، مواضيع مختارة في نظرية الرسوم البيانية ، المجلد  2، لندن: أكاديميك برس، الصفحات 55-87 .
• باتش، يانوس ؛ توث، جيزا (2002)، "التعرف على الرسوم البيانية للسلاسل قابل للتقرير"، الهندسة المنفصلة والحسابية ، 28 (4): 593-606 ، doi : 10.1007/s00454-002-2891-4.
• شايفر، ماركوس؛ ستيفانكوفيتش، دانيال ( 2001)، "قابلية تحديد رسوم بيانية السلاسل"، وقائع الندوة السنوية الثالثة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC 2001) : 241-246.
• شيفر، ماركوس؛ سيدجويك، إريك؛ ستيفانكوفيتش، دانيال (2003)، "التعرف على رسوم بيانية للسلاسل في NP"، مجلة علوم الحاسوب والأنظمة ، 67 (2): 365-380 ، doi : 10.1016/S0022-0000(03)00045-X.
• سيندن، إف دبليو (1966)، "طوبولوجيا دوائر RC ذات الأغشية الرقيقة"، مجلة بيل سيستم التقنية ، 45 (9): 1639-1662 ، doi : 10.1002/j.1538-7305.1966.tb01713.x.