پل (نظریه گراف)

یک مسئلهٔ باز که یال‌های برشی را نیز شامل می‌شود مسئلهٔ پوشش مضاعف دورها، بوسیلهٔ جرج زکارس و پل سیمور (در سال‌های ۱۹۷۸ و ۱۹۷۹، مستقل از هم) است که بیان می‌کند هر گراف فاقد یال برشی دورهایی دارد که هر یال را دقیقاً دو بار در بر می‌گیرند.

یالی از گراف برشی است اگر و فقط اگر در هیچ دوری قرار نگرفته باشد.

اثبات با برهان خلف: فرض کنید e = uv یال برشی از گراف همبند G است و e در دور C شامل u,v،w، …x,u قرار گرفته‌است. گراف G – e دارای یک مسیر u-v به شکل u,x، …،w,v است، یعنی u به v متصل است. حال a و b را دو راس دلخواه از G – e در نظر می‌گیریم و نشان می‌دهیم که G – e مسیری از a به b دارد. چون G همبند بود پس مسیر a-b مانند P در G یافت می‌شود. اگر یال e در آن مسیر قرار نداشته باشد مسلماً باز هم همان مسیر P در G – e نیز وجود دارد و a به b در G – e راه دارد. فرض کنید e در مسیر P قرار دارد؛ بنابراین P را می‌توان به صورت a، …،u,v، …،b یا a، …،v,u، …،b نشان داد. قبلاً ثابت کردیم در G – e، از v به u مسیر وجود دارد؛ بنابراین اگر e در دوری قرار گرفته باشد، با حذف آن هنوز هم بین هر دو راس دلخواه a و b از G – e مسیر وجود دارد که یعنی e یال برشی نیست. پس به تناقض رسیدیم.

برعکس فرض کنید e = uv یالی است که در هیچ دوری قرار نگرفته‌است. دوباره با برهان خلف فرض کنید e یال برشی نیست. پس G – e همبند است و مسیری مثل P از u به v در G – e وجود دارد. در این صورت P باضافه e دوری در G ایجاد می‌کند که شامل e است که به تناقض می‌رسیم.

برای گراف روبرو با مراجعه به روش‌های یافتن راس برشی گراف پیمایش شدهٔ زیر را بدست می‌آوریم که B 2/1 به معنای Low(B) = ۱ و Num(B) = ۲ است.

• هر راس v که (Num(v) = Low(v به همراه پدرش یک یال برشی را تشکیل می‌دهند.

در گراف بالا Num(G) = Low(G) = ۷ پس GC (تنها) یال برشی است. در درخت دور وجود ندارد.

گراف‌هایی که هیچ پلی ندارند را بدون پل می‌نامند. حالت معادل گراف بدون پل وقتی است که اجزای متصل گراف دارای یک تجزیه گوشی باز باشند و هر جزء دارای درجه دو (دو اتصال) باشد.

• توضیح و مثال‌هایی از یال و راس برشی
• مباحث نظریهٔ گراف
• یال برشی در سایت wolfram