موضوع مقاله: درخت اس‌پی‌کیوآر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت اس‌پی‌کیوآر | مقدمه: ساختارهای بنیادین درخت SPQR، مؤلفه‌های سه همبند گراف، و اتصال بین این اجزا و تعبیهٔ مسطح یک گراف مسطح، را اولین بار ساندرز مک‌لین(1973) بررسی کرد.پژوهشگران دیگری همچون دی‌باتیستا وتاماسیا این ساختارها را، پیش از رسمی شدن به عنوان درخت SPQR در الگوریتم‌های کارآمد استفاده کرده بودند. | ## بخش 1: درخت اس‌پی‌کیوآر | ساختار یک درخت SPQR فرم یک درخت بدون ریشه را دارد که در آن هر گره x با یک گراف بدون جهت یا یک گراف چندگانه Gx متناظر شده‌است. گره و گراف متناظر با آن یکی از 4 فرم زیر را داراست: در یک گرهٔ S، گراف متناظر یک گراف دوری با بیشتر از 2 راس یا یال است.این مورد مشابه ترکیب سری در گراف‌های سری- موازی است؛ S نشان دهندهٔ سری(series) است. در یک گرهٔ P، گراف متناظر یک گراف دوقطبی(یک گراف چندگانه دارای دو راس با تعداد یال بیشتر از 2) است.یک همزاد مسطح(Planar Dual) برای یک گراف دوری. این مورد جزئی تنها برای گراف‌هایی که یک راس دارند به کار برده می‌شود و در گراف‌های پیچیده‌تر ظاهر نمی‌شود. در یک گرهٔ R، گراف متناظر یک گراف سه‌همبند است که دوری با دوقطبی نباشد.R نشان دهندهٔ صلب (rigid ) است: در کاربرد درخت SPQR در تعبیهٔ گراف مسطح، گراف متناظر با یک گرهٔ R یک تعبیهٔ مسطح منحصربه‌فرد دارد. با انجام این گام برای هر یال درخت SPQR گراف GT ساخته می‌شود، ترتیب این گام‌ها تأثیری در نتیجهٔ نهایی ندارد. | ## بخش 2: درخت اس‌پی‌کیوآر | هر راس در گراف Gx با یک راس منحصربه‌فرد در GT متناظر می‌شود.(راس فوقانی که از ادغام این راس به وجود آمده است.) معمولاً" در یک درخت SPQR دو گرهٔ S یا دو گرهٔ P نمی‌توانند مجاور باشند، زیرا اگر چنین اتفاقی بیفتد دو گرهٔ مجاور می توانند ادغام شوند و یک گرهٔ بزرگتر را تولید کنند. یافتن برش‌های دو راسی با استفاده از درخت SPQR یک گراف G (بدون گره‌های Q) یافتن هرکدام از جفت راس‌هایی مانند x و u، که حذف کردن آن‌ها باعث غیرهمبند شدن گراف می شود، و مولفه‌های همبند گراف باقی‌مانده، سر‌راست می شود. دو راس u و v ممکن است دو سر یک یال مجازی در گراف متناظر با یک گرهٔ R باشند، که در این صورت دو مولفه با دو زیردرخت از درخت SPQR نشان داده می شوند که از حذف کردن یال متناظر در درخت SPQR به دست می آیند. دو راس u و v ممکن است دو راس در گراف متناظر با یک گرهٔ P باشند که تعداد 2 یا بیشتر یال مجازی دارد. در این صورت مولفه‌هایی که با حذف u و v به وجود می آیند، با زیردرخت‌هایی از درخت SPQR نشان داده می شوند به طوری که هر یک در ازای یکی از یال‌های مجازی گره است. دو راس u و v ممکن است دو راس در گراف متناظر با یک گرهٔ S باشند به طوری که یا u و v مجاور نیستند یا یال uv مجازی است. | ## بخش 3: درخت اس‌پی‌کیوآر | اگر یال مجازی باشد، دوتایی (u،v ) به یک گرهٔ نوع P و R هم تعلق دارند و مولفه‌های آن‌ها در بالا توصیف شده‌اند. اگر دو راس مجاور نباشند پس دو مولفه با دو مسیر در گراف دوری متناظر با گرهٔ S، و با گره‌های وابسته به آن دو مسیر در درخت SPQR نشان داده می شود. تعبیهٔ گراف‌های مسطح گراف مسطح سه‌همبند، با توجه به جهتگیری و انتخاب اینکه کدام وجه آن وجه خارجی باشد، یک تعبیهٔ مسطح منحصربه‌فرد دارد. هرچند برای یک گراف مسطح( با یال‌ها و راس‌های برچسب‌دار) که دوهمبند باشد، آزادی بیشتری برای پیدا کردن تعبیهٔ همبند وجود دارد. مخصوصا" وقتی دو گره در درخت SPQR گراف، که با یک جفت یال مجازی به هم متصلند، تغییر جهتگیری یکی از گره‌ها امکان‌پذیر است. | ## جمع‌بندی | همچنین در یک گرهٔ P درخت SPQR قسمت‌های مختلف درخت که با یال‌های مجازی با گرهٔ P ارتباط دارند، می توانند به صورت دلخواه جابه‌جا شوند.