تدفق معدوم

في نظرية الرسوم البيانية ، يُعرف التدفق الذي لا يساوي الصفر في أي مكان، أو التدفق NZ، بأنه تدفق شبكي لا يساوي الصفر في أي مكان. وهو مرتبط ارتباطًا وثيقًا (عن طريق الازدواجية) بتلوين الرسوم البيانية المستوية .

التعريفات

ليكن G = ( V , E ) مخططًا موجهًا، ولتكن M زمرة تبديلية . يُقال عن التطبيق φ : E → M أنه دوران M إذا كان لكل رأس v ∈ V

\sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),

حيث تشير δ ⁺ ( v ) إلى مجموعة الحواف الخارجة من v وتشير δ ⁻ ( v ) إلى مجموعة الحواف الداخلة إلى v . ويُشار إلى هذا الشرط أحيانًا باسم قانون كيرشوف .

إذا كانت φ ( e ) ≠ 0 لكل e ∈ E ، فإننا نسمي φ تدفقًا لا صفري في أي مكان، أو تدفق M ، أو تدفق NZ. إذا كان k عددًا صحيحًا و 0 < | φ ( e )| < k، فإن φ هو تدفق k . ^{[ 1 ]}

مفاهيم أخرى

ليكن G = ( V , E ) رسمًا بيانيًا غير موجه . يكون اتجاه E تدفقًا معياريًا من الرتبة k إذا كان لكل رأس v ∈ V لدينا:

|\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.

ملكيات

لا تشكل مجموعة التدفقات M بالضرورة مجموعة، حيث أن مجموع تدفقين على حافة واحدة قد يصل إلى 0.
(توت، 1950) يكون للرسم البياني G تدفق من الرتبة M إذا وفقط إذا كان له تدفق من الرتبة | M |. ونتيجة لذلك، فإن $\mathbb {Z} _{k}$ يوجد تدفق إذا وفقط إذا وُجد تدفق من الرتبة k . ^{[ 1 ]} ونتيجة لذلك، إذا كانت G تقبل تدفقًا من الرتبة k، فإنها تقبل تدفقًا من الرتبة h حيث $h\geq k$ .
استقلالية الاتجاه. عدّل تدفقًا لا صفري φ على الرسم البياني G باختيار حافة e ، وعكس اتجاهها، ثم استبدال φ ( e ) بـ −φ ( e ). بعد هذا التعديل، يظل φ تدفقًا لا صفري. علاوة على ذلك، إذا كان φ في الأصل تدفقًا من الرتبة k ، فإن φ الناتج هو أيضًا تدفق من الرتبة k . بالتالي، فإن وجود تدفق M لا صفري أو تدفق k لا صفري مستقل عن اتجاه الرسم البياني. لذا، يُقال إن الرسم البياني غير الموجه G يحتوي على تدفق M لا صفري أو تدفق k لا صفري إذا كان هناك اتجاه (وبالتالي كل) اتجاه من اتجاهات G يحتوي على مثل هذا التدفق.

متعدد الحدود للتدفق

يترك $N_{M}(G)$ ليكن عدد التدفقات M على G. وهو يحقق صيغة الحذف والانكماش : ^{[ 1 ]}

N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).

وبدمج هذا مع الاستقراء يمكننا أن نبين $N_{M}(G)$ هي متعددة الحدود في $|M|-1$ أين $|M|$ هي رتبة المجموعة M. نسميها $N_{M}(G)$ متعدد الحدود التدفق للمجموعة G والمجموعة الأبيلية M.

يشير ما سبق إلى أن مجموعتين من نفس الرتبة لهما نفس عدد تدفقات NZ. الرتبة هي المعيار الوحيد المهم للمجموعة، وليس بنية M. على وجه الخصوص $N_{M_{1}}(G)=N_{M_{2}}(G)$ لو $|M_{1}|=|M_{2}|.$

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

ازدواجية التلوين بالتدفق

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

توجد ازدواجية بين تلوينات الوجوه من الرتبة k وتدفقات الوجوه من الرتبة k للرسوم البيانية المستوية عديمة الجسور . ولتوضيح ذلك، ليكن G رسمًا بيانيًا مستويًا موجهًا عديم الجسور مع تلوين مناسب للوجوه من الرتبة k بألوان $\{0,1,\ldots ,k-1\}.$ قم بإنشاء خريطة

\phi :E(G)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}

وفقًا للقاعدة التالية: إذا كان للحافة e وجه بلون x على اليسار ووجه بلون y على اليمين، فليكن φ ( e ) = x – y . عندئذٍ يكون φ تدفقًا من النوع (NZ) k لأن x و y يجب أن يكونا بلونين مختلفين.

إذا كان G و G* رسمين بيانيين ثنائيين مستويين ، وكان G* قابلاً للتلوين بـ k لون (أي أن هناك تلوينًا لأوجه G )، فإن G يمتلك تدفقًا من الرتبة n-Z من الرتبة k . وباستخدام الاستقراء على | E ( G )|، أثبت توت أن العكس صحيح أيضًا. ويمكن التعبير عن ذلك بإيجاز كما يلي: ^{[ 1 ]}

\chi (G^{*})=\phi (G),

حيث يمثل RHS رقم التدفق ، وهو أصغر قيمة k التي تسمح بها G بتدفق k .

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

ينطبق هذا الازدواجية على التدفقات العامة من النوع M أيضًا:

يترك $c$ لتكن دالة تلوين الوجه ذات القيم في M.
يُعرِّف $\phi _{c}(e)=c(r_{1})-c(r_{2})$ حيث r ₁ هو الوجه الموجود على يسار e و r ₂ هو الوجه الموجود على اليمين.
لكل دورة M $\phi$ توجد دالة تلوين c بحيث $\phi =\phi _{c}$ (ثبت بالاستقراء).
c هو تلوين وجه من النوع | E ( G )| إذا وفقط إذا $\phi _{c}$ هو تدفق NZ M (مباشر).

تتضح الازدواجية من خلال الجمع بين النقطتين الأخيرتين. يمكننا التخصص في $M=\mathbb {Z} _{k}$ للحصول على نتائج مماثلة لتدفقات k المذكورة أعلاه. ونظرًا لهذه الازدواجية بين تدفقات NZ والتلوين، وبما أنه يمكننا تعريف تدفقات NZ لأي نوع من الرسوم البيانية (وليس فقط الرسوم البيانية المستوية)، يمكننا استخدام ذلك لتوسيع نطاق تلوين الأوجه ليشمل الرسوم البيانية غير المستوية. ^{[ 1 ]}

التطبيقات

تكون G قابلة للتلوين بوجهين إذا وفقط إذا كان لكل رأس درجة زوجية (ضع في اعتبارك التدفقات الثنائية NZ). ^{[ 1 ]}
يترك $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ ليكن K مجموعة كلاين-4 . عندئذٍ، يكون للرسم البياني المكعب تدفق K إذا وفقط إذا كان قابلاً للتلوين بثلاثة ألوان على الحواف . وكنتيجة لذلك، فإن الرسم البياني المكعب القابل للتلوين بثلاثة ألوان على الحواف يكون قابلاً للتلوين بأربعة ألوان على الأوجه. ^{[ 1 ]}
يكون الرسم البياني قابلاً للتلوين بأربعة أوجه إذا وفقط إذا كان يسمح بتدفق رباعي من نوع NZ (انظر نظرية الألوان الأربعة ). لا يحتوي الرسم البياني لبيترسن على تدفق رباعي من نوع NZ، وقد أدى ذلك إلى تخمين التدفق الرباعي (انظر أدناه).
إذا كان G مثلثًا، فإن G يكون قابلًا للتلوين بثلاثة ألوان (رؤوس) إذا وفقط إذا كان لكل رأس درجة زوجية. وبحسب النقطة الأولى، فإن الرسم البياني الثنائي G * قابل للتلوين بلونين، وبالتالي فهو ثنائي الأجزاء ومكعب مستوٍ. لذا، فإن G * له تدفق NZ ثلاثي، وبالتالي فهو قابل للتلوين بثلاثة ألوان (وجوه)، مما يجعل G قابلًا للتلوين بثلاثة ألوان (رؤوس). ^{[ 1 ]}
كما أنه لا يوجد رسم بياني ذو حافة حلقية له تلوين رؤوس صحيح، فلا يمكن لأي رسم بياني ذي جسر أن يمتلك تدفق NZ M لأي مجموعة M. وعلى العكس من ذلك، فإن كل رسم بياني بدون جسر يمتلك تدفق NZ. $\mathbb {Z}$ التدفق (شكل من أشكال نظرية روبنز ). ^{[ 3 ]}

وجود تدفقات k

مشكلة لم تُحل في الرياضيات

هل لكل رسم بياني بدون جسور تدفق خماسي لا يساوي صفرًا في أي مكان؟ وهل لكل رسم بياني بدون جسور لا يحتوي على رسم بياني بيترسن كرسم بياني فرعي تدفق رباعي لا يساوي صفرًا في أي مكان؟

تُثار تساؤلات مثيرة للاهتمام عند محاولة إيجاد تدفقات k غير الصفرية لقيم k الصغيرة . وقد تم إثبات ما يلي:

نظرية التدفق الرباعي لجاغر. كل رسم بياني متصل بالحواف من الدرجة الرابعة يحتوي على تدفق رباعي. ^{[ 4 ]}

نظرية سيمور للتدفق السداسي. كل رسم بياني بدون جسور له تدفق سداسي.^{[ 5 ]}

تخمينات التدفق الثلاثي، والتدفق الرباعي، والتدفق الخماسي

اعتبارًا من عام 2019، لا تزال المسائل التالية غير محلولة (بسبب توتي ):

تخمين التدفق الثلاثي. كل رسم بياني متصل بأربعة حواف له تدفق ثلاثي غير صفري في أي مكان. ^{[ 6 ]}

تخمين التدفق الرباعي. كل رسم بياني بدون جسور لا يحتوي على رسم بياني بيترسن كرسم بياني فرعي ، يكون له تدفق رباعي لا يساوي الصفر في أي مكان. ^{[ 7 ]}

تخمين التدفق الخماسي. كل رسم بياني بدون جسور له تدفق خماسي لا يساوي الصفر في أي مكان. ^{[ 8 ]}

لا يصح عكس فرضية التدفق الرباعي، لأن الرسم البياني الكامل K ₁₁ يحتوي على رسم بياني بيترسن وتدفق رباعي. ^{[ 1 ]} بالنسبة للرسوم البيانية المكعبة عديمة الجسور والتي لا تحتوي على قاصر بيترسن، توجد تدفقات رباعية وفقًا لنظرية سنارك (سيمور وآخرون، 1998، لم تُنشر بعد). تُكافئ نظرية الألوان الأربعة القول بأن أي سنارك ليس مستويًا. ^{[ 1 ]}

انظر أيضاً

مراجع

1 2 3 4 5 6 7 8 9 10 ديستل، راينهارد (30 يونيو 2017). نظرية الرسم البياني . سبرينغر. ISBN 9783662536216. OCLC 1048203362 .
↑ توت، دبليو تي (1954). "مساهمة في نظرية كثيرات الحدود اللونية". المجلة الكندية للرياضيات . 6 : 80-91 . doi : 10.4153/CJM-1954-010-9 .
↑ للحصول على نتيجة أقوى بشأن تعداد $\mathbb {Z}$ - التدفقات ذات الحد الأقصى لمقدار التدفق لكل حافة، باستخدام نظرية روبنز حول التوجهات الدورية تمامًا، انظر النظرية 2 من كوخول، مارتن (2002)، "كثيرات الحدود المرتبطة بالتدفقات غير الصفرية في أي مكان"، مجلة نظرية التوافقية ، السلسلة ب، 84 (2): 260-269 ، doi : 10.1006/jctb.2001.2081 ، MR 1889258
↑ F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205–216.
↑ PD Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130–135.
↑، حديقة المشاكل المفتوحة.
↑، حديقة المشاكل المفتوحة.
↑، حديقة المشاكل المفتوحة.

للمزيد من القراءة

تشانغ، كون-كوان (1997). تدفقات الأعداد الصحيحة وأغطية الدورات للرسوم البيانية . سلسلة تشابمان آند هول/سي آر سي للرياضيات البحتة والتطبيقية. مارسيل ديكر، إنك. ISBN 9780824797904. إل سي سي إن 96037152 .
تشانغ، كون-كوان (2012). الغلاف المزدوج للدوائر للرسوم البيانية . مطبعة جامعة كامبريدج. ISBN 978-0-5212-8235-2.
جنسن، تي آر؛ توفت، بي. (1995). "13 اتجاهًا وتدفقًا". مسائل تلوين الرسوم البيانية . سلسلة وايلي-إنترساينس في الرياضيات المتقطعة والتحسين. ص 209-219 . ISBN 9780471028659.
جاكوبسن، جيسبر ليك؛ سالاس، خيسوس (2013). "هل فرضية التدفقات الخمسة خاطئة تقريبًا؟". مجلة نظرية التوافيق . السلسلة ب. 103 (4): 532-565 . arXiv : 1009.4062 . doi : 10.1016 / j.jctb.2013.06.001 . MR 3071381. S2CID 41483928 .

[:0-1] 1 2 3 4 5 6 7 8 9 10 ديستل، راينهارد (30 يونيو 2017). نظرية الرسم البياني . سبرينغر. ISBN 9783662536216. OCLC 1048203362 .

[2] توت، دبليو تي (1954). "مساهمة في نظرية كثيرات الحدود اللونية". المجلة الكندية للرياضيات . 6 : 80-91 . doi : 10.4153/CJM-1954-010-9 .

[3] للحصول على نتيجة أقوى بشأن تعداد $\mathbb {Z}$ - التدفقات ذات الحد الأقصى لمقدار التدفق لكل حافة، باستخدام نظرية روبنز حول التوجهات الدورية تمامًا، انظر النظرية 2 من كوخول، مارتن (2002)، "كثيرات الحدود المرتبطة بالتدفقات غير الصفرية في أي مكان"، مجلة نظرية التوافقية ، السلسلة ب، 84 (2): 260-269 ، doi : 10.1006/jctb.2001.2081 ، MR 1889258

[4] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205–216.

[5] PD Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130–135.

[6] ، حديقة المشاكل المفتوحة.

[7] ، حديقة المشاكل المفتوحة.

[8] ، حديقة المشاكل المفتوحة.

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]